Comparison of initial partitioning methods for multilevel direct k-way graph partitioning with fixed vertices

Abstract : In scientific computing, load balancing is a crucial step conditioning the performance of large-scale applications. In this case, an efficient decomposition of the workload to a number of processors is highly necessary. A common approach to solve this problem is to use graph representation and perform a graph partitioning in k parts using the multilevel framework and the recursive bisection (RB) paradigm. However, in graph instances where fixed vertices are used to model additional constraints, RB often produces partitions of poor quality.In this paper, we investigate the difficulties of RB to handle fixed vertices and we compare its results with two different alternatives. The first one, called KGGGP is a direct k-way greedy graph growing partitioning that properly handles fixed vertices while the second one, introduced in kPaToH, uses RB and a post-processing technique to correct the obtained partition. Finally, experimental results on graphs that represent real-life numerical simulations show that both alternative methods provide improved partitions compared to RB.
Complete list of metadatas

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/hal-01538600
Contributor : Aurélien Esnard <>
Submitted on : Wednesday, June 14, 2017 - 10:20:01 AM
Last modification on : Thursday, January 11, 2018 - 6:22:35 AM
Long-term archiving on: Tuesday, December 12, 2017 - 2:16:55 PM

File

parco16.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial - ShareAlike 4.0 International License

Identifiers

Collections

Citation

Maria Predari, Aurélien Esnard, Jean Roman. Comparison of initial partitioning methods for multilevel direct k-way graph partitioning with fixed vertices. Parallel Computing, Elsevier, 2017, ⟨10.1016/j.parco.2017.05.002⟩. ⟨hal-01538600⟩

Share

Metrics

Record views

415

Files downloads

536