On the organization and performance of a function flow multi computer
Michael Paul Whelan · 1982
The organization, programming and performance of a general purpose multi computer system is examined. The goals of this system are to achieve high average throughput, without the need for low level program tuning, to be extensible in small increments over a broad range, to gracefully degrade under processor failures and to be suitable for implementation in VLSI technology. An architecture based on data flow execution is proposed to achieve these goals. The architecture consists of many identical processors and a central control unit. The control unit assigns tasks to the processors via a shared bus and the processors return the results of these tasks over another shared bus. In the control unit, task synchronization is handled in a distributed fashion by using data flow mechanisms. Issues relating to the implementation of such a machine are discussed. After the basic architecture has been presented, issues relating to the execution of software constructs on the machine are considered. Among the issues considered are the lazy and active mode of conditional code execution and cautious and zealous modes of loop execution. The effects of bus system congestion on the machine's performance are then considered. A congestion model is developed to account for these effects. The results of this analysis are compared with simulation results for the system in question, against published simulation studies for a single bus congestion system and against alternative analysis techniques. The methods of analysis which are developed require far less computational effort than does the product form approach while providing a very good model for the effects of congestion. Using the congestion techniques developed, the performance of the architecture while executing several important programs is examined. The effects of both congestion and data dependencies are taken into account. The problems examined include the FFT algorithm, the solution of Laplace's equation using successive over relaxation and a variety of image processing tasks. The image processing tasks considered were convolution filtering, the Sobel edge detector, median filtering, histogramming, pixel classification, clustering and relaxation.