Data processing system with synchronization coprocessor for multiple threads

Abstract

A multiprocessor system comprises a plurality of processing nodes, each node processing multiple threads of computation. Each node includes a data processor which sequentially processes blocks of code, each block defining a thread of computation. The code includes instructions to send start messages with data values to start new threads of computation. Each node also includes a synchronization coprocessor for processing start messages from the same and other nodes of the system. The coprocessor processes the start messages to store values as operands for threads of computation, to determine when all operands required for a thread of computation have been received and to provide an indication to the data processor that a thread of computation may be initiated. The data processor subsequently nonsynchronously initiates the thread of computation. Preferably, the processors load and store from and to a common memory with the translation from a local virtual address to a local physical address. The data processor creates messages to remote nodes using a global virtual address which is translated before transmission to a node designation and a local virtual address at the remote node. The synchronization coprocessor is a pipeline processor in which a data cache stage is modified to increment and test a counter value during a join operation.

Claims

We claim:

1. A data processing system comprising:

a data processor for processing threads of computation with respect to frames of data, threads of computation including operations to generate messages with operands for initiating new threads of computation; and

a synchronization coprocessor for responding to messages by processing message handlers which store the operands carried by the messages into the frames of data and which indicate to the data processor when conditions including availability of the operands in the frames of data are met such that new threads of computation are to be performed, the data processor being synchronized to availability of operands by initiating processing of the new threads of computation with respect to the frames of data after the synchronization coprocessor indicates that the new threads of computation are to be performed.

2. A data processing system as claimed in claim 1 further comprising a message formatter instructed by the data processor to create and send messages to remote nodes of the data processing system.

3. A data processing system as claimed in claim 2 wherein the message formatter comprises registers on a common bus with the data processor in the address space of the data processor and the data processor instructs the message formatter to create and send message to remote nodes by memory mapped stores to the message formatter registers.

4. A data processing system as claimed in claim 3 wherein the data processor loads global virtual addresses along its data bus into registers in the message formatter, a number of bits in the global virtual address being greater than a number of bits available in the local virtual address space of the data processor, and the message formatter translates the global virtual address to a node designation and a local virtual address on that node.

5. A data processing system as claimed in claim 4 wherein each node translates local virtual addresses to local physical addresses for local memory accesses from the data processor and for local memory accesses in response to messages from remote nodes.

6. A data processing system as claimed in claim 1 wherein the data processor and the synchronization coprocessor communicate with a common local memory in which operands are stored within activation frames by the synchronization coprocessor and fetched by the data processor.

7. A data processing system as claimed in claim 6 further comprising a cache memory shared by the data processor and synchronization coprocessor.

8. A data processing system as claimed in claim 7 wherein the data processor is a single chip microprocessor having a cache memory thereon.

9. A data processing system as claimed in claim 1 wherein the synchronization coprocessor comprises a queue to which continuations are posted to serve as indications to the data processor that the new threads of computation are to be initiated.

10. A data processing system as claimed in claim 9 wherein the queue presents continuations according to priority to continue processing active frames.

11. A data processing system as claimed in claim 10 wherein the synchronization coprocessor comprises a frame registry which identifies active frames to be given priority in the queue.

12. A data processing system as claimed in claim 11 wherein the system maintains a software list of continuations where capacity of the registry is exceeded.

13. A data processing system as claimed in claim 9 wherein the continuations comprise a pointer to an activation frame and a pointer to a data processor instruction.

14. A data processing system as claimed in claim 9 wherein the queue is on a bus of the data processor and new threads of computation are initiated by the data processor by loading continuations from the queue.

15. A data processing system as claimed in claim 1 wherein the messages include an object oriented message which identifies a method, an object and argument, and the synchronization coprocessor stores the argument in a frame and provides a frame pointer to the data processor.

16. A data processing system as claimed in claim 15 wherein the synchronization coprocessor processes the method and object identifications to locate an instruction pointer for the data processor.

17. A data processing system as claimed in claim 1 which is a multiprocessor system of a plurality of processing nodes, each processing node comprising one of said data processors and one of said synchronization coprocessors.

18. A data processing system as claimed in claim 16 wherein each data processor operates on a local virtual address space, and each node comprises means for translating from the local virtual address space to a local physical address space, each data processor generating a global virtual address space to access an address in a remote node, and each node comprising means for translating the global virtual address to a node designation and a local virtual address of the remote node.

19. A data processing system as claimed in claim 1 wherein the messages include a start message which comprises a pointer to an activation frame and a pointer to a synchronization coprocessor instruction.

20. A data processing system as claimed in claim 1 wherein the synchronization coprocessor comprises a start processor for processing start messages and a remote memory processor for processing remote memory load and store instructions from remote nodes.

21. A data processing system as claimed in claim 1 wherein the synchronization coprocessor is a programmable processor.

22. A data processing system as claimed in claim 1 wherein the synchronization coprocessor comprises a processing pipeline including hardware for counting operands received for the threads of computation.

23. A data processing system as claimed in claim 1 wherein the synchronization coprocessor comprises a processing pipeline including increment and test hardware for incrementing a value fetched from cache memory, testing the value to test whether all operands for a computational thread have been received, and returning the incremented value to cache memory.

24. In a multiprocessor system comprising a plurality of processing nodes, each node processing multiple threads of computation, the system comprising at each processing node:

a data processor which processes threads of code, the code including instructions to create messages with data values to start new threads of computation; and

a synchronization coprocessor for processing messages from the same node and other nodes of the system, the synchronization coprocessor processing messages to store values from the messages as operands for the threads of computation, to determine when all operands required for the threads of computation have been received and to provide indications to the data processor that the threads of computation are to be initiated, the data processor nonsynchronously initiating processing of the threads of computation after completion of prior threads of computation in response to the indications from the synchronization coprocessor.

25. A data processing system comprising:

a data processor which sequentially processes, as threads of code, code blocks including local memory load and store instructions, start instructions which cause start messages to be sent with data values to start new threads of computation and remote memory load and store instructions which cause messages to be sent to remote memory locations to fetch or store data from or in the remote memory locations; and

a synchronization coprocessor which receives start messages and processes the start messages to store data values from the start messages as operands for the threads of computation, to determine when all operands required for the threads of computation have been received and to provide indications to the data processor that the threads of computation are to be initiated, the data processor nonsynchronously initiating processing of the threads of computation after completion of prior threads of computation in response to the indications from the synchronization coprocessor.

Description

BACKGROUND OF THE INVENTION

Many are interested in the goal of general purpose computing that achieves very high speeds by exploiting parallelism in a scalable, cost-effective way. There seems to be widespread consensus that the architecture of such machines will be composed of a number of nodes interconnected with a high speed, regular network, where each node is built with an off-the-shelf microprocessor. Because such machines are built out of commodity parts, and because the topology is scalable, it is felt that such a machine with hundreds or thousands of nodes will be cheaper and faster than classical supercomputers, which are built with exotic technology and are thus very expensive.

To date, the prevailing opinion seems to be that microprocessors have their own evolutionary momentum (from CISC to RISC and, now, to a multiple instruction issue), and that a massively parallel machine will simply track this wave, using whatever microprocessors are currently available. However, a massively parallel machine is in fact a hostile environment for today's micros, arising largely because certain properties of the memory system in a massively parallel machine are fundamentally different from those assumed during the evolution of these micros. In particular, most micros today assume that all memory is equally distant, and that memory access time can be made effectively small by cacheing. Both these assumptions are questionable in a massively parallel machine.

On the other hand, dataflow processors have been designed from the start by keeping in mind the properties of the memory system in a parallel machine. However, past dataflow processor designs have neglected single-thread performance, and hence must be classified as exotic, not the kind of processor to be found in commodity workstations.

To be cost-effective, the micros used in massively parallel machines should be commodity parts, i.e., they should be the same micros as those used in workstations and personal computers. Market forces are such that a lot more design effort can be expended on a stock microprocessor than on a processor that is sold only in small quantities. In addition, there is a question of software cost. Parallel programs are often evolved from sequential programs, and will continue to use components that were developed for single-thread uniprocessors (such as transcendental function libraries, Unix, etc.). This does not mean that we are restricted to using good, conventional microprocessors in any parallel machine that we build. All it means is that any new processor that we design for multiprocessors must also stand on its own as a cheap and viable uniprocessor.

Parallel programs contain synchronization events. It is well known that processor utilization suffers if it busy-waits; to avoid this, some form of multiplexing amongst threads (tasks or processes) is necessary. This is true even in uniprocessors.

In order to build parallel machines that are scalable both physically and economically, we must face the fact that inter-node latency in the machine will grow with machine size, at least by a factor of log (N), where N is the number of nodes in the machine. Thus, access to a non-local datum in a parallel machine may take tens to hundreds of cycles, or more. If we are to maintain effective utilization of the machine, a processor must perform some other useful work instead of idling during such a remote access. This requires that the processor be multiplexed amongst many threads, and that remote accesses must be performed as split transactions, i.e., a request and its response should be treated as two separate communication events across the machine. If we follow this argument a step further, we see that a communication entering a node will arrive at some relatively unpredictable time, and that we need some means of identifying the thread that is waiting for this communication. This is, in fact, a synchronization event.

Thus, the following picture emerges. In a parallel machine, the way to deal with long inter-node latencies is exactly the way to deal with synchronization. A program must be compiled with sufficient parallel slackness ("excess parallelism") so that every processor has a pool of threads instead of a single thread, and some threads are always likely to be ready to run. Each processor must be able to multiplex itself efficiently amongst these threads. All communications should be split transactions, in which (a) an issuing processor does not block to await a response, and (b) a receiving processor can efficiently identify and enable the thread that awaits an incoming communication. For a more thorough explication of this argument, please refer to Arvind and R. A. Iannucci, "Two Fundamental Issues in Multiprocessing," Proceedings of DFVLR--Conference 1987 on Parallel Processing in Science and Engineering, Bonn-Bad Godesberg, W. Germany, Springer-Verlag LNCS 295, Jun. 25-29, 1987.

Modern von Neumann microprocessors are excellent single-thread processors, but they are not designed to exploit parallel slackness efficiently. First, the cost of multiplexing amongst threads is high because of the enormous processor state that is associated with the currently executing thread. This state manifests itself in the register set and instruction and data caches, all of which may have to be reloaded with the new thread's context. Second, for a parallel environment, there is no efficient mechanism for naming, communicating and invoking continuations for split transactions to access remote locations. Third, many first-generation parallel machines had very poor interfaces to the interconnection network. There was a large software cost in handling incoming messages. This was further aggravated by the fact that messages trying to cross a node had to go through the node. However, many of the successors of these machines have solved this problem somewhat by devoting separate resources to message handling.

The net result is a high communication and synchronization cost with von Neumann machines. Programs can be written to use these machines effectively provided they minimize the occurrence of communication and synchronization events, and there are many success stories that do so. However, there is a high software cost associated with trying to structure programs to fit this model, and it is still a far cry from our goal of truly general purpose computing.

Dataflow architectures have evolved substantially over the years. We will focus our comments on Monsoon (G. M. Papadopoulos, "Implementation of a General-Purpose Dataflow Multiprocessor," PhD thesis, Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, Mass. 02139, August 1988; G. M. Papadopoulos and D. E. Culler, "Monsoon: An Explicit Token Store Architecture," Proc. 17th Intl. Symp. on Computer Architecture, Seattle, Wash., May 1990 and U.S. patent application Ser. No. 07/396,480) as the most recent representative of that evolution.

Dataflow architectures are excellent at exploiting parallel slackness. Indeed, this has always been a major underlying rationale for dataflow architectures. Parallel slackness is achieved by partitioning a program into extremely fine grain threads; in the pure dataflow model, each instruction is a separate thread. A thread descriptor is implemented as a token, which includes three parts (FP, IP, V), where:

FP is a frame pointer, which points at a frame relative to which the instruction will be executed;

IP is an instruction pointer, which points t code; and

V is a data value.

The pool of threads in a processor is manifest at a token queue. On each cycle, a token is extracted from the token queue, and the instruction to which it refers is executed by the processor relative to the frame to which it points. Every instruction explicitly names its successor instruction(s). As a result of this execution, zero, one, or two successor tokens are produced, which are placed back in the token queue. Thus, a dataflow processor like Monsoon can multiplex between threads on every cycle.

Split transactions are performed thus: when a processor wishes to read a remote location A, it executes a fetch instruction. This causes a "read" token to be constructed and injected into the network. Suppose the fetch instruction names label L as its successor instruction. The corresponding read request token contains the following information:

(READ, A, FP, L)

Once the read request token is sent out, the processor continues to execute other tokens in its token queue. When the read request token reaches the remote memory, the following token is sent back:

(FP, L, V)

This token is placed in the token queue to be executed just like any other token.

In addition, Monsoon also has an efficient mechanism to synchronize two threads. Two threads that must join will arrive at a common instruction that names a frame location which contains "presence bits", which can be regarded as a synchronization counter. On arrival, each thread causes the counter to decrement. When the first thread arrives, the counter does not reach its terminal value; the instruction is aborted and the processor moves on to execute another token from the token queue. When the second thread arrives, the counter reaches its terminal value and the instruction is executed.

Thus, dataflow architectures (and Monsoon in particular) provide good support for exploiting parallel slackness fine grain threads, efficient multiplexing, cheap synchronization, and support for split transactions to mask inter-node latency.

However, present dataflow architectures do not have good single-thread performance. The fundamental problem is that present dataflow architectures do not provide adequate control over the scheduling of threads. In the pure dataflow model, successive tokens executed by the processor may refer to arbitrarily different frames and instructions. The consequence is that an instruction can transmit values to its successors only through slow memory--it cannot exploit any special high speed storage such as registers and caches. In conventional uniprocessors, caches allow fast transmission of values because the successor instruction is executed immediately, while a previously stored value is still in the cache. This locality through successor-scheduling is absent in pure dataflow models. Pure dataflow models allow exactly one value to be transmitted without going to memory--the value on the token.

Monsoon improves on this situation. In Monsoon, an instruction can annotate one of its successors so that it is executed directly, i.e., instead of placing the token back into the token queue, it is recirculated directly into the processor pipeline. Thus, in a chain of such direct successors, instructions can communicate values down the thread via high speed registers--no other thread can intervene to disturb the registers. However, Monsoon still has some engineering limitations that limit single-thread performance, namely, (a) very few registers (only three) and (b) the processor pipeline is eight cycles long, so that each instruction in a chain takes eight cycles.

In Monsoon, control over scheduling stops at this point. A chain of direct successors is broken when it reaches an instruction that is a split transaction instruction (like a load), or when it reaches an instruction that executes a join that fails. At this point, there is no further control on the next thread to be executed. If we had such control, we might, for example, choose another thread from the same frame, to maintain locality with respect to the current frame.

DISCLOSURE OF THE INVENTION

The present invention provides the fast single-thread execution of conventional micros, coupled with the facilities to exploit parallel slackness from dataflow architectures. In addition, we provide tight control over the scheduling of threads.

In accordance with one aspect of the present invention, a von Neumann data processor processes threads of computation, those threads including operations to generate messages for initiating new threads of computation. A synchronization coprocessor responds to the messages and indicates to the data processor when a new thread of computation maybe performed. The data processor subsequently initiates processing of the new thread of computation.

The messages may include a start message which comprises a pointer to an activation frame and a pointer to a synchronization coprocessor instruction in order to start a thread of computation. In a further application of the invention, the messages include object oriented messages which identify a method, an object and arguments. In that case, the synchronization coprocessor establishes a frame in which at least the arguments are stored and identifies that frame to the data processor. The synchronization processor may also locate an instruction pointer into the method and provide that to the data processor.

In a multiprocessor system comprising a plurality of processing nodes, each node processes multiple threads of computation. In a preferred addressing approach, each data processor operates on a local virtual address space, and each node has means for translating from the local virtual address space to a local physical address space. Further, each data processor generates a global virtual address to access an address in a remote node, and each node comprises means for translating the global virtual address to a node designation and a local virtual address of the remote node.

Each data processor sequentially processes threads of code. In the preferred system, the code includes local memory load and store instructions, start instructions which cause start messages to be sent with data values to start new threads of computation and remote memory load and store instructions which cause messages to be sent to remote memory locations to fetch or store data from or in remote memory locations. The synchronization coprocessor processes start messages to store values from the start messages as operands for threads of computation, to determine when all operands required for a thread of computation have been received and to provide an indication to the data processor that a thread of computation may be initiated.

A system using a conventional RISC data processor includes a message formatter. The message formatter is instructed by the data processor to create messages to remote nodes of the data processing system. The message formatter comprises registers on a common bus with the data processor in the address space of the data processor. The data processor instructs the message formatter to create messages by memory mapped stores to the message formatter registers. The data processor loads global virtual addresses along its data bus into registers in the message formatter. The number of bits in the global virtual address is greater than the number of bits available in the local virtual address space of the data processor. The message formatter translates the global virtual address to a node designation and a local virtual address on that node.

Preferably, the data processor and the synchronization coprocessor communicate with the common local memory in which operands are stored within activation frames by the synchronization coprocessor and fetched by the data processor. A cache memory is shared by the two processors. Further, the data processor is a single chip microprocessor which has a cache memory thereon.

The synchronization coprocessor may comprise a start processor for processing start messages and a remote memory processor for processing remote memory load and store instructions from remote nodes. A start message comprises a pointer to an activation frame and a pointer to a synchronization coprocessor instruction. The synchronization coprocessor also comprises a queue in which continuations are posted to serve as indications to the data processor that a thread of computation may be initiated. The continuation is comprised of a pointer to an activation frame and a pointer to a data processor instruction. Preferably, the continuations are presented by a frame registry according to priority to continue processing active frames in the data processor. A software list of continuations may be maintained where the capacity of the registry is exceeded. New threads of computation are initiated by the data processor by loading continuations from the queue.

The synchronization coprocessor is preferably a programmable processor with a processing pipeline. The processing pipeline includes counting hardware to test whether all operands per computational thread have been received The hardware may be increment and test hardware for incrementing (positively or negatively) a value fetched from cache memory, testing the value and returning the incremented value to cache memory. Other counting techniques such as unary encoding in a bit field may also be used.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing and other objects, features and advantages of the invention will be apparent from the following more particular description of preferred embodiments of the invention, as illustrated in the accompanying drawings in which like reference characters refer to the same parts throughout the different views. The drawings are not necessarily to scale, emphasis instead being placed upon illustrating the principles of the invention.

FIG. 1 is a schematic illustration of a single node of a multiprocessor embodying the present invention.

FIG. 2 illustrates the transmission of start messages between plural nodes of a data processing system.

FIG. 3 illustrates transmission of a remote load message to a remote node and return of a start message. FIG. 4 presents the code for performing the SAXPY routine.

FIG. 5 illustrates an improved version of the SAXPY code.

FIG. 6 is a more detailed illustration of the system of FIG. 1 employing a Motorola 88110 microprocessor.

FIG. 7 illustrates global and local address translation in accordance with the present invention.

FIG. 8 is a detailed illustration of the Start Processor of FIG. 6.

FIG. 9 is a detailed illustration of the increment and test logic of the Start Processor of FIG. 8.

FIG. 10 is a reservation table illustrating timing of operations within the pipeline of FIG. 8 relative to instructions in response to a start message .

DESCRIPTION OF A PREFERRED EMBODIMENT

In most languages, when a procedure is invoked,

a frame (also known as an activation record) must be allocated for it;

arguments (if any) must be deposited in its frame; and

execution of its code must be initiated.

When it terminates, it passes results to the frame of its continuation, and initiates computation there (usually, this is its caller). During execution, the frame is generally stored in registers.

In a parallel system, a procedure may invoke several other code blocks in parallel. Further, iterations of a loop may also be invoked in parallel and be distributed across the nodes of the machine. Where previously a loop ran in a single frame, we may now have to allocate separate frames for each iteration or group of iterations. In general, instead of a stack of frames, we now have a tree of frames. Because frames may now correspond both to the procedure invocations and to loop iterations, we prefer to use the term code block for the segment of code that is the unit of invocation.

We are going to use frames as the basis for locality. Frames may be distributed among the nodes of the parallel machine, but each frame must reside entirely within a single node. There is no such restriction on global data structures--a single object may span several nodes of the machine. For each frame in a node, the corresponding code block must also be present in that node. This means that if a code block is invoked in several nodes, copies of that code block must exist in all those nodes. A simple way to achieve this is to copy all code into all nodes, but code blocks could also be loaded dynamically on demand. The key point is that a particular invocation of a code block can always access its frame locations using local memory operations. Accessing locations in other frames or in global objects, however, may involve communication. This will be reflected in the instruction set of the processor in each node.

The *T (pronounced "start") model embodying the present invention for a node in a parallel machine is shown in FIG. 1. Although the memory of the machine is physically distributed amongst all the nodes, we assume a single global address space, i.e., the local memory in a node implements a piece of a single address space.

The Data Processor 22 is a superset of a conventional RISC processor, with a conventional repertoire of register-to-register instructions, and ability to manipulate local memory using conventional load and store instructions. Its program counter is called DIP ("Data processor Instruction Pointer"). One of its registers, called DFP, is assumed to contain a pointer to the "current frame" which is always in its local memory. Being a conventional RISC processor, the Data Processor 22 is optimized to run long, sequential threads efficiently. It obtains the starting points of these threads from a Start Processor 24 of a Synchronization Processor 26. On completion of a thread, if there is no new thread available from the Start Processor, the Data Processor simply waits until a thread becomes available. Clearly, for good utilization, this situation should be avoided.

In addition to its conventional RISC instructions, the Data Processor can execute a few additional "dataflow instructions" whose effect is to send messages into the network through a queue 27. These are non-blocking sends, i.e., the Data Processor continues executing after sending a message. The message can cause threads to be scheduled on the other nodes or on the same node, and a later response may deposit values in the sender's frame. As discussed below, by including a message formatter in the Synchronization Processor, the Data Processor can be a fully conventional RISC processor.

We will look at messages in more detail shortly, but for the moment it is enough to know that each message has the form:

msg.sub.-- op arg1, arg2, . . .

Arg1 is always a global address that identifies a unique destination node in the parallel machine. The message is automatically routed there. Of course, messages to the current node are short-circuited back directly. Broadly speaking, msg.sub.-- ops fall into two categories: "start" messages and "remote memory" messages. Start messages ultimately initiate processing of a thread by the data processor. Remote memory messages serve to write or fetch data into or from memory; fetched data is ultimately returned to the requesting node with a start message. For convenience, the two types of messages are handled by separate processors within the synchronization processor, but a single processor may be used. When a message arrives at a node, it is passed either to the Start Processor 24 through a queue 30 or to an RMem Processor 28 through a queue 34 based on the category of it msg.sub.-- op.

The Start Processor has a program counter called SIP ("Start processor Instruction Pointer"), two special registers SFP and SV and, perhaps, other general purpose registers. The Start Processor is triggered by the arrival of a start message from a queue. It simply waits if there is no start message available. When it picks up a start message, its SIP, SFP and SV registers are loaded with values from the message, after which it begins executing instructions from the address in SIP. It can read and write local memory 36 and it can post new thread identifying (FP, L.sub.D) pairs to a queue 32 to be picked up by the Data Processor in initiating new threads of computation. FP is a frame pointer and L.sub.D is a pointer to the block of code for the thread.

Because both the Start Processor and the Data Processor may execute instructions, we will distinguish labels for the two processors by the subscripts S and D, respectively.

The instruction set of the Data Processor is a proper superset of a conventional RISC instruction set, so we will assume the reader is familiar with conventional arithmetic-logic and comparison instructions, unconditional and conditional jumps, etc. We will focus here only on the novel, dataflow instructions that have to do with threads and synchronization. While reading the descriptions below, please refer to FIG. 2 for an overview of the thread-related instructions and messages.

A common situation where we wish to start a new thread is when one code block F calls another code block G. For example, we may wish to transport an argument from F's frame to G's frame and to initiate a thread in G that will compute with it. Similarly, we may wish to transport a result back from G's frame to F's frame and to initiate a thread in F to compute with it. In general, these frames may be on different nodes, so we need an explicit communication to perform these actions. For this, we use a start instruction, which has three register arguments:

    ______________________________________
    Data Processor Instruction: start rF, rI, rV
    Semantics:   Let FP = Register [rF]
                 Let L.sub.S = Register [rI]
                 Let V = Register [rV]
                 Send message: msg.sub.-- start FP, L.sub.S,
    ______________________________________
                 V

    ______________________________________
    Data Processor Instruction: fork rI
    Semantics:  Let L.sub.S = Register [rI]
                Let FP .fwdarw. Register [DFP]
                Send message: msg.sub.-- startv FP, L.sub.S,
    ______________________________________
                foo

    ______________________________________
    Date Processor Instruction: next
    Semantics:     A new frame pointer FP and
                   a new instruction pointer L.sub.D
                   are loaded from the Start
                   Processor into the Data
                   Processor into DFP and DIP
                   registers.
    ______________________________________

    ______________________________________
    Start Processor Instruction: store SFP[X], SV
    Semantics:     Let A = Register [SFP] + X
                   Memory[A] := Register[SV]
    ______________________________________

    ______________________________________
    Start Processor Instruction: post rF, rI
    Semantics:     Let FP = Register[rF]
                   Let L.sub.D = Register[rI]
                   Post (FP,L.sub.D) to be picked up
                   by the Data Processor
    ______________________________________

    ______________________________________
    Start Processor Instruction: next.sub.-- msg
    Semantics:     Reload SFP, SIP and SV from
                   the next incoming msg.sub.-- start
                   message
    ______________________________________

    ______________________________________
    L.sub.S :
      store SFP[X], SV
                   store incoming value into
                           frame offset X
      post SFP, L.sub.D
                   enable thread L.sub.D with this
                           frame in Data Processor
      next.sub.-- msg
                   done, handle next message
    ______________________________________

    ______________________________________
    L.sub.S
      store SFP[X1],SV
                 store incoming value into
                         frame offset X1
      load RO, SFP[C]
                 load counter from frame offset
                         C
      incr RO
                 increment i
      store RO,SFP[c]
                 store it back
      cmp RO,2,RB
                 compare counter value to 2
      jeq RB,N.sub.s
                 if equal, go to N.sub.S
      next.sub.-- msg
                 else die; handle next message
    M.sub.S
      store SFP[X1],SV
                 store incoming value into
                         frame offset X2
      load RO, SFP[C]
                 . . .
      incr RO
                 . . .
      store RO,SFP[c]
                 same as above
      cmp RO,2,RB
                 . . .
      jeq RB,N.sub.s
                 . . .
      next.sub.-- msg
                 . . .
    N.sub.S
      post SFP,L.sub.D
                 When both messages handled,
                         enable L.sub.D in Data Processor
      next.sub.-- msg
                 with this frame
    ______________________________________

    ______________________________________
    Date Processor Instruction: rload rA, rI
    Semantics:   Let A = Register[rA]
                 Let L.sub.S = Register[rI]
                 Let FP = Register[DFP]
                 Send message: msg.sub.-- rload A,FP,L.sub.S
    ______________________________________

    ______________________________________
    RMem Message: msg rload A, FP, L.sub.S
    Semantics:    Let V = Memory[A]
                  Send message: msg.sub.-- start FP, L.sub.S,
    ______________________________________
                  V

    ______________________________________
    Data Processor Instruction: rstore rA,rV,rI
    Semantics:    Let A = Register[rA]
                  Let V = Register[rV]
                  Let L.sub.S = Register[rI]
                  Let FP = Register[DFP]
                  Send message: rstore A,V,FP,L.sub.S
    ______________________________________

    ______________________________________
    RMem Message:
                 rstore A,V,FP,L.sub.S
    Semantics:   Memory[A]  :=V
                 Send message: msg.sub.-- start FP,L.sub.S,foo
    ______________________________________

    ______________________________________
    Data Processor Instruction: rIload rA, rI
    Semantics:  Let A = Register[rA]
                Let L.sub.S = Register[rI]
                Let FP = REgister[DFP]
                Send message: msg.sub.-- rIload A,FP,L.sub.S
    Date Processor Instruction: rIstore rA,rV,rI
    Semantics:  Let A = Register[rA]
                Let V = Register[rV]
                Let L.sub.S = Register[rI]
                Let FP = Register[DFP]
                Send message: msg.sub.-- rIstore A,V,FP,L.sub.S
    ______________________________________

    ______________________________________
    RMem Message: msg.sub.-- rIload A,FP,L.sub.S
    Semantics:    if full?(Memory[a])
                   Let V = Memory[A]
                   Send message: msg start, FP,L.sub.S,V
                  else
                   enqueue (FP,L.sub.S) at Memory[A]
    ______________________________________

    ______________________________________
    RMem Message:
                msg.sub.-- rIstore A,V,FP,L.sub.S
    Semantics:  if empty?(Memory[A])
                 Let queue = Memory[A]
                 Memory[A] :=V
                 For each (FP',M.sub.S) in queue
                  Send message: msg.sub.-- start FP', M.sub.S,V
                 Send message: msg.sub.-- start, FP,L.sub.S,foo
                else
                 error "Multiple writes not allowed"
    ______________________________________

    ______________________________________
    Data Processor Instruction: rtake rA,rI
    Semantics:   Let A = Register[rA]
                 Let L.sub.S = Register[rI]
                 Let FP = Register[DFP]
                 Send message: msg.sub.-- rtake A,FP,L.sub.S
    Data Processor Instruction: rput rA,rV,rI
    Semantics:   Let A = Register[rA]
                 Let V = Register[rV]
                 Let L.sub.S = Register[rI]
                 Let FP = Register[DFP]
                 Send message: msg.sub.-- rput A,V,FP,L.sub.S
    ______________________________________

    ______________________________________
    RMem Message: msg.sub.-- rtake A,FP,L.sub.S
    Semantics:    if full?(Memory[A])
                   Let V = Memory[A]
                   Send message: msg.sub.-- start FP,L.sub.S,V
                   Set presence bit of Memory[A] to
                    "empty"
                  else
                   enqueue (FP,L.sub.S) at Memory[A]
    ______________________________________

    ______________________________________
    RMem Message:
                msg.sub.-- rput A,V,FP,L.sub.S
    Semantics:   if empty?(Memory[a])
                  Let queue = Memory[A]
                  if queue is empty
                   Memory[A] :=V
                   Set presence bit of Heap[A] to
                   "full"
                 else
                  Let (FP',M.sub.S) = head(queue)
                  Send message: msg.sub.-- start FP',M.sub.S, V
                  Memory[A] := tail(queue)
                 Send message: msg.sub.-- start FP, L.sub.S,foo
                else
                 error "Multiple writes not allowed"
    ______________________________________

    ______________________________________
             for i = 1 to N do
               Y[i] = a * X[i] = Y[i]
    ______________________________________

    ______________________________________
                       . . .
    XP                 pointer to X[1]
    YP                 pointer to Y[1]
    A                  loop constant A
    YLim               pointer to Y[N]
                       . . .
    ______________________________________

    ______________________________________
          load DFP[XP], rXP
                        load ptr to X
                         load DFP[YP], rYP
                         load ptr to Y
                         load DFP[A], rA
                         load loop constant: a
                         load DFP[YLim], rYLim
                         load loop constant: Y
                           pointer limit
                        LOOP:
                         cmp rYLim, rYP, RB
                         compare ptr to Y with
                           limit
                         jgt rB, OUT
                         jump out of loop if
                           greater
                         load rXP, rXI
                         load C
                           X[i] into rXI (L1)
                         load rYP, rYI
                         load Y[i] into rYI (L2)
                         add 1, rXP, rXP
                         increment ptr to X
                         mult rA, rXI, r1
                         a*X[i]
                         add r1, rXI, r2
                         a*X[i] = Y[i]
                         jump LOOP
                        OUT:
                         . . . loop sequel . . .
    ______________________________________

    ______________________________________
                    . . .
    XP              pointer to X[1]
    YP              pointer to Y[1]
    A               loop constant A
    YLim            pointer to Y[N]
    XI              copy of X[I]
    YI              copy of Y[I]
    c1              join counter for rloads
    c2              join counter for rstores
                    . . .
    ______________________________________

    ______________________________________
             start DFP, L1s  Ls1: post SFP, L2d
                             next-msg
    L1d:
             . . . loop 1 . . .
             next
    L2d:
             . . . loop 2 . . .
             next
    OUT:
             . . . loop sequel . . .
    ______________________________________

    ______________________________________
    mOP        Message operation (rload, rstore, or start)
    mA         Destination address GVA or FP
    mI         Continuation start code displacement .delta.
    mV         Message value
    mDFP       Cached copy of DFP
    ______________________________________

    ______________________________________
    L --do --rload.d:
    st.d rA, rMF,  --mA
                      ;     address to load
                            into formatter reg
                            mA
    st rI, rMF,  --mI ;     start code disp.
                            into formatter reg
                            mI
    or rmsg,  --rload.d, rO
                      ;     formulate rload
                            command to fetch 64
                            bits
    st rmsg, rMF,  --mOP
                      ;     tell formatter to
                            launch rload
                            message
    ______________________________________

    ______________________________________
    SELECT    .delta.     msg --op 000
    8         16          5        3
    ______________________________________

    ______________________________________
    mA      .rarw.        double value written
    mI      .rarw.        .delta.
    mOP     .rarw.        msg --op
    ______________________________________

    ______________________________________
    L --do --rload.d:
    st.d rA, rSEL,         ;     initiate rload
    ( --delta << 8) .parallel. ( --rload.d << 3)
    ______________________________________

    ______________________________________
    A                 =     Register[mA]
    FP                =     Register[mDFP]
    .delta.           =     Register[mI]
    n.v               =     SegmentXlate(A)
    C                 =     (this --node.FP,.delta.)
    Send message:           msg --rload n.v,C
    ______________________________________

    ______________________________________
    L --do --rstore.d:
    st.d rV, rMF,  --mV    ;     value to store
    st.d rA, rSEL,         ;     initiate rstore
    ( --delta << 8) .parallel. ( --rstore.d << 3)
    ______________________________________

    ______________________________________
    V                =     Register[mV]
    A                =     Register[mA]
    FP               =     Register[mDFP]
    .delta.          =     Register[mI]
    n.v              =     SegmentXlate(A)
    Send message:          msg --rstore n.v,V,C
    ______________________________________

    ______________________________________
    L --do --start.d:
    st.d rV, rmF,  --mV   ;     value-part of
                                start message
    st.d rRC, rSEL,       ;     initiate start
    ( --adj << 8) .parallel. ( --start.d << 3)
    ______________________________________

    ______________________________________
    V                 =     Register[mV]
    adj               =     Register[mI]
    (n.v,.delta.)     =     Register[mA]
    .delta.           =     .delta. + adj
    C                 =     (n.v,.delta.)
    Send message            msg --start C,V
    ______________________________________

    ______________________________________
             Ex-         rload/rstore
           Size    ten-        Im-    I-      M-
    Operand
           (Bytes) sion   start
                               perative
                                      Structure
                                              Structure
    ______________________________________
    null   0       .n
    byte   1       .b
    halfword
           2       .h
    word/  4       .w/.s
    single
    double 8       .d
    quad-  16      .q
    word
    octword
           32      .o
    ______________________________________

    ______________________________________
    1d.d rDFP, rQ, O
                ;     pop FP, IP pair from head of queue
    jmp rDIP    ;     jump to the new thread
    ______________________________________

    ______________________________________
    Activation Frame Area
                     Start Proc. M88110
    ______________________________________
    Linkage - IP BASE
                     Read-Only   R/W
    Join Counters    R/W         Read-Only
    Message Values   Write       Read
    Inter-Thread Values          R/W
    ______________________________________

    ______________________________________
    SIP         Message handler instruction pointer
    SFP         Current activation frame base
    SV          Message value (MSW)
    SV1         Message value
    SV2         Message value
    SV3         Message value (LSW)
    ______________________________________

• Inventors
  Papadopoulos, Gregory M.; Nikhil, Rishiyur S.; Greiner, Robert J.;
• Assignee
  Massachusetts Institute of Technology (Cambridge, MA)
• Published
  Jul-4-1995
• Current US Classes:
  719/314
• Application #
  734252
• International Classes
  G06F 015/80
• Field of Search
  395/375 395/650 395/800 364/DIG.
• Examiner
  Harrell; Robert B.
• Agent
  Hamilton, Brook, Smith & Reynolds
• US Patent References:
  4481573
  4819155
  4858105
  4943908
  5050068
  5050070
  5226131
  5241635