PMondriaan: A Parallel Hypergraph Partitioner

Abstract

Hypergraph partitioning is an important problem with many applications, such as very large scale integration design and sparse matrix distribution for parallel computation. The data provided by these applications has become so large, that serial partitioners have trouble handling these hypergraphs because of memory and/or running time limitations. In this thesis, a new parallel partitioning method is presented for a distributed-memory architecture. We extend the multilevel framework to a parallel multilevel framework that is used to recursively bipartition the hypergraph. The parallel coarsening algorithm uses a sampling scheme to reduce communication. The parallel refinement algorithm moves groups of vertices together, to limit the number of synchronizations. The method was implemented in a parallel hypergraph partitioner, named PMondriaan, that can partition a hypergraph into $k$ parts using $p$ processors. Our experiments show that PMondriaan achieves our goal of memory scalability, while providing state-of-the-art solutions. A reasonable speedup is achieved with respect to the single processor running times of PMondriaan, but no speedup is achieved with respect to the Mondriaan partitioner.