In a refreshingly lucid fashion, the authors describe an elegant implementation of communication and message passing among multiple processors. A method is shown for message passing between any two of four clustered INMOS T800 transputers using a single shared memory and mounted on a single board, resulting in transfer times that are approximately 2.5 times faster than the conventional manufacturer-provided interprocessor links.

In this implementation, the size of the shared memory is 64K, in addition to the 2M private memory of each transputer. Access to the shared memory is via data buffers and address latches; given enough of these, the authors state the upper limit of the shared memory as 256M.

A single shared memory access takes 250 ns. Thus, four simultaneous accesses would take 4 x 250 ns or 1 &mgr;s to complete. Pipelining was thus introduced to enable pending requests to be processed every 100 ns after the first 250 ns. Thus, four simultaneous requests are processed in 550 ns as opposed to 1 &mgr;s. Finally, every access to shared memory is followed by an access to private memory to complete the transfer of the message.

One key to this method is the arbitration logic used to resolve contention for the shared memory. The authors establish a process whereby pending requests are prioritized and their priority is increased with the completion of a request. This process is reflected in hardware by a single programmable logic array (PLA) chip, a diagram for which is presented. The modus operandi guarantees that no request waits for more than the time required to process three other requests.

A second key is synchronization of the sending and receiving of messages. Each transputer has an associated event register and control logic. The shared memory is partitioned in a fixed manner. The authors explain in detail how the transfer takes place.

The shared memory is divided into 12 partitions. Each transputer has three distinct areas in which it can store messages to be passed to each of the three other transputers in the cluster. Hence, four transputers times three buffers each yields 12 partitions. Twelve unidirectional paths are also established, so any transputer can send and receive from any other transputer in the cluster, thus achieving true parallelism. Each unidirectional path between transputers via one of these buffers is termed a pseudolink. The partitioning scheme need not be fixed, and the hardware does not preclude the use of a software-controlled process by which each buffer could be dynamically allocated and sized.

In short, the process steps are as follows. For each access event, the initiating transputer writes the message into the designated shared memory partition for the transfer and causes an appropriate flag to be set on the receiving transputer’s event register. Latches are used for flags. The receiving transputer’s event channel is activated, reads its event register to determine the source of the event, clears the flag, reads the message from the shared memory, and sets the corresponding flag on the sending transputer’s event register to signal completion. Finally, the sending transputer event channel is activated, reads its event register and determines that the event has been completed, and clears the flag. The pseudolink is then ready for another event.

Although this paper is short--only five full pages of text and diagrams--seldom have I seen a more clearly written and illustrated paper on such a technically advanced topic.