Design and Simulation of a Data-Flow Multiprocessor

  Bruno Richard Preiss. Master's thesis, Department of Electrical Engineering, University of Toronto, 1984. 157 pp.[39].

A data-flow execution model that supports program reentrancy, recursion and automatic run-time loop unraveling without the use of tagged tokens is described. This execution model is based on a novel data-flow program graph representation scheme which is a hybrid of static and dynamic data-flow program representation methods. In particular, the use of separate instruction and data token spaces allows program reentrancy. Execution environments called contexts execute acyclic data-flow graphs associated with high-level code blocks. Iteration and function calling are implemented by the dynamic creation of contexts.

A multiprocessor architecture that supports this execution model is proposed. The system architecture is based on a partitioned ring in which each partition of the ring is a conventional processor/memory bus. Each processor consists of a processing element and a task manager together with a portion of global memory.

The proposed architecture has been simulated in software. A number of test programs have been developed and their execution on the proposed architecture has been evaluated. The performance of the proposed architecture with various numbers of processing elements is described. In addition, a number of task scheduling algorithms are presented and evaluated.

Copyright 1984 by Bruno R. Preiss.

Full text. Catalogue Entry. BibTeX entry.