In parallel and distributed systems, an important issue inmanaging a decentralized task queue is load balancing among multipleprocessors. In this paper, we propose a scheme for this problem by usinga symmetric broadcast network (SBN) which provides an efficient androbust communication pattern between processors. We compare theperformance of SBN-based load balancing algorithm withrandomization-based algorithm, gradient algorithm, and extended gradientalgorithm on a broad range of computing and communication platforms. Allfour algorithms were first implemented on an 8-processor Intel's iPSC-2,a hypercube-based multicomputer. Then, the programs were ported toParallel Virtual Machine (PVM). Using PVM we compared all fouralgorithms on (i) an d-processor bus-based Silicon Graphicsmultiprocessor (SGI), (ii) two DEC's Alpha workstations connected by aLocal Area Network, and (iii) SGI and the two DEC Alpha's connected byinternet. We found that our SBN-based algorithm performed well over awide range of workloads, and computer and communication configurations
展开▼
