Parkway 2.0: A parallel multilevel hypergraph partitioning tool. We recently proposed a coarse-grained parallel multilevel algorithm for the k-way hypergraph partitioning problem. This paper presents a formal analysis of the algorithm’s scalability in terms of its isoefficiency function, describes its implementation in the Parkway 2.0 tool and provides a run-time and partition quality comparison with state-of-the-art serial hypergraph partitioners. The isoefficiency function (and thus scalability behaviour) of our algorithm is shown to be of a similar order as that for Kumar and Karypis’ parallel multilevel graph partitioning algorithm. This good theoretical scalability is backed up by empirical results on hypergraphs taken from the VLSI and performance modelling application domains. Further, partition quality in terms of the k-1 metric is shown to be competitive with the best serial hypergraph partitioners and degrades only minimally as more processors are used.
Keywords for this software
References in zbMATH (referenced in 7 articles )
Showing results 1 to 7 of 7.
- Sebastian Schlag, Vitali Henne, Tobias Heuer, Henning Meyerhenke, Peter Sanders, Christian Schulz: k-way Hypergraph Partitioning via n-Level Recursive Bisection (2015) arXiv
- Çatalyürek, Ümit V.; Deveci, Mehmet; Kaya, Kamer; Uçar, Bora: UMPa: A multi-objective, multi-level partitioner for communication minimization (2013)
- Kayaaslan, Enver; Pinar, Ali; Çatalyürek, Ümit; Aykanat, Cevdet: Partitioning hypergraphs in scientific computing applications through vertex separators on graphs (2012)
- Selvitopi, R. Oguz; Turk, Ata; Aykanat, Cevdet: Replicated partitioning for undirected hypergraphs (2012) ioport
- Zhou, Min; Sahni, Onkar; Devine, Karen D.; Shephard, Mark S.; Jansen, Kenneth E.: Controlling unstructured mesh partitions for massively parallel simulations (2010)
- Trifunović, Aleksandar; Knottenbelt, William J.: Parallel multilevel algorithms for hypergraph partitioning (2008)
- Knottenbelt, William J.; Bradley, Jeremy T.: Tackling large state spaces in performance modelling (2007)