11.1.3 Algorithms for Load Balancing

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].