Adl Project Abstract Machine

The AMAM abstract machine consists of a set of independent computational nodes, each of which maintains its own internal state and local memory, and executes code units or threads from a global system-wide program. The nodal state information includes details concerning:

which elements of each global aggregate are stored locally [f1],
which threads have been activated on the local node,
which one of those activations presently has control of the node,
which of those thread activations are presently blocked awaiting (tagged) values from another thread, and
which (tagged) values are currently buffered awaiting receipt by a local thread activation.

The model executes threads according to a simple paradigm of non-preemptive nodal multi-threading. The thread activation, t, currently executing on a given node proceeds through the following phases:

The activation t sequentially executes instructions until such time as it voluntarily relinquishes control. During this (thread-defined) quantum, instructions may be executed which cause any number of the following events:
- a new activation of a program thread to be entered into the local pool of thread activations,
- a new activation of a program thread to be entered into another node's pool of thread activations by means of asynchronous communication [f2], in the style of Active Messages
- a (tagged) value to be entered into the local result pool,
- a (tagged) value to be entered into the another node's result pool by means of asynchronous communication in the style of Active Messages
At some time, the activation t will give up control of the node. This can occur in one of two ways:
- the activation issues the terminate command, in which case it is simply removed from the system and the node becomes idle, or
- the activation issues the suspend x command, in which case the node becomes idle but the activation remains in the system, tagged as being unexecutable until such time as the given data item (x) is present in the local result pool
When the node has become idle, a system scheduler searches the current local pool of activations to determine which should next be executed. The search strategy involves two distinct operations:
- the determination of which suspended activations are now executable on account of their requested data now being present in the local result pool. This analysis is called key matching
- the manipulation of the activation pool required to quickly find the first executable activation. This process is termed pool rotation
Once an executable activation is chosen from the local pool, control (and any awaited data item) is immediately passed to it, and it is permitted to execute as per step 1.

Instrumentation

During the execution of a thread program under the AMAM machine, certain events are recorded for later analysis. In the present implementation these fall into two classes: communications events and mode-change events. Communication events occur whenever a node sends or receives a message, whether it be a data-communication (i.e., the insertion of a tagged value into a remote node's result pool) or remote-activation (i.e., the insertion of a new activation into a remote node's activation pool). Each event generates a time-stamped log entry which records the identity of the node on which it occurred, the size of the message sent or received, and an identifier used to uniquely identify the message's content. This information, once collected and collated post-run forms the basis for the visualization and analysis of communication patterns and volume. Mode-change events are related to a model of nodal utilization of the AMAM machine. At every point in time, each node is considered to be conceptually engaged in one of five modes:

executing code from a user thread
interpreting a message received behind-the-scenes
matching keys to determine which activation to execute next
rotating the task pool to find the next executable activation
implementing the logic of the scheduling loop

Each time a node transfers from one of these modes to another, an event is written to the log recording the node's identity and the new mode it is entering. Post-run analysis of this information allows accurate plots and measures of node utilization. For the most part, the tracing carried out within the AMAM system has only slight perturbations on system performance. The network hardware of the CM-5 incorporates a high resolution timer for each node which we read directly to obtain our time stamps. The very low cost of this timer read (essentially a single read from a memory-mapped hardware register) makes problems of nodal clock drift relatively insignificant. To further eliminate intrusiveness on the part of the logging system, all time-stamped traces are buffered in efficient static data-structures.

Footnotes

A novel aspect of the model is its support for arbitrary partitioning of data aggregates. Each aggregate has an associated partitioning function which describes its division amongst nodes of the machine. This abstraction allows the expression of parallel operators (possibly involving communication) in a fashion that is independent of partitioning choices.
During the execution of an activation, values may be received asynchronously from other nodes of the machine. Such receipt occurs behind-the-scenes, invisible to the executing activation. Such communication can be thought of, in an abstract sense, as seamless modification of a remote state.