ON MULTIPROCESSING OF CHAIN STRUCTURED COMPUTATIONS

Abstract

Multiprocessor systems speed up the program execution by performing many tasks. simultaneously. In such systems, a modular program must have its modules assigned among the processors so as to avoid the excessive interprocessor communication, while taking advantage of specific efficiencies of some processors in executing some program modules. The objective of mapping is to allocate tasks in such a way that minimizes execution time with a minimum number of parallel processors. Factors contributing to the cost of an assignment are module execution time, data transmitted between modules, speed of processors and link speeds. Optimally mapping an arbitrary structured task graph on an arbitrary structured system graph is very complex. A number of constraints on the structure of the program and/or the multicomputer may lead to assignment in polynomial time. This thesis presents three algorithms for task assignment in multiprocessor system. The first algorithm assigns a chain- structured parallel program to a chain-structured parallel processor interconnection. In this algorithm, the objective is to minimize the bottleneck cost, which is the measure of quality of the assignment. The second algorithm maps multiple independent program chains on a host-satellite system. Here a minimum sum-bottleneck path value gives the optimal mapping. The last algorithm maps chain-structured parallel programs on a homogeneous chain-structured multiprocessor system. All three algorithms presented here are based on probing approaches. These algorithms are compared with the existing algorithms to show that they perform better.