Data Flow on a Queue Machine

  Bruno Richard Preiss. Data Flow on a Queue Machine. PhD thesis, Department of Electrical Engineering, University of Toronto, 1987. 185 pp.[40].

Data-flow computer architectures have been suggested as a means to achieve increased computational throughput via the automatic detection and exploitation of potential parallelism. In this thesis, a new approach to data-flow, called pseudo-static data flow, is described.

One way of realizing the pseudo-static data-flow approach is to use a queue machine. A queue machine is a processing element that uses a queue as the underlying mechanism for the manipulation of operands. It can be shown that instruction sequences on a queue machine are a natural execution model for computation graphs specified by acyclic data-flow graphs. A compiler for the OCCAM programming language that decomposes source programs into acyclic data-flow graphs for execution on a queue machine is described.

The architecture of a queue-machine processing element intended for use in a multiprocessor system is proposed. A multiprocessor system architecture based on a partitioned bus configuration in a ring topology that uses the queue machine processing element has been simulated in order to characterize its performance potential. The system has been simulated with up to eight processing elements and it exhibits better than linear speed-up as the number of processing elements is increased.

Copyright 1987 by Bruno R. Preiss.

Full text. Presentation slides. Catalogue Entry. BibTeX entry.