le 27 mars 2021
Vers des algorithmes de recherche arborescente Exascale basés sur Chapel : Traiter avec des accélérateurs de GPU multiples Nouredine Melab (Université de Lille, CNRS/CRIStAL), Tiago Carneiro (INRIA Lille), Akihiro Hayashi, Vivek Sarkarx (Institut de Technologie Georgia, USA)
Les algorithmes de recherche arborescente appliqués aux problèmes d’optimisation combinatoire sont très irréguliers et prennent beaucoup de temps lorsqu’il s’agit de résoudre de grandes instances. La résolution efficace de ces instances nécessite l’utilisation de supercalculateurs massivement parallèles à mémoire distribuée. Selon les tendances récentes du Top 500, le degré de parallélisme de ces superordinateurs continue d’augmenter en taille et en complexité, avec des millions de cœurs hétérogènes (principalement CPU-GPU). L’exploitation de cette échelle de ressources informatiques soulève au moins trois problèmes difficiles qui sont décrits et traités dans le présent document. En effet, en tant qu’étape vers le calcul exascale, nous revisitons la conception et l’implémentation d’algorithmes de recherche d’arbres traitant de multiples GPU, en plus de l’extensibilité et de la prise en compte de la productivité à l’aide de Chapel. L’algorithme proposé exploite les itérateurs distribués de Chapel en combinant une stratégie de recherche partielle avec avec des noyaux CUDA précompilés pour une exploitation plus efficace du parallélisme intra-nœud. Des expériences approfondies sur de grandes instances de problèmes N-Queens utilisant 24 GPU montrent qu’il est possible d’atteindre jusqu’à 90 % de l’accélération linéaire.
En savoir plus...
français
English