Next: 11.1.4 Simulated Annealing
Up: 11.1 Load Balancing as
Previous: 11.1.2 The Optimization Problem
This book presents performance evaluation of three load-balancing
algorithms, all of which run in parallel. With a massively parallel machine,
it would not be possible to load-balance the mesh sequentially. This is
because (1) there would be a serious sequential bottleneck, (2) there would not be enough memory in a host machine to
store the entire distributed mesh, and (3) the large cost incurred in
communicating the entire mesh.
The three methods are:\
- SA-Simulated annealing: We
directly minimize the above cost function by a process analogous to
slow physical cooling.
- ORB-Orthogonal recursive bisection: A simple method which cuts the graph into two by a vertical
cut, then cuts each half into two by a horizontal cut, then cuts each
quarter vertically, and so on. These cuts are usually
motivated by the natural geometrical or physical structure of the
problem [Baden:87a], [Fox:88mm]. However, they can also be
generated in more abstract fashion directly from a graph [Fox:88nn].
- ERB-Eigenvector recursive bisection: This method also cuts
the graph in two then each half into two, and so on, but the cutting is done
using an eigenvector of a matrix with the same sparsity structure as the
adjacency matrix of the graph. The method is an approximation to a
computational neural net [Fox:88e], [Williams:91a].
Guy Robinson
Wed Mar 1 10:19:35 EST 1995