|
Message Driven Computing and Its Relationship to ACTORS |
|
We define Message Driven Computation as a style of computing with two characteristics:
1) Messages, not sequential processes, convey both control and data. Indeed, there
are no sequential processes unless they are programmed explicitly in terms of messages.
2) Computation is invoked by the presence of a collection of messages at the same location. We have embodied MDC in two languages, extensions of Icon and of C. MDC is designed to be coherent with the global structure of multicomputers and hence forms a basis for general purpose multicomputing. MDC may also be viewed as a generalization of Actors [AGHA86]. Our development of Message Driven Computation has three main goals: 1) to be coherent with the structure of multicomputers, 2) to be efficient, 3) to be useful for general purpose computation. Here we introduce the features of Message Driven Computation and relate them to the features of multicomputers, to Actors, to other parallel programming systems, and to our goals. It should be understood from the outset that our current version of MDC is nearly at the assembly language level. It is not much easier to use than any other low level language. We base the design of MDC on the structure of multicomputers. Consider the differences between von Neumann computers and multicomputers at their global level. |
|||||||||||
| 3.1 | Von Neumann vs. Multicomputer | ||||||||||
| In a von Neumann computer, processors and memories are separate and connected
through a switch, which forms a bottleneck. In a multicomputer, processors and memories
are combined at nodes, which are interconnected, in most designs, without bottlenecks. In a von Neumann computer, memory locations are small. In a multicomputer, the node memories are large and can store large, structured objects. In a von Neumann computer, addressing logic is simple and memory locations are addressed by integer. In a multicomputer, node memories are not directly addressable from outside, and accesses to non-local data must use the processor of the node on which the data resides. Since a full processor will be used anyway, creation of some form of an associative memory is trivial. In a von Neumann computer, a process contains data in its local memory and executes instructions to control the transformation of the data. In a multicomputer, messages carry data between the nodes and the arrival of messages trigger the execution of instructions and the transformation of data. We hypothesize that messages in a multicomputer are the equivalent of processes on a von Neumann computer.
Considering the global structure of multicomputers, we have designed MDC with the
following features: |
| *. | The name behavior we take from Actors. We will compare our work to Actors below. | ||||||||||||||
| *. | internally generated unique values | ||||||||||||||
| 3.2 | Relationship to Actors | ||||||||||||||
| We were inspired in our design of MDC by Actors. An actor is, in effect, a message queue with a procedure and an actual parameter list attached (the parameterized procedure is called a "behavior"). When one or more messages (called "tasks") are in the queue, the procedure is called with the parameter list and with the first message, which is removed. The procedure can create new actors, send messages, and can replace the procedure and parameter list attached to its message queue. Actors are easily translated into MDC as follows. The Actors construct given on the left may be implemented by the corresponding MDC construct on the right.
To implement an actor system in MDC, associate the loci with the mailboxes. Partition
the portals into those associated with behaviors and those associated with tasks. Require
that there be precisely one message at a "behavior" portal of a locus, while there may be
many at a task portal. Restrict the MDC behavior definitions to specify precisely two
messages in their patterns: one at a behavior portal and one at the task portal.
Features where we differ are:
|
|||||||||||||||
| 3.3 | Relationship to other parallel processing languages: | ||||||||||||||
| What particularly makes us believe in the generality of our approach is the ease with which we can encode other programming languages in MDC. Both code-copying and tagged-token implementations of dataflow [VEEN86][ACKE82][ARVI82] are trivially encoded in MDC (a one-for-one translation). We are also running an FP [BACK78][BURT87] interpreter in MDC and have a demand-driven interpreter for an applicative system providing static scoping and lazy evaluation via demand-driven graph copying and graph reduction [TREL82a]. Conventional sequential process languages, e.g. Pascal, are a bit messy to translate into MDC, but no more difficult than compiling them at all. (Lower-level sequential languages, such as C, which assume a linear address space and encourage pointer arithmetic, would be very difficult to translate efficiently.) | |||||||||||||||
| 3.4 | Concluding Remarks | ||||||||||||||
| Message Driven Computation, derived in part from the parallel object oriented language Actors, provides a more general computational style than strict object orientation, but does include object oriented programming as a special case. Message Driven Computation can also support control-flow, data-flow, and demand-driven computational models. We consider Message Driven Computation to be an excellent foundation on which to build parallel programming software. | |||||||||||||||
| 3.5 | References | ||||||||||||||
|
