|
 lgorithms
that find good partitionings of highly unstructured and irregular graphs are critical
for developing efficient solutions for a wide range of problems in many applications
on both serial and parallel computers. Traditional graph partitioning problems focus
on computing a partitioning of a graph such that each domain has an equal number
of vertices, and the number of edges cut by partitioning is minimized. This graph
partitioning problem is widely used for static distribution of the mesh in parallel
scientific simulations, VLSI design, and many other areas. While no algorithms are
known to produce verifiably optimal solutions in a reasonable amount of time, a number
of multilevel algorithms have been developed recently that are able to obtain near-optimal
results very quickly.
Researchers at the University of Minnesota Army High Performance Computing Research
Center (AHPCRC) have been working on developing and implementing these algorithms.
Professor Vipin Kumar and Assistant Professor George Karypis of the Department of
Computer Science and Engineering and AHPCRC at the University of Minnesota are the
principal investigators for this project. Professor Kumar is a Fellow of the Supercomputing
Institute. They, along with Graduate Student Researcher Kirk Schloegel of the Department
of Computer Science and Engineering at the University of Minnesota, have implemented
static and dynamic serial and parallel graph partitioning libraries called Metis
and ParMetis. These libraries are widely used for a variety of applications in government,
academia, and industry. They have been shown to be scalable to graphs with very large
numbers of vertices. In fact, ParMetis is able to compute a 128-way partitioning
of an eight million element three-dimensional finite element mesh in less than nine
seconds on a 128-processor Cray T3D.
 |
| Mesh for a 6-phase automobile engine
simulation. Each color represents a different computational phase. A partitioning
is required in which every domain contains an equal amount of vertices of each different
color. Mesh provided by Analysis and Design Application Company Limited. |
Unfortunately, the traditional graph partitioning problem alone is not sufficient
to model the underlying requirements of many current and emerging applications, especially
in the area of high-performance scientific simulations. For example, the effective
parallel solution of multi-phase computations in areas such as automobile engine
design (see figures) and crash-worthiness testing requires that the partitioning
algorithm simultaneously balance the computations performed during each one of the
phases and minimize the various communication overheads–none of which can be accomplished
by current graph models and partitioning algorithms. A number of emerging applications
also require that not only computation, but also memory requirements be balanced
across the processors to allow the execution of very large problems on parallel machines.
These problems are better modeled by multi-constraint graph partitioning in which
each vertex has multiple weights, and desired partitioning is such that sums of each
of the vertex weights are balanced across all domains.
Currently, this group is developing new generalized formulations for multi-constraint
graph partitioning and algorithms for solving these problems. Initial versions of
these algorithms are already included in the Metis library (available at www-users.cs.umn.edu/~karypis/metis).
 |
 |
| Two domains from an 8-way partitioning
computed using the multi-constraint partitioning algorithm implemented in the Metis
library. Mesh provided by Analysis and Design Application Company Limited. |
|
This information is available in alternative formats upon request by
individuals with disabilities. Please send email to
alt-format@msi.umn.edu
or call 612-624-0528.
|
|
URL: http://www.msi.umn.edu/general/Bulletin/Vol.15-No.2/index.html
|
|
|
This page last modified on
Monday, 12-May-2008 17:00:26 CDT |
|
Website related questions or problems should be directed to
webmaster@msi.umn.edu
The Supercomputing Institute does not collect personal information on
visitors to our website. For the University of Minnesota policy, see
www.privacy.umn.edu.
|
|
| |
|
