Premium
Parallel algorithm design for workstation clusters
Author(s) -
Magee J. N.,
Cheung S. C.
Publication year - 1991
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.4380210302
Subject(s) - workstation , computer science , parallel computing , supervisor , cluster (spacecraft) , parallel algorithm , speedup , class (philosophy) , travelling salesman problem , simple (philosophy) , parallel processing , algorithm , distributed computing , operating system , artificial intelligence , philosophy , epistemology , political science , law
Clusters of workstations connected by local area networks are in common use in many organizations. The combined processing power of these clusters is rarely exploited owing to the lack of suitable parallel algorithms. The paper describes a parallel programming paradigm called supervisor‐worker , suitable for the workstation environment, which can be used to speed up the execution of a large class of existing sequential programs. Simple formulae are developed to predict the speed‐up of a parallel algorithm developed in this way. The predictions depend on two easily‐determined parameters of the sequential program and the characteristic communication cost of the workstation cluster. Consequently, it is possible to estimate the benefits of the parallel program before proceeding with detailed implementation. As an example, the parallel version of a travelling salesman program is developed and the measured speed‐up compared with the predicted speed‐up.