CHEVALIER, Cédric; PELLEGRINI, François

doi:10.1016/j.parco.2007.12.001

Metadatos

Licencia de uso del documento

CHEVALIER, Cédric
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]

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

Idioma

Article de revue

Este ítem está publicado en

Parallel Computing. 2008-07-01, vol. 34, n° 6-8, p. 318-331

Elsevier

Resumen en inglés

The parallel ordering of large graphs is a difficult problem, because on the one hand minimum degree algorithms do not parallelize well, and on the other hand the obtainment of high quality orderings with the nested dissection algorithm requires efficient graph bipartitioning heuristics, the best sequential implementations of which are also hard to parallelize. This paper presents a set of algorithms, implemented in the PT-Scotch software package, which allows one to order large graphs in parallel, yielding orderings the quality of which is only slightly worse than the one of state-of-the-art sequential algorithms. Our implementation uses the classical nested dissection approach but relies on several novel features to solve the parallel graph bipartitioning problem. Thanks to these improvements, PT-Scotch produces consistently better orderings than ParMeTiS on large numbers of processors.< Leer menos

Palabras clave en inglés

Parallel graph ordering

Nested dissection

Distributed memory computer

Multi-threading

URI

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

DOI

http://dx.doi.org/10.1016/j.parco.2007.12.001

Proyecto ANR

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

Orígen

Importado de Hal

Centros de investigación

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