A unified approach to performance evaluation of dataflow and multiprocessing architectures
Dipak Ghosal, Laxmi Narayan Bhuyan · 1988
With the recent advances in VLSI technology, parallel processing architectures have emerged to satisfy the growing need for more computing power. The wide popularity of these architectures has been further enhanced by the realization that significant parallelism is inherent in application software. A large number of parallel processing architectures have been proposed. This has necessitated the development of tools to evaluate these architectures so that a choice between the various alternatives can be made. This dissertation presents a unified analytical tool to evaluate two distinct styles of parallel processing architectures, namely, the dataflow architectures and the shared memory multiprocessor systems. Previous studies on dataflow architectures have been based on simulation or experiments on small prototype machine. On the other hand, shared memory multiprocessor systems have been extensively studied at the interconnection network level. The primary aim of the study reported in this dissertation was to incorporate the dataflow graph/task graph into the model of these architectures. Since the exact modeling of the execution of any arbitrary dataflow graph/task graph is an intractable problem, some reasonably simple and approximate characterization of these graphs were attempted. As a result, we proposed the notion of average parallelism to characterize both the dataflow and multiprocessing task graphs. Based on this characterization, closed queueing networks of these architectures were developed and their finite population was shown to be related to the average parallelism of the dataflow graph/task graph under execution. In the case of the dataflow architectures, the results obtained from the analytical model were validated with those obtained from the prototype Manchester dataflow computer. For the shared memory multiprocessor, validation was done through simulation. Based on the models, these architectures were evaluated under different loading conditions and their bottleneck centers were identified. Also, various system level performance indices such as response time, processing power, etc., were obtained. Furthermore, through the model, the scalability and the computation-communication trade-offs in these architectures were studied. Finally, the similarity in the performance behavior of dataflow and multiprocessing architectures is argued to be based on certain correspondences between these architectures.