The declaration of an entity is syntactically similar to that of a C function; the key difference is that unlike a function, an entity does not return a value. An entity type consists of a heading that declares the name and formal parameters of the entity type and a body that declares local variables and the message types that may be received by the entity type and defines its actions. For instance, the entity type declared in Figure 1 describes an object that models a resource manager. This entity type will be used as a running example to illustrate various Maisie constructs. The heading in lines 1 and 2 of the figure indicates that the entity type is called Manager and has one integer parameter called num_resources. The body of the entity is contained within curly braces in lines 3--16. The body is a compound C statement that may include message declarations (described in the next section) together with standard C declarations. The body may also include constructs to send and receive messages as described subseqeuntly.
An entity is created by the execution of a new statement and is automatically assigned a unique id on creation. Maisie defines a type called ename which is used to store entity-identifiers. The following statement will create an instance of entity type Manager and store its identifier in variable manager, which must be declared to be of type ename.
manager = new Manager{10};An entity can internally refer to its id using the keyword self. An entity instance terminates itself by `falling off the end'. (In the current implementation of the parallel runtime system, the user must explicitly terminate the program with a call to terminate().)
1 entity Manager {num_resources}
2 int num_resources;
3 {
4 int resources = num_resources;
5 message Request {ename requester;};
6 message Release;
7 for (;;)
8 wait until {
9 mtype(Request) st (resources > 0) {
10 resources--;
11 invoke msg.Request.requester with Resource;
12 }
13 or mtype(Release)
14 resources++;
15 }
16 }
|
invoke destination with message_type;where destination is a variable of type ename and message_type is a message whose type has been declared by the destination entity destination. For instance, execution of the invoke statement in line 11 of the Manager will deposit a message of type Resource in the message buffer of the entity identified by requester. Message type declarations are necessary only within the entity type of the destination entity (although for software engineering reasons, message types should be declared in a common header file).
wait until {
mtype(m_1) [st b_1] statement_1;
or mtype(m_2) [st b_2] statement_2;
.
.
.
or mtype(m_n) [st b_n] statement_n};
where m_i is a message-type, b_i an optional boolean
expression referred to as a guard, and statement_i
is any C or Maisie statement. The guard is a side-effect free boolean
expression that may refer to local variables or message parameters.
If omitted, the guard is assumed to be the constant true.
The message-type and guard are together referred to as a resume
condition and the resume condition together with the statement is
refered to as a resume statement. A resume condition with
message-type m_i and guard b_i is said to be
enabled if the message buffer contains a message of type
m_i, which if delivered to the entity would cause b_i to
evaluate to true; the corresponding message is called an
enabling message. A resume condition that is not enabled is
said to be disabled.
For instance, the wait statement in line 8 of the Manager entity consists of two resume statements. The resume condition (line 9) in the first statement ensures that the entity accepts a Request message only if enough resources are available (resources > 0). If so, the resource is allocated to the requesting entity (line 10-11). Keyword msg is used to refer to the last message that was removed from its buffer and delivered to the entity. The second resume statement (line 13) accepts a Release message and simply increments the count of available resources. As discussed subsequently, the resume condition in a wait statement may include multiple message-types, each with its own boolean expression. This allows many complex enabling conditions to be expressed directly, without requiring the programmer to describe the buffering explicitly.
If two or more resume conditions in a wait statement are enabled, then, in general, the enabling message which arrived first will be chosen. If the two messages arrived from the same source, then they will arrive in the same order they were sent. Otherwise, no assumption can be made about the order of arrival. By default, if all resume conditions in the wait statement are disabled, the corresponding entity is suspended until it receives an enabling message. A timeout mechanism is also supported as described in the following section.
1 entity Job{manager}
2 ename manager;
3 {
4 message Resource;
5 for (;;) {
6 hold(processing_time);
7 invoke manager with Request{self};
8 wait until
9 mtype(Resource) {
10 /* use the Resource */
11 invoke manager with Release;
12 }
13 }
14 }
|
wait 0 until {
mtype(m_1) [st b_1] statement_1;
...
or mtype (timeout) {
... }
}
If no enabling message is available at the time of this statement's execution, the entity will receive a timeout message. A non-blocking wait statement must contain a resume statement that specifies the action to be executed by the entity on receipt of a timeout message.
#include "maisie.h"
#define N 50000 /* N is the number of rounds */
#define B 1000 /* B is the message size, in bytes */
#define First 1 /* The first player prints the results */
#define Second 0 /* The second player doesn't */
/*---------------------------------------------------
* Driver entity
*-------------------------------------------------*/
entity driver {}
{
ename Jack, Jill;
Jack = new Player{First};
Jill = new Player{Second};
/* Send opponent's name to each entity */
invoke Jack with Opponent{Jill};
invoke Jill with Opponent{Jack};
/* Start the game. */
invoke Jack with Ball{'0'};
}
/*---------------------------------------------------
* Player entity
*-------------------------------------------------*/
entity Player {i_am_first}
int i_am_first;
{
int trips;
ename opponent;
message Opponent {ename name;} opp;
message Ball {char size[B];} ball;
/* Wait to receive opponent's name. */
wait until mtype (Opponent)
opponent = msg.Opponent.name;
/* Wait for the ball, and then hit it back to opponent. */
for (trips = 1; trips < N; trips++)
wait until mtype(Ball)
invoke opponent with Ball{'0'};
/* Game over */
if (i_am_first) {
printf("Game over after %d rounds and %d byte ball size!", N, B);
wait until mtype(Ball)
terminate();
}
}
|
1 #include "maisie.h" /* formerly mayc.h */
2
3 entity Sieve{myno}
4 int myno;
5 {
6 message Number {int number;} number;
7 ename next_sieve;
8 int myprime;
9
10 wait until mtype(Number)
11 myprime = msg.Number.number;
12
13 printf("Sieve number %d is for prime number %d\n", myno, myprime);
14
15 next_sieve = new Sieve{myno + 1};
16
17 for (;;)
18 wait until mtype(Number)
19 if(msg.Number.number % myprime)
20 invoke next_sieve with Number = msg.Number;
21 }
22
23 entity driver{}
24 {
25 int i;
26 ename first;
27 first = new Sieve{1};
28 for (i = 2 ; i <= 1000; ++i)
29 invoke first with Number{i};
30 }
|
The sequential program may be refined for a parallel implementation simply by modifying the new statements to create subsequent sieve entities on remote nodes. Assuming that the parallel implementation will be executed on N nodes, each entity creates the next sieve entity on a neighboring node. Required modifications to the preceding program are indicated in Figure 5. The parallel version may also be compiled and executed on a sequential architecture.
15 next_sieve = new Sieve{myno + 1} at (myno + 1);
...
27 first = new Sieve{1} at 1;
|
The sequential Floyd-Warshall algorithm works as follows:
for k = 0 to SIZE - 1
for i = 0 to SIZE - 1
for j = 0 to SIZE - 1
Graph[i][j] = min(Graph[i][j], Graph[i][k] + Graph[k][j]);
with additional checks for non-existent edges.
The parallel version (source code), assigns each row of the Graph matrix to an entity. At the kth iteration, the row-k entity broadcasts its row to all the other row entities and each row executes the j loop shown above.
message Request {ename requester; int count; };
.
.
.
wait until {
mtype(Request) st (msg.Request.count <= resources)
.
.
.
Maisie also provides a number of pre-defined functions that may be used by an entity to inspect its message buffer. For instance, the function qsize(m_t) returns the number of messages of type m_t in the buffer. A special form of this function called qempty(m_t) is defined, which returns true if the buffer does not contain any messages of type m_t, and returns false otherwise. This function may be used to impose priorities on incoming messages. Assume that the manager is to be modified such that a request message is accepted only if no Release messages are present in the buffer. A simple way to do this is to strengthen the guard for the Request message as follows:
wait until {
mtype(Request) st (qempty(Release) && (msg.Request.count <= resources))
The following example (taken from the Maisie User's Manual) illustrates simple wait statements with a single resume statement. The resume condition in the first wait statement is enabled if the message-buffer contains a req message. The resume condition in the second wait statement is enabled only if the buffer contains a req message whose parameter units is not greater than the entity variable units. Note, since the value of the mvar oldreq is not modified until an enabling message is received, msg must be used in the guard to reference the message being inspected. The last example causes req messages to be sorted and received in increasing order of the message parameter units.
wait until mtype (req); wait until oldreq = mtype (req) st (msg.req.units <= units); /* First-Fit */ wait until oldreq = mtype (req) min units st (msg.req.units <= units); /* Least-Fit */
wait until
mvara = mtype (ma) [max va] [st ba]
and mvarb = mtype (mb) [max vb] [st bb]
and mvarn = mtype (mn) [max vn] [st bn]
{
statement;
}
The Ping Pong program was written by Monnica Terwilliger.
The All Pairs Shortest Path program was written by Mike Patterson and modified by Richard Meyer to conform to the style of the document.