For access to this article, please select a purchase option:
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
Your recommendation has been sent to your librarian.
The maximum speedup of a multiprocessor system is limited by the sequential part of an algorithm, and in loosely coupled processor systems a large 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 determining the distribution for loosely coupled multiprocessors using a branch and bound technique based on the Moore-Skelboe interval arithmetic 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 workstations, the optimal data distribution provides a significant performance increase of 44% over the equal distribution, which does not take into account communication overheads. Further, it is shown that, for a workstation cluster with random variations in their processing speeds, the execution time ratio of the equal and optimal distributions remains relatively unchanged. Thus the execution time of the optimal data distribution is no more sensitive to processor speed variation than the execution time of the equal distribution.
Inspec keywords: multiprocessing systems; performance evaluation; matrix multiplication; resource allocation
Other keywords:
Subjects: Operating systems; Multiprocessing systems; Linear algebra (numerical analysis); Performance evaluation and testing