Skip to Main content Skip to Navigation
Conference papers

Multithreaded clustering for multi-level hypergraph partitioning

Abstract : Requirements for efficient parallelization of many complex and irregular applications can be cast as a hypergraph partitioning problem. The current-state-of-the art software libraries that provide tool support for the hypergraph partitioning problem are designed and implemented before the game-changing advancements in multi-core computing. Hence, analyzing the structure of those tools for designing multithreaded versions of the algorithms is a crucial tasks. The most successful partitioning tools are based on the multi-level approach. In this approach, a given hypergraph is coarsened to a much smaller one, a partition is obtained on the the smallest hypergraph, and that partition is projected to the original hypergraph while refining it on the intermediate hypergraphs. The coarsening operation corresponds to clustering the vertices of a hypergraph and is the most time consuming task in a multi-level partitioning tool. We present three efficient multithreaded clustering algorithms which are very suited for multi-level partitioners. We compare their performance with that of the ones currently used in today's hypergraph partitioners. We show on a large number of real life hypergraphs that our implementations, integrated into a commonly used partitioning library PaToH, achieve good speedups without reducing the clustering quality.
Complete list of metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-00763565
Contributor : Equipe Roma <>
Submitted on : Thursday, December 19, 2019 - 11:18:27 AM
Last modification on : Thursday, December 19, 2019 - 3:13:47 PM
Long-term archiving on: : Friday, March 20, 2020 - 3:15:48 PM

File

cdku-ipdps12.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Umit Catalyurek, Mehmet Deveci, Kamer Kaya, Bora Uçar. Multithreaded clustering for multi-level hypergraph partitioning. 26th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2012,, May 2012, Shanghai, China. pp.848--859, ⟨10.1109/IPDPS.2012.81⟩. ⟨hal-00763565⟩

Share

Metrics

Record views

325

Files downloads

166