Zoltan User's Guide  | Next  |  Previous 

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:

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:
  1. 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.
  2. 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.
  3. 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]