A Robust Dynamic Load-balancing Scheme for Data Parallel Application on Multicomputer Systems

Abstract

Multicomputer systems based on message passing draw attractions in the field of high performance computing, where loop or data parallelism is a main source of parallel processing. When exploiting parallelism on multicomputers, however, we confront several challenging problems. First, the nodes of multicomputer are likely to be heterogeneous with respect to computing power and workload. To minimize the elapsed time of program, loads should be balanced according to the performance of nodes. In addition, various dynamic failures should be managed appropriately. Lastly, selecting a proper number of nodes in a node pool is also desirable to achieve a good performance. We propose a new dynamic load balancing scheme called RAS to simultaneously deal with the three issues. RAS solves the load-balancing problem and dynamic failures by a work stealing mechanism, and the processor selection problem by data distribution based on a reservation scheme. According to our experiments on an IBM SP2 with matrix multiplication and ray tracing, RAS has shown better performance than other algorithms such as static chunk and weighted factoring under a shared running environment and even under the dedicated running environment.