Rather than coloring the graph by direct minimization of the load-balance cost function, we may do better to reduce the problem to a number of smaller problems. The idea of recursive bisection is that it is easier to color a graph with two colors than many colors. We first split the graph into two halves, minimizing the communication between the halves. We can then color each half with two colors, and so on, recursively bisecting each subgraph.
There are two advantages to recursive bisection; first, each subproblem (coloring a graph with two colors) is easier than the general problem; second, there is natural parallelism. While the first stage is splitting a single graph in two, and is thus a sequential problem, there is two-way parallelism at the second stage, when the two halves are being split, and four-way parallelism when the four quarters are being split. Thus, coloring a graph with P colors is achieved in a number of stages which is logarithmic in P.
Both of the recursive bisection methods we shall discuss split a graph into two by associating a scalar quantity, , with each graph node, e, which we may call a separator field. By evaluating the median S of the , we can color the graph according to whether is greater or less than S. The median is chosen as the division so that the number of nodes in each half is automatically equal; the problem is now reduced to that of choosing the field, , so that the communication is minimized.
Orthogonal Recursive Bisection
A simple and cheap choice [Fox:88mm] for the separator field is based on the position of the finite elements in the mesh. We might let the value of be the x-coordinate of the center of mass of the element, so that the mesh is split in two by a median line parallel to the y-axis. At the next stage, we split the submesh by a median line parallel to the x-axis, alternating between x and y stage by stage, as shown in Figure 11.11. Another example is shown in Figure 12.13.
Figure 11.11: Load Balancing by ORB for Four Processors. The elements (left) are reduced to points at their centers of mass (middle), then split into two vertically, then each half split into two horizontally. The result (right) shows the assignment of elements to processors.