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 5 articles )
Showing results 1 to 5 of 5.
- Ç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)
- 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)