The prime objective of the project described in this thesis was the development of a parallel processing system capable of exploiting all forms of parallelism present in a program. Conventional approaches, based upon Von Neumann concepts, tend to perform poorly in attempts to exploit parallelism, except in certain special cases. Among the alternatives to the Von Neumann model, the dataflow model of computing offers a simple, yet powerful, formalism for describing parallel computations.
The architecture to be described in this thesis, called PATTSY (Processor Array Tagged-Token SYstem), is of the dataflow type and can be considered to offer a compromise between two well known dynamic dataflow systems, namely the Manchester and Arvind machines. It is shown in the thesis that the compromise position taken in the design of PATTSY allows our machine to offer most of the advantages of the Manchester and Arvind systems, while substantially reducing their disadvantages.
PATTSY has been built using entirely off-the-shelf components. Important features include a capability for dynamic re-routing of tokens in the presence of faults and built-in facilities to aid deadlock detection and program debugging. Also described in the thesis is a new batching arbitration scheme necessary for efficient processor inter-communication, and a bus structure that can support the techniques of batching arbitration, deadlock detection and token re-routing.
Four major software issues are also dealt with; these are 1) procedure handling, 2) loop handling, 3) data structure handling and 4) the design of an instruction set for a base language. Data movement in PATTSY is minimised in two ways: 1) by unfolding loops at run-time at Processing Element (PE) level and 2) by distributing the elements of data structures over all the PEs. Brief descriptions of garbage collection and run-time error handling are also given.
The thesis also describes a language called Adam which is being developed for the user-interface to PATTSY. As with other dataflow languages, Adam is characterised by an imperative syntax and functional semantics. Some preliminary work on the debugging of dataflow programs is also presented.