A multi-level load balancing scheme for OR-parallel exhaustive search programs on the multi-PSI
- 1 February 1990
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 25 (3), 50-59
- https://doi.org/10.1145/99164.99170
Abstract
Good load balancing is the key to deriving maximal performance from multiprocessors. Several successful dynamic load balancing techniques on tightly-coupled multiprocessors have been developed. However, load balancing is more difficult on loosely-coupled multiprocessors because inter-processor communication overheads cost more. Dynamic load balancing techniques have been employed in a few programs on loosely-coupled multiprocessors, but they are tightly built into the particular programs and not much attention is paid to scalability. We have developed a dynamic load balancing scheme which is applicable to OR-parallel programs in general. Processors are grouped, and work loads of groups and processors are balanced hierarchically. Moreover, it is scalable to any number of processors because of this multi-level hierarchical structure. The scheme is tested for the all-solution exhaustive search Pentomino program on the mesh-connected loosely-coupled multiprocessor Multi-PSI, and speedups of 28.4 times with 32 processors and 50 times with 64 processors have been attained.Keywords
This publication has 8 references indexed in Scilit:
- Optimal number of processors for finding the maximum value on multiprocessor systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Distributed game-tree searchingJournal of Parallel and Distributed Computing, 1989
- GAMMON: a load balancing strategy for local computer systems with multiaccess networksIEEE Transactions on Computers, 1989
- Problem size, parallel architecture, and optimal speedupJournal of Parallel and Distributed Computing, 1988
- Overview of the Parallel Inference Machine Operating System (PIMOS)Published by Springer Nature ,1988
- Parallel depth first search. Part I. ImplementationInternational Journal of Parallel Programming, 1987
- Solution of sparse positive definite systems on a shared-memory multiprocessorInternational Journal of Parallel Programming, 1986
- Optimal static load balancing in distributed computer systemsJournal of the ACM, 1985