Graph Partitioners
The goals of a graph partitioner, also called mesh partitioner, is to
separate the vertices of a graph into almost equal-sized components
such that the number of edges between components is minimized.
Finding good graph partitions has been the focus of much recent
research because it can be used to reduce the communication among
processors in a parallel machine. In particular if the graph
represents the communication structure of a set of entities, then the
graph partitioner can be used to allocate the entities to processors
such that communication is reduced. Graph partitioners also
have many other uses.
We have implemented three algorithms for finding separators of graphs
in NESL for the purpose of comparing the
quality of the cuts. These algorithms are: coordinate bisection,
geometric random circles, and spectral. The first two algorithms
require geometric information about locations of the vertices, while
the third does not. All three algorithms are based on cutting the
graph into two components, and then being applied recursively to split into
more components. Here we outline how the partition into two is made.
- Coordinate bisection:
- This algorithm considers each axis (x, y or z in three dimension)
and takes a median along that axis. It then measures the number of
edges that will be cut if we separate the vertices into the ones less
and greater than the median. We select the axis (one of x, y or z)
that minimizes the number of edges cut. An animation of this
algorithm is available. The
Nesl code.
- Random Circles:
- This technique due to Miller, Teng, Thurston and Vavasis, is also
geometric in nature. Instead of making planar cuts as in the
coordinate bisection, it makes spherical cuts (or circular in 2
dimensions). These cuts are made by projecting the vertices onto the
surface of a sphere in one higher dimension and then making a planar
cut on that sphere (these cuts will transform into spherical cuts when
projected back into the lower dimension). The random circles
technique can generate much better cuts than coordinate bisection.
The Nesl code.
- Spectral bisection
- This algorithm is based on finding the second eigenvector of the
Jacobian of the graph. This vector is then sorted and all the
vertices are split based on amplitude. The algorithm is described in
more detailed in a paper
by Pothen, Simon, and Wang.
The Nesl code.
Our work is joint with several other groups here at Carnegie Mellon
and elsewhere, including Gary Miller, the
iWarp
project, Mike Heroux at Cray Research,
Shanghua Teng at the University of Minnesota,
and Eric Schwabe at Northwestern.
Here is a paper that overviews the work.
Related Work (online)
Up to the Irregular Algorithms page,
the NESL page, or
the Scandal page.
guy.blelloch@cs.cmu.edu.