Efficient and scalable parallel graph partitioning

PELLEGRINI, François; HER, Jun-Ho

Métadonnées

Licence d’utilisation du document

PELLEGRINI, François
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]

HER, Jun-Ho
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]

Langue

Communication dans un congrès

Ce document a été publié dans

5th International Workshop on Parallel Matrix Algorithms and Applications (PMAA'08), 2008-06-20, Neuchâtel.

Résumé en anglais

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.< Réduire

Mots clés en anglais

graph partitioning

static mapping

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198361

Project ANR

SOLveurs et SimulaTIons en Calculs Extrême - ANR-06-CIS6-0010

Origine

Importé de hal

Unités de recherche

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800

Métadonnées

Partager cette publication !

Licence d’utilisation du document