The numerical solution of partial differential equations usually involves dividing up the physical domain into small elements or volumes to form a mesh. To solve the problem on a distributed memory parallel computer, the mesh should be decomposed into subdomains, the number of which usually equals the number of processors, with each subdomain assigned to a unique processor.
The static load balancing problem is that of how to decompose the mesh into subdomains so that each processor has about the same amount of computation and so that the communication cost between processors is minimized, with the overall aim of minimizing the runtime of the calculation.
After the grid is partitioned and the parallel solver code has been executed for a number of iterations, the mesh may need to be refined (or coarsened) at certain locations, based on an estimate of the discretization errors. As a consequence of the refinement (or coarsening), some processors may have significantly more (or less) elements than others, thus it becomes necessary to re-balance the load in order to maintain the parallel efficiency. This is the dynamic load balancing problem.
Usually the load of each processor remains fixed for many iterations in between mesh adaptations, and the load balancing step is only needed just after a mesh refinement or coarsening. Such quasi-dynamic load balancing problems are relatively easy to solve, although still far more difficult than the static load balancing problem.
In this paper developments over recent years and the state of the art in static and dynamic load balancing algorithms will be reviewed. The discussion is biased towards unstructured mesh based applications, although the techniques discussed here may be used in many other areas where static and dynamic load balancing problems appear, for example, task scheduling in operating systems. Section 2 introduces some useful notation, followed by Section 3 which looks at the classical as well as recent graph partitioning algorithms. Section 4 discusses dynamic load balancing algorithms. The paper finishes with some future research topics in Section 5 and conclusions in Section 6.