Design and Implementation of Multi-Threaded and Hybrid Parallel Graph Partitioning Algorithms in Scotch v7
Conception et mise en œuvre d'algorithmes de partitionnement de graphes multi-tâches et à parallélisme hybride dans Scotch v7
Résumé
Graph partitioning is a ubiquitous problem which has many applications in scientific computing. Due to the ever increasing size of the problems to solve, many parallel implementations of graph partitioning algorithms have been proposed in the literature, whether for shared-memory multiprocessors or distributed-memory multicomputers.
This paper describes the design and implementation of multi-threaded algorithms in version 7 of the Scotch partitioning package. These algorithms concern both the formerly sequential version, Scotch, and the parallel, distributed-memory version, PT-Scotch. Notably, a hybrid parallel (MPI+threads) graph coarsening algorithm is proposed, which is used to accelerate the classic multilevel partitioning framework. In order to provide scientific reproducibility, deterministic algorithms have been implemented whenever possible, and can be selected at the user's choice. Concurrent execution of multiple partitioning tasks is made possible by their encapsulation within execution contexts.
While a global linear speedup is out of reach due to the many remaining non-parallel sections, the multi-threaded algorithms evidence high scalability themselves, and provide for a significant improvement in run time, without any loss in partition quality.
Le partitionnement de graphes est un problème très courant qui a de nombreuses applications en calcul scientifique. Du fait de la taille toujours croissante des problèmes à résoudre, de nombreuses mises en œuvre parallèles d'algorithmes de partitionnement de graphes ont été proposées dans la littérature, que ce soit sur des ordinateurs multi-processeurs à mémoire partagée ou des ordinateurs parallèles à mémoire distribuée.
Cet article décrit la conception et la mise en œuvre d'algorithmes multi-tâches au sein de la version 7 du logiciel de partitionnement Scotch. Ces algorithmes concernent à la fois l'ancienne version séquentielle, Scotch, et la version parallèle à mémoire distribuée, PT-Scotch. Notamment, un algorithme hybride parallèle (MPI + threads) de contraction de graphes est proposé, qui est utilisé pour accélérer la méthode classique de partitionnement multi-niveau. Afin d'assurer la reproductibilité des résultats, des algorithmes déterministes ont été mis en œuvre dans la mesure du possible et peuvent être sélectionnés par l'utilisateur. L'exécution simultanée de plusieurs tâches de partitionnement est rendue possible par leur encapsulation dans des contextes d'exécution.
Bien qu'une accélération globale linéaire soit hors de portée du fait des nombreuses sections non parallèles restantes, les algorithmes multi-tâches existants passent bien à l'échelle et permettent une amélioration significative de la durée d'exécution, sans perte de qualité de la partition.
Origine : Fichiers produits par l'(les) auteur(s)
