Shared memory parallel algorithms in Scotch 6
Résumé
The Scotch software package comprises two libraries: the Scotch sequential library, and the PT-Scotch parallel library. The latter is based on a distributed memory paradigm, and uses MPI to exchange data between processes. The advent of many-core, shared memory, machines imposes to reconsider this approach. The complexity of graph partitioning algorithms is low compared to factorization. A first solution is to reduce communication overhead by running graph partitioning only on a limited number of nodes. A second solution is to make graph partitioning algorithms more efficient, by reducing communication overhead and resorting to shared memory parallelism. This talk present our first experiments in this direction.
La distribution logicielle Scotch conprend deux bibliothèques : la bibliothèque séquentielle Scotch et la bibliothèque parallèle PT-Scotch. Cette dernière est basée sur le paradigme de la mémoire distribuée, et utilise MPI pour échanger les données entre processeurs. L'existence de machines many-core à mémoire partagée impose de reconsidérer cette approche. La complexité des algorithmes de partitionnement de graphes est faible par rapport aux temps de factorisation. Une première solution est de réduire les surcoûts de communication en ne calculant les partitionnements que sur un nombre limité de noeuds. Une seconde solution est de rendre les algorithmes de partitionnement plus efficaces, en réduisant le surcoût de communication et en se tournant vers le parallélisme à mémoire partagée. Cet exposé présente nos premiers travaux dans cette direction.