Load balancing in large parallel systems with distributed memory is a difficult task often influencing the overall efficiency of applications substantially. A number of efficient distributed load balancing strategies have been developed in the recent yea.rs. Although they are currently not generally available as part of parallel operating systems, it is often not difficult to integrate them into applications.

In this paper we use the notion of graph embedding to develop a general description for different kinds of load balancing problems. Based on the characteristics of the application and the parallel system we classify the problems into five groups. For the case of applications from the field of scientific computing, useful methods are described in more detail.

If an application isstatic, the load balancing problem reduces to the task of mapping the application graph onto the processor network. For modern parallel architectures, this problem can further be relaxed to graph partitioning. We give a survey of the most important graph partitioning heuristics.

If the application is dynamic, e.g. adaptively refining meshes in finite element calculations, a number of different dynamic load balancing strategies can be used to handle the varying utilization of processors. We describe several methods based on a two-step approach: 1.) Considering how much load to move in which direction and 2.) which load to move.

purchase the full-text of this chapter (price £20)

go to the previous chapter
go to the next chapter
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)