Actor model implementation
Encyclopedia
In computer science
, Actor model implementation concerns implementation issues for the Actor model
.
most other parallel processors is that this multiple instruction
multiple-data machine uses message passing
instead of shared variables for communication between
concurrent processes. This computational model is reflected
in the hardware structure and operating system,
and is also the explicit message passing communication seen by the programmer. According to Seitz [1985]:
was developed by Bill Dally et al. at MIT providing architectural support suitable for Actors.
This included the following:
Concurrent Smalltalk (which can be modeled using Actors
) was developed to program the J Machine.
Messages are expressed in XML using the notation
The semantics of the programming language are defined by defining each program construct as an Actor with its own behavior. Execution is modeled by having Eval messages passed among program constructs during execution.
When Request[Bind[identifier value] customer] is received by an Actor Environment, a new environment Actor is created such that
when the new environment Actor receives
Request[Lookup[identifier’] customer’] then if identifier is the same as identifier’ send customer’ Returned[value], else send Environment
Request[Lookup[identifier’] customer’].
The above builds on an Actor EmptyEnvironment which
when it receives Request[Lookup[identifier] customer], sends customer Thrown[NotFound[identifier] ].
When it receives a Bind request EmptyEnvironment acts like Environment above.
<identifier>
When Request[Eval[environment] customer] is received, send environment Request[Lookup[<identifier>] customer]
send <recipient> <communication>
When Request[Eval[environment] customer] is received, send <recipient> Request[Eval[environment] evalCustomer1] where evalCustomer1 is a new Actor such that
when evalCustomer1 receives the communication Returned[theRecipient], then send <communication>
Request[Eval[environment] evalCustomer2] where evalCustomer2 is a new actor such that
when evalCustomer2 receives the communication Returned[theCommunication], then send theRecipient theCommunication.
<recipient>.<message>
When Request[Eval[environment] customer] is received, send <recipient> Request[Eval[environment] evalCustomer1] such that
when evalCustomer1 receives the communication Returned[theRecipient], then send <message> Request[Eval[environment] evalCustomer1] such that
when evalCustomer2 receives the communication Returned[theMessage], then send theRecipient
Request[theMessage customer]
receiver … <pattern>i <expression>i …
When Request[Eval[environment] customer] is received, send customer a new actor theReceiver such that
when theReceiver receives a communication com, then create a new bindingCustomer and send environment
Request[Bind[<pattern>i com] bindingCustomer] and
behavior … <pattern>i <expression>i …
When Request[Eval[environment] customer] is received, send customer a new actor theReceiver such that
when theReceiver receives Request[message customer’], then create a new bindingCustomer and send environment
Request[bind[<pattern>i message] customer’] and
{<expression>1, <expression>2}
When Request[Eval[environment] customer] is received, send <expression>1 Request[Eval[environment] ] and concurrently send <expression>2 Request[Eval[environment] ] customer].
let <identifier> = <expression>value in <expression>body
When message[Eval[environment] customer] is received, then create a new evalCustomer and send <expression>value
Request[Eval[environment] evalCustomer1.
When evalCustomer receives Returned[theValue], create a new bindingCustomer and send environment
Request[bind[<identifier> theValue] bindingCustomer]
When bindingCustomer receives Returned[environment’], send <expression>body Request[Eval[environment’] customer]
serializer <expression>
When Request[Eval[environment] customer] is received, then send customer Returned[theSerializer] where theSerializer is a new actor such that communications sent to theSerializer are processed in FIFO order with a behavior Actor that is initially <expression>.Eval[environment] and
When communication com is received by theSerializer, then send the behavior Actor Request[com customer’] where customer’ is a new actor such that
when customer’ receives Returned[theNextBehavior] then theNextBehavior is used as the behavior Actor for the next communication received by theSerializer.
Cell ≡
The above program which creates a storage cell makes use of the behavior ReadWrite which is defined as follows:
ReadWrite(contents) ≡
Note that the above behavior is pipelined, i.e., the behavior might still be processing a previous read or write message while it is processing a subsequent read or write message..
For example the following expression creates a cell x with initial contents 5 and then concurrently writes to it with the values 7 and 9.
let x = Cell.Create[5] in {x.write[7], x.write[9], x.read[]}
The value of the above expression is 5, 7 or 9.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, Actor model implementation concerns implementation issues for the Actor model
Actor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
.
Cosmic Cube
The Cosmic Cube was developed by Chuck Seitz et al. at Caltech providing architectural support for Actor systems. A significant difference between the Cosmic Cube andmost other parallel processors is that this multiple instruction
multiple-data machine uses message passing
instead of shared variables for communication between
concurrent processes. This computational model is reflected
in the hardware structure and operating system,
and is also the explicit message passing communication seen by the programmer. According to Seitz [1985]:
- It was a premise of the Cosmic Cube experiment that the internode communication should scale well to very large numbers of nodes. A direct network like the hypercube satisfies this requirement, with respect to both the aggregate bandwidth achieved across the many concurrent communication channels and the feasibility of the implementation. The hypercubeHypercubeIn geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...
is actually a distributed variant of an indirect logarithmic switching network like the Omega or banyanBanyan switchIn electronics, a banyan switch is a complex crossover switch used in electrical or optical switches.It is named for its resemblance to the roots of the banyan tree which cross over in complex patterns. Logical banyan switches are used in logic or signal pathways to crossover switching of signals...
networks: the kind that might be used in shared-storage organizations. With the hypercube, however, communication paths traverse different numbers of channels and so exhibit different latencies. It is possible, therefore, to take advantage of communication locality in placing processes in nodes.
J–Machine
The J–MachineJ–Machine
The J–Machine is a parallel computer designed by the MIT Concurrent VLSI Architecture group in conjunction with the Intel Corporation...
was developed by Bill Dally et al. at MIT providing architectural support suitable for Actors.
This included the following:
- Asynchronous messaging
- A uniform space of Actor addresses to which messages could be sent concurrently regardless of whether the recipient Actor was local or nonlocal
- A form of Actor pipelining (see Actor modelActor modelIn computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
)
Concurrent Smalltalk (which can be modeled using Actors
Actor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
) was developed to program the J Machine.
Prototype Actor Programming Language
Hewitt [2006] presented a prototype Actor programming language in the sense that it directly expresses important aspects of the behavior of Actors.Messages are expressed in XML using the notation
- <tag>[<element>1 … <element>] for
- “<”<tag>“>” <element>1 … <element>n “<”/<tag>“>”
The semantics of the programming language are defined by defining each program construct as an Actor with its own behavior. Execution is modeled by having Eval messages passed among program constructs during execution.
Environment Actors
Each Eval message has the address of an Actor that acts as an environment with the bindings of program identifiers. Environment Actors are immutable, i.e., they do not change.When Request[Bind[identifier value] customer] is received by an Actor Environment, a new environment Actor is created such that
when the new environment Actor receives
Request[Lookup[identifier’] customer’] then if identifier is the same as identifier’ send customer’ Returned[value], else send Environment
Request[Lookup[identifier’] customer’].
The above builds on an Actor EmptyEnvironment which
when it receives Request[Lookup[identifier] customer], sends customer Thrown[NotFound[identifier] ].
When it receives a Bind request EmptyEnvironment acts like Environment above.
Expressions
The prototype programming language has expressions of the following kinds:<identifier>
When Request[Eval[environment] customer] is received, send environment Request[Lookup[<identifier>] customer]
send <recipient> <communication>
When Request[Eval[environment] customer] is received, send <recipient> Request[Eval[environment] evalCustomer1] where evalCustomer1 is a new Actor such that
when evalCustomer1 receives the communication Returned[theRecipient], then send <communication>
Request[Eval[environment] evalCustomer2] where evalCustomer2 is a new actor such that
when evalCustomer2 receives the communication Returned[theCommunication], then send theRecipient theCommunication.
<recipient>.<message>
When Request[Eval[environment] customer] is received, send <recipient> Request[Eval[environment] evalCustomer1] such that
when evalCustomer1 receives the communication Returned[theRecipient], then send <message> Request[Eval[environment] evalCustomer1] such that
when evalCustomer2 receives the communication Returned[theMessage], then send theRecipient
Request[theMessage customer]
receiver … <pattern>i <expression>i …
When Request[Eval[environment] customer] is received, send customer a new actor theReceiver such that
when theReceiver receives a communication com, then create a new bindingCustomer and send environment
Request[Bind[<pattern>i com] bindingCustomer] and
- 1 if bindingCustomer receives Returned[environment’]. send <expression>i
- Request[Eval[environment’] ]
- 2 otherwise if bindingCustomer receives Thrown[…],.try <pattern>i+1
behavior … <pattern>i <expression>i …
When Request[Eval[environment] customer] is received, send customer a new actor theReceiver such that
when theReceiver receives Request[message customer’], then create a new bindingCustomer and send environment
Request[bind[<pattern>i message] customer’] and
- 1 if bindingCustomer receives Returned[environment’], send <expression>i
- Request[Eval[environment’] customer’]
- 2 otherwise if bindingCustomer receives Thrown[…],.try <pattern>i+1
{<expression>1, <expression>2}
When Request[Eval[environment] customer] is received, send <expression>1 Request[Eval[environment] ] and concurrently send <expression>2 Request[Eval[environment] ] customer].
let <identifier> = <expression>value in <expression>body
When message[Eval[environment] customer] is received, then create a new evalCustomer and send <expression>value
Request[Eval[environment] evalCustomer1.
When evalCustomer receives Returned[theValue], create a new bindingCustomer and send environment
Request[bind[<identifier> theValue] bindingCustomer]
When bindingCustomer receives Returned[environment’], send <expression>body Request[Eval[environment’] customer]
serializer <expression>
When Request[Eval[environment] customer] is received, then send customer Returned[theSerializer] where theSerializer is a new actor such that communications sent to theSerializer are processed in FIFO order with a behavior Actor that is initially <expression>.Eval[environment] and
When communication com is received by theSerializer, then send the behavior Actor Request[com customer’] where customer’ is a new actor such that
when customer’ receives Returned[theNextBehavior] then theNextBehavior is used as the behavior Actor for the next communication received by theSerializer.
Example program
An example program for a simple storage cell that can contain any Actor address is as follows:Cell ≡
- receiver
- Request[Create[initial] customer]
- send customer Returned[serializer ReadWrite(initial)]
- Request[Create[initial] customer]
The above program which creates a storage cell makes use of the behavior ReadWrite which is defined as follows:
ReadWrite(contents) ≡
- behavior
- Request[read[] customer]
- {send customer Returned[contents], ReadWrite(contents)}
- Request[write[x] customer]
- {send customer Returned[], ReadWrite(x)}
- Request[read[] customer]
Note that the above behavior is pipelined, i.e., the behavior might still be processing a previous read or write message while it is processing a subsequent read or write message..
For example the following expression creates a cell x with initial contents 5 and then concurrently writes to it with the values 7 and 9.
let x = Cell.Create[5] in {x.write[7], x.write[9], x.read[]}
The value of the above expression is 5, 7 or 9.
See also
- Actor model and process calculiActor model and process calculiIn computer science, the Actor model and process calculi are two closely related approaches to the modelling of concurrent digital computation...
- Actor model theoryActor model theoryIn theoretical computer science, Actor model theory concerns theoretical issues for the Actor model.Actors are the primitives that form the basis of the Actor model of concurrent digital computation. In response to a message that it receives, an Actor can make local decisions, create more Actors,...
- Forth