S. Ichikawa, S. Yamashita
Proceedings ISCA 13th Int'l Conf. Parallel and Distributed Computing Systems (PDCS-2000), pp. 399-405 (2000).
Abstract:
This paper describes a static load balancing scheme for partial differential equation solvers in a distributed computing environment. Though there has been much research on static load balancing for uniform processors, a distributed computing environment is a computationally more difficult target because it usually consists of a variety of processors. Our method considers both computing and communication time to minimize the total execution time with automatic data partitioning and processor allocation. This problem is formulated as a combinatorial optimization and solved by the branch-and-bound method for up to 20--24 processors. This paper also presents approximation algorithms that give good allocation and partitioning in practical time. The quality of the approximation is quantitively evaluated in comparison to the optimal solution or theoretical lower bounds. Our method is general and applicable to a wide variety of parallel processing applications.