Edition 1.1, September 17, 1996.

Edition 1.2, November 26, 1996 updated by K. Cablk.

Released to the public domain, 1996, by Thomas W. Christopher

Overview

AMDC (Active Message Driven Computing) is a successor to MDC90, Enhanced Actors, and MEMO-all systems designed and implemented at Illinois Institute of Technology.

In AMDC, computation occurs at abstract locations. Each abstract location has a name. The names are structured: Each name is composed of a "symbol" and several integers. This form of name has been found to allow all common data structures to be constructed. For example, a distributed array can be composed of locations whose names all contain the same symbol with integers indicating the indices.

A location contains an input queue and a table of messages. Locations are dynamic: they are only allocated space when needed: there is a message present in either the input queue or the table or there is a process attached to the location.

AMDC assumes a SPMD distributed-memory implementation: the computation is spread over a number of nodes (computers or processes) all running the same program and communicating with each other by passing messages.

On a distributed-memory machine, locations are distributed across the machine. The name of a location is hashed to give the number of the machine it is on. The locations assigned to a machine are kept in a hash table.

When an AMDC program runs, one or more processes are created, each at its own location. These processes execute their programs and can send messages to the others at their locations. Messages may also be sent to dynamic locations where the arriving messages execute procedures on their own.

A messages has several components:

• A script: a pointer to a procedure.
• A tag: a long integer to identify the purpose of the message. The messages within a table are looked-up by tag field.
• A body: a block of storage interpreted only by the AMDC programmer, not by the AMDC system.
• A table of messages attached to the message. (This was found to be quite useful in MDC90.)

Processing is parallel across processors, round-robin by location within a processor, and FIFO by input queue within a location.

To perform a step of computation, the system pulls the first message off the input queue at a location and executes its script. The script is a procedure which is passed pointers to the message and to the location. The script can create and send messages, store messages into and retrieve messages from tables, and perform the usual (arithmetic and logical) computations. The script is executed to completion before another step of computation on the same machine is dispatched.

The programming techniques available to AMDC programmers include distributed data structures, communicating processes, traveling processes, Wall's version of active messages, actors, itinerant actors, streams, dataflow, I-structures, closures, continuations, and graph-reduction.

Running programs

Compiling

You compile the package by the command

cc -Dsystem amd*.c

where system is a symbol that indicates your computer/operating system. If you omit system you will get a generic AMDC system that will not run parallel, but only with a single process.

(Currently there are no options for system. We'll get the parallel versions going real soon now....)

To compile your program with the system, use something like

cc amd*.o -llibrary -o yourprog

(The library library is required on some machines to link in parallel processing functions.)

Command line options on running

To run your program, use

yourprog amdc_parameters

or

yourprog amdc_parameters -! Your_parameters

The amdc_parameters are defined below:

-a

When each MESSAGE is being allocated or freed, print its message Id.

-m

When each MESSAGE is being sent or left, print its message Id and destination.

-M

Same as -m including contents of each message.

-t

When each MESSAGE is being sent or left, print the messages in its table with message Id and index.

-T

Same as -t including contents of each message.

-r

Before RUNNING each behavior, print the message Id executing.

-R

Same as -r including contents of each message.

-e

On EXIT print all locations remaining including messages Id's for each MsgType.

-E

Same as -e including contents of the messages.

-d file

Save debug printout in 'file'. Default 'mdcdebug.trc' for a single process.

-n #

Execute with # number of nodes.

-!

Stop parsing command line and pass all remaining argument to Main.

-h

Write out the HELP message. (This list.) Don't run the program.

Multiple flags for debugging may be set.

Currently implemented: -h -! -r -m

Procedure Main

Your program is written in C. Two things to remember:

1. Your main program must be named Main, not main. It is otherwise the same.
2. You must include a header file to give you access to the AMDC system:

	#include "amdc96.h"

Location names

A location name is composed of a symbol and an array of three unsigned long integers.

A location name is of data type LocName. Its definition is

#define NUM_X 3
typedef struct 
   {Symbol S; unsigned long X[NUM_X];} LocName;

Experience has shown that three long integers are usually enough without wasting too much space. If you wish to use a different number, redefine NUM_X.

Locations are distributed over the nodes (machines, processes) of a parallel computer in a manner controlled by the kind of symbol in the location's name.

There is a procedure to initialize a location name:

LocName amdc_initLocName0D(Symbol symbol);

returns a location name which contains the S field symbol and zeros in all the X fields.

Symbols

Symbols represent names of parallel/distributed data structures.

• You can create a unique new symbol whenever you wish using procedure amdc_newSymbol(kind).
• There are four kinds of symbols. The kind of symbol controls how locations with that symbol in their names are distributed over the nodes of the parallel computer.
• You can also create symbols at compile time using the macro AMDC_AbsoluteSymbol(I,K) where I is a small positive integer and K is a kind.

Symbol creation:

Symbol amdc_newSymbol(int kind);

allocate a new symbol at run time of kind kind.

AMDC_AbsoluteSymbol(I,K)

allocate a symbol at compile time. I is a small positive integer. K is a kind.

Kinds of symbols:

AMDC_SYMB_0

allocates locations on node 0. Don't use this unless, e.g., only node zero can access I/O.

AMDC_SYMB_X0

allocates locations on the node whose number is loc.X[0]%numberOfNodes.

AMDC_SYMB_HASH

allocates locations by hashing their names. Use this to spread computation statistically via the law of large numbers.

AMDC_SYMB_HERE

allocate the location on the same node that created the symbol.

Predefined symbols:

AMDC_NULL_SYMBOL

AMDC_AbsoluteSymbol(0,AMDC_SYMB_0): Used to represent null pointers.

AMDC_PROCESS_SYMBOL

AMDC_AbsoluteSymbol(0,AMDC_SYMB_X0): Used to name the locations to which the processes are attached.

AMDC_SymbolNode(S)

tells you the node that created the symbol.

AMDC_SymbolKind(S)

tells you the kind of the symbol.

Messages

Messages have a header and a body. The header is used by the system, the body is used by you.

When you have a pointer to a message, your pointer points to the body; you can cast that pointer to any pointer type you want and access the data in the message through it.

The header contains

• A script: a pointer to a procedure.
• A tag: a long integer to identify the purpose of the message. The messages within a table are looked-up by tag field.
• A location name.
• A table of messages attached to the message.

The data type of a message is Message.

Message creation and deletion

Message amdc_rawMsg(int leng);

creates a message with a body of length leng. The header is uninitialized except for (1) the script, which is set to a procedure amdc_rawScript (discussed below) which will put the message in the table of the location to which it is sent, and (2) the table which is set empty.

Message amdc_newMsg(Script script,Tag tag,int leng);

creates a new message with a body of length leng. The script is set to script, the tag is set to tag, the table is set empty, the location name is uninitialized.

Message copyMsg(Message msg);

creates a copy of the message msg, including the header and the body and with all the messages in its table copied into the table of the new message as well.

void freeMsg(Message msg);

deletes the message msg and all messages in its table.

Access to header

Tag amdc_getTag(Message msg);

returns the tag of message msg.

Message amdc_setTag(Message msg,Tag tag);

sets the tag of message msg to tag.

int amdc_getLeng(Message msg);

returns the length of message msg.

Script amdc_getScript(Message msg);

returns the script of message msg.

Message amdc_setScript(Message msg,Script script);

sets the script of message msg to script.

LocName amdc_getLocName(Message msg);

returns the location name of message msg.

Message amdc_setLocName(Message msg,LocName locName);

sets the location name of message msg to locName.

Destiny amdc_getDest(Message msg);

returns a Destiny structure for message msg, containing its tag, location name, and script.

Message amdc_setDest(Message msg,Destiny dest);

sets the tag, location name, and script for message msg from the contents of the Destiny structure dest.

Sending messages

All sends perform no operation if the message is NULL.

void amdc_sendMsg(Message msg);

send msg to the location named in its header.

void amdc_sendTo(Message msg,LocName locName);

send msg to the location named locName.

void amdc_sendToAs(Message msg,LocName locName,Tag tag);

set the tag of msg to tag and send it to the location named locName.

void amdc_sendToAsDo(Message msg,LocName locName,Tag tag,Script script);

set the tag of msg to tag, the script to script, and send it to the location named locName.

void amdc_sendToDest(Message msg,Destiny destiny);

sets the tag, location name, and script for message msg from the contents of the Destiny structure destiny and sends it.

Destiny

Yes, Destiny is an unusual name. The idea is rather simple. If you do a remote procedure call by sending a message, you need to indicate where the result is to be sent. But of course, the result message must also have a tag and execute a script when it arrives. A Destiny combines a location name, tag, and script, so you can specify all those in one place. The data type is:

typedef struct {	
LocName locName;	
Tag tag;	
Script script;
 } Destiny;

Why call it a Destiny? It says where message is going, what tag it will be known by, and what it will do, which comes pretty close to what we mean by destiny.

The operations on destinies are

void amdc_initDest(Destiny *dest,LocName loc,Tag tag,Script script);

initializes the destiny whose address is the first parameter.

Destiny amdc_getDest(Message msg);

returns a Destiny structure for message msg, containing its tag, location name, and script.

Message amdc_setDest(Message msg,Destiny dest);

sets the tag, location name, and script for message msg from the contents of the Destiny structure dest.

void amdc_sendToDest(Message msg,Destiny destiny);

sets the tag, location name, and script for message msg from the contents of the Destiny structure destiny and sends it.

Locations

A location has three components:

• A location name.
• A queue of incoming messages.
• A table of messages.

The AMDC system polls the locations to see if there is anything to do. If it finds a location with messages in its input queue, it will get the first message from the queue and execute the message's script, passing the script pointers to the message and the location.

Here are functions that operate on locations:

void amdc_putLoc(Location loc,Message msg);

put the message msg into the table at the location loc. The message will be associated with its tag field. More than one message with the same tag field may be put in the table: they are queued.

Message amdc_getLoc(Location loc,Tag tag);

removes and returns the first message from the table in loc which has the tag field tag. Returns NULL if there is no such message.

Message amdc_getArbLoc(Location loc);

removes and returns an arbitrary message from the table in loc. Returns NULL if there is no message in the table.

int amdc_numLoc(Location loc,Tag tag);

returns the count of messages in the table at loc which have the tag tag.

int amdc_presentLoc(Location loc,Tag tag);

returns true if there are any messages in the table at loc which have the tag tag.

Tag amdc_firstTagLoc(Location loc);

returns the first tag in ascending order of any message in the table at loc. Returns NO_MSG_TAG if the table is empty.

Tag amdc_nextTagLoc(Location loc,Tag prev);

returns the next tag in ascending order of any message in the table at loc following tag prev. Returns NO_MSG_TAG if there is no message with a higher tag than prev.

LocName amdc_getNameOfLoc(Location loc);

returns the name of the location.

void amdc_enqueueAtLoc(Location loc,Message msg);

puts the message msg in the input queue of location loc. It performs no operation if the message is NULL.

Scripts

A script is a pointer to a function that takes a message as its first parameter and a location as its second. The script is contained in a message and is executed when that message is dispatched at a location. The data structure is:

struct MessageStruct;

struct LocationStruct;

typedef void (*Script)(struct MessageStruct*,struct LocationStruct*);

Scripts must not block

Do not try to wait for a message within a script. It could result in a deadlock.

Scripts, written in C, have to run on a stack. All scripts run on the stack of the process that is running on their node. If a script is running, it is on top of the stack and the process beneath it cannot be running. Similarly, if AMDC were to poll the locations and dispatch a script at location R while one is still running at location Q, the script suspended at Q cannot continue executing. Moreover, since scripts have exclusive use of location while executing, no other script can execute at Q until both scripts terminate.

Consider the following sequence of events:

1. Script A is running at location Q on stack S.
2. A calls a polling routine.
3. Script B is dispatched at location R, also on stack S.
4. B sends a message M to Q and loops waiting for a reply.
5. Message M cannot execute its script since script A is holding on to the location. Script A cannot run to completion because script B is on top of it on the stack. Script B won't complete until message M runs its script. Deadlock.

Instead of waiting for a message, have the script leave a continuation message and terminate. A continuation message contains all the information that is needed to continue executing a procedure: the local variables, other data, and script. When the awaited message arrives, it must trigger the continuation message to resume execution.

Raw script

There is a built-in script that is placed in a message when it is created by amdc_rawMsg(). When executed, it will simply place the message in the table at the location.

void amdc_rawScript(Message m,Location loc)
{
	amdc_putLoc(loc,m);
}

Processes

When run with command line parameter -n num, an AMDC program will run with num processes, i.e. on num nodes.

• Each process runs the procedure Main().
• Each process will have its own number, p, in the range 0 through num-1.
• Each process will have its own location with name AMDC_PROCESS_SYMBOL[p,0,0].

Functions for processes:

Location amdc_getMyLoc(void);

gives process a pointer to its location.

int amdc_getMyId(void);

gives a process its own number.

int numNodes(void);

tells a process how many nodes are running.

void amdc_pollLocations(void);

allows the AMDC system to poll the locations on this node to run a few scripts.

void amdc_pollBlock(void);

like amdc_pollLocations, but if there are no locations with messages present, it will wait for more messages to arrive from other nodes. If all nodes are blocked and no messages are in transit, the program terminates.

Tables attached to messages

Tables of messages can be attached to messages. Their function is much like attachments on e-mail, memos, and letters: the cover message indicates how the attached messages are to be used. For example, a broadcast message may deliver a copy of an attached message to a set of locations.

void amdc_putMsg(Message tbl,Message msg);

put the message msg into the table at the message tbl. The message will be associated with its tag field. More than one message with the same tag field may be put in the table: they are queued.

Message amdc_getMsg(Message msg,Tag tag);

removes and returns the first message from the table in msg which has the tag field tag. Returns NULL if there is no such message.

Message amdc_getArbMsg(Message msg);

removes and returns an arbitrary message from the table in msg. Returns NULL if there is no message in the table.

int amdc_numMsg(Message msg,Tag tag);

returns the count of messages in the table at msg which have the tag tag.

int amdc_presentMsg(Message msg,Tag tag);

returns true if there are any messages in the table at msg which have the tag tag.

Tag amdc_firstTagMsg(Message msg);

returns the first tag in ascending order of any message in the table at msg. Returns NO_MSG_TAG if the table is empty.

Tag amdc_nextTagMsg(Message msg,Tag prev);

returns the next tag in ascending order of any message in the table at msg following tag prev. Returns NO_MSG_TAG if there is no message with a higher tag than prev.