Algorithms and Software for Partitioning Graphs
Graph partitioning is an NP hard problem with numerous applications.
It appears in various forms in parallel computing, sparse matrix
reordering, circuit placement and other important disciplines.
I worked with Rob Leland for several years on heuristic methods
for partitioning graphs, with a particular focus on parallel
computing applications. Our contributions include:
More recently, I have worked with Tammy Kolda on alternatives
to the standard graph partitioning model. A critique of the
standard approach and a discussion of alternatives can be
found below. I have also been
working with Karen Devine and a number of other researchers on
dynamic load balancing.
Dynamic load balancing is fundamentally harder than static partitioning.
Algorithms and implementations must run quickly in parallel without
consuming much memory. Interfaces need to be subroutine calls instead
of file transfers. And since the data is already distributed, the new
partition should be similar to the current one to minimize the amount
of data that needs to be redistributed. We are working to build a tool called
Zoltan
to address this plethora of challenges. Zoltan is designed to be extensible
to different applications, algorithms and parallel architectures. For example,
it is data-structure neutral - an object oriented interface separates the
application data structures from those of Zoltan. The tool will also support
a very general model of a parallel computer, facilitating the use of
heterogeneous machines.
Closely related to Zoltan, I have been interested in the software
challenges inherent in parallelizing unstructured computations. I
feel that well-designed tools and libraries are the key to addressing
this problem. I have also worked with Ali Pinar and Steve Plimpton on
algorithms for some of the kernel operations which arise in this setting,
and relevant papers can be found here.
Graph Partitioning Algorithms and Tools
Alternatives to Standard Graph Partitioning
More recently, I have become disenchanted with the graph partitioning
abstraction as it is applied to parallel computing. Some of my
concerns and an effort to address them can be found in the following
papers and talks.
Algorithms for Unstructured Applications
Many unstructured computations can be built from simpler, common
components. Methods for doing so, along with efficient algorithms for
some of these kernels can be found in the following papers.
Chaco
Rob Leland and I have developed a widely used graph partitioning
tool called Chaco, which is
available under a GNU open source license. The code is used
at over 300 institutions for parallel computing, sparse matrix
reordering, circuit placement and a range of other applications.
The Chaco web page has more
information about the capabilities of the software and how
to download it.
Other Graph Partitioning Web Sites
Return to Bruce's home page