Implementation of a General Purpose Data Flow Multiprocessor: (Research Monographs in Parallel & Distributed Computing)

General purpose multiprocessors have largely failed to meet expectations for programmability and performance. The author blames the lack of usable parallel programming languages and systems on the underlying processor architecture. Machines built out of conventional sequential processors simply do not support the synchronization demands of parallel execution so the programmer focuses upon the dangerous and arduous task of discovering a minimum set of sychronization points without introducing nondeterminisim. He argues that processors must be fundamentally changed to execute a parallel machine language, in which parallel activities are coordinated as efficiently as instructions are scheduled. Dataflow architectures address this challenge by radically reformulating the basic specification of a machine program. These machines directly execute dataflow graphs, which specify only the essential prerequisites for the execution of an instruction - the availability of operands. Unfortunately, dataflow machines, including the MIT Tagged Token Dataflow Architecture (TTDA), have laboured under a number of implementation burdens, notably the apparent need for a fully associative operand matching store which discovers when instructions are able to execute. This work introduces and develops a novel dataflow architecture, the Explicit Token Store (ETS), which directly executes tagged-token dataflow graphs while correcting a number of inherent inefficiencies of previous dataflow machines. In the ETS model, operand matching is performed at compiler-designated offsets within an activation frame. It shows that the ETS is compatible with the TTDA by giving translations from TTDA machine graphs to ETS machine graphs. Finally, this work describes an implementation of an ETS dataflow multiprocessor, called Monsoon, now under construction.

Table of Contents:
Part 1 General purpose multiprocessing: why fine grain synchronization - tasks should be cheap, a virtual memory analogy, an informal task model of parallel computation, parallelism and synchronization, the costs of task state transitions, dataflow machines directly execute a "Reduced" task graph, related work; roadmap. Part 2 The tagged-token dataflow architecture: a TTDA primer - a simple example, tages distinguish tokens from different activations; tag efficiency - recycling tage, iteration optimization, context registers; the TTDA abstract pipeline - storage and names in the TTDA, the waiting-matching problem. Part 3 The explicit token store: storage, tokens and instructions; code blocks; transformation of tokens; activity generation - dyadic operators, monadic operators, dyadic operators with a constant operand; token generation - the arithmetic rule, the send rule, the extract rule, combining rules; the heap. Part 4 Compiling for an ETS dataflow processor: basic instruction set equivalences - machine data types, TTDA instructions, rewriting three-imput instructions, operand matching rules, rewriting instructions with three or more destinations, instruction opcode classes; loops; I-structures - descriptors and multiple readers - descriptors, multiple deffered reads; closures; resource managers; operators with more than tow inputs; slot allocation revisited. Part 5 Compiling imperative languages for an ETS: threads; translating quads into tread sequences; multiple threads within an activation. Part 6 Monsoon - an ETS multiprocessor: multiple processors - sharing code, interleaving structures, two ways of referencing presence bits; a LIFO token queue; exceptions; the network - bandwidth requirements, the write-acknowledgment problem; hardware support for infinite processor simulation; machine data types - tokens; instructions; processing pipeline; status. Part 7 Monsoon instruction decoding: first level decode - effective address generation, type map, presence map, operand fetch/store; second level decode - function unit control, floating point, arithmetic and logic unit, pointer increment unit, type propagation unit, machine control unit, next address control, form token section, form token control, stack management; exceptions; statistics.