PT-Scotch : Un outil pour la renumérotation parallèle efficace de grands graphes dans un contexte multi-niveaux

Cédric Chevalier (1) , François Pellegrini (1, 2)

1 SCALAPPLIX - Algorithms and high performance computing for grand challenge applications
2 LaBRI - Laboratoire Bordelais de Recherche en Informatique

La renumérotation parallèle de grands graphes est un problème difficile, parce que ni les algorithmes de degré minimum ni les meilleures méthodes de partitionnement de graphes nécessaires à la dissection emboîtée ne se parallélisent bien ni ne sont scalables. Cet article présente un ensemble d'algorithmes, mis en oeuvre au sein de l'outil PT-SCOTCH, qui permettent de calculer de façon parallèle et multi-tâche des renumérotations de très grands graphes, dont la qualité est équivalente à celle des meilleurs algorithmes séquentiels connus.

Mots clés: Renumérotation; partionnement; graphe; parallélisme; multi-tâche

Domaines: Calcul parallèle, distribué et partagé [cs.DC]

Cédric Chevalier, François Pellegrini. PT-Scotch : Un outil pour la renumérotation parallèle efficace de grands graphes dans un contexte multi-niveaux. RenPar'17 / SympA'2006 / CFSE'5 / JC'2006, Oct 2006, Canet en Roussillon, France. 8 p. ⟨hal-00410408⟩