Y. F. Hu and R. J. Blake
The efficient use of distributed memory parallel systems requires the load on each processor to be well balanced. In cases where the load changes unpredictably during the computation, a dynamic load balancing strategy is needed. Load balancing problems have been studied extensively in recent years, particularly in the context of unstructured mesh based applications. Static load balancing can be approximated by a graph partitioning problem and many efficient algorithms have been developed. Significant progress has also been made in the development of dynamic load balancing algorithms. This paper looks at the history and the state of the art of both classes of algorithms, with a particular emphasis on mesh based applications. However the underlying algorithms, including those for graph partitioning and flow calculation, are sufficiently generic to be applicable to other applications.