Efficient and scalable parallel graph partitioning
Résumé
The realization of efficient parallel graph partitioners requires the parallelization of the multi-level framework which is commonly used in sequential partitioners to improve quality and speed. While parallel matching algorithms are now efficient and un-biased enough to yield coarsened graphs of good quality, the local optimization algorithms used in the refinement step of the uncoarsening process are still an issue. This talk will present the results obtained to date in the PT-Scotch project regarding k-way graph partitioning and parallel static mapping. We will show how parallel diffusive method can advantageously replace classical (and purely sequential) Fiduccia-Mattheyses-like algorithms for local optimization, as well as the specific algorithmic problems posed by static mapping.