Graph vs Hypergraph Partitioning
Graph partitioning has proven quite useful in scientific computing.
Hypergraph partitioning
is a more recent improvement
that uses a hypergraph model, which is
often a more accurate model than the graph model for scientific computing.
(Hypergraphs contain hyperedges which connect two or more
vertices.)
See [Catalyurek & Aykanat] and
[Hendrickson & Kolda]
for further details.
You do not need to understand the underlying models
to use graph or hypergraph partitioning for load-balancing
in Zoltan. The basic trade-offs are:
- Hypergraph partitioning usually produces partitions (assignments)
of higher quality than graph partitioning, which may reduce
communication time in parallel applications (up to 30-40%
reduction has been reported). However, hypergraph
partitioning takes longer time to compute.
- The graph model is restricted to symmetric data dependencies.
If you have a non-symmetric problem, we recommend hypergraph
partitioning.
Migrating from ParMetis to PHG in Zoltan
If you already use Zoltan for graph partitioning (via ParMetis),
there are three ways to switch to the Zoltan-PHG hypergraph partitioner:
- The quick and easy way: Just change the
LB_METHOD to "Hypergraph".
Zoltan will then use the graph query functions (presumably
already implemented) to construct a hypergraph model, which
is similar to but not equivalent to the graph.
- The proper way: Change the LB_METHOD, but also implement and
register the
hypergraph query functions
required by Zoltan. These may give a more accurate representation
of data dependencies (and communication requirements) for your
application.
- If you really want graph (not hypergraph) partitioning:
Just change the
LB_METHOD to "Graph".
Zoltan will then use PHG as a graph partitioner, which is slower than
ParMetis but often produces better partitions (lower cuts).
Technical note: A hypergraph is constructed from the graph as follows:
The vertices are the same in the hypergraph as in the graph. For each vertex
v, create a hyperedge that consists of all neighbors in the graph
and v itself.
[Table of Contents |
Next: ParMETIS |
Previous:
Graph Partitioning | Privacy and Security]