DEVELOPMENT OF A METHOD OF OPTIMIZING DATA DISTRIBUTION ON A LOOSELY-COUPLED MULTIPROCESSOR SYSTEM

The maximum speedup of multiprocessor system is limited by the sequent ial part of an algorithm, and in loosely coupled processor systems a l arge part of this sequentiality is caused by the communication between processors. As this communication is dependent on the distribution of data the data distribution must be optimised in order to achieve the maximum speedup. In the paper the authors present a new method of dete rmining the distribution for loosely coupled multiprocessors using a b ranch and bound technique based on the Moore-Skelboe interval arithmet ic algorithm. The key issue of this load-balancing algorithm has been addressed, namely the branch selection criterion. When this method is applied to a matrix multiplication algorithm running on a cluster of w orkstations, the optimal data distribution provides a significant perf ormance increase of 44% over the equal distribution, which does not ta ke into account communication overheads. Further, it is shown that, fo r a workstation cluster with random variations in their processing spe eds, the execution time ratio of the equal and optimal distributions r emains relatively unchanged. Thus the execution time of the optimal da ta distribution is no more sensitive to processor speed variation than the execution time of the equal distribution.