Towards Chapel-based Exascale Tree Search ...
Type de document :
Communication dans un congrès avec actes
Titre :
Towards Chapel-based Exascale Tree Search Algorithms: dealing with multiple GPU accelerators
Auteur(s) :
Carneiro, Tiago [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Melab, Nouredine [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Hayashi, Akihiro [Auteur]
Georgia Institute of Technology [Atlanta]
Sarkar, Vivek [Auteur]
Georgia Institute of Technology [Atlanta]
Optimisation de grande taille et calcul large échelle [BONUS]
Melab, Nouredine [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Hayashi, Akihiro [Auteur]
Georgia Institute of Technology [Atlanta]
Sarkar, Vivek [Auteur]
Georgia Institute of Technology [Atlanta]
Titre de la manifestation scientifique :
HPCS 2020 - The 18th International Conference on High Performance Computing & Simulation
Ville :
Barcelona / Virtual
Pays :
Espagne
Date de début de la manifestation scientifique :
2021-03-22
Titre de la revue :
Proceedings of HPCS 2020 - The 18th International Conference on High Performance Computing & Simulation
Mot(s)-clé(s) en anglais :
Backtracking
GPU
PGAS
Chapel
GPU
PGAS
Chapel
Discipline(s) HAL :
Informatique [cs]/Recherche opérationnelle [cs.RO]
Résumé en anglais : [en]
Tree-based search algorithms applied to combinatorial optimization problems are highly irregular and time consuming when it comes to solving big instances. Solving such instances efficiently requires the use of massively ...
Lire la suite >Tree-based search algorithms applied to combinatorial optimization problems are highly irregular and time consuming when it comes to solving big instances. Solving such instances efficiently requires the use of massively parallel distributed-memory supercomputers. According to recent Top 500 trends, the degree of parallelism in these supercomputers continues to increase in size and complexity, with millions of heterogeneous (mainly CPU-GPU) cores. Harnessing this scale of computing resources raises at least three challenging issues which are described and addressed in this paper. Indeed, as a step towards exascale computing, we revisit the design and implementation of tree search algorithms dealing with multiple GPUs, in addition to scalability and productivity-awareness using Chapel. The proposed algorithm exploits Chapel's distributed iterators by combining a partial search strategy with pre-compiled CUDA kernels for more efficient exploitation of the intra-node parallelism. Extensive experimentation on big N-Queens problem instances using 24 GPUs shows that up to 90% of the linear speedup can be achieved.Lire moins >
Lire la suite >Tree-based search algorithms applied to combinatorial optimization problems are highly irregular and time consuming when it comes to solving big instances. Solving such instances efficiently requires the use of massively parallel distributed-memory supercomputers. According to recent Top 500 trends, the degree of parallelism in these supercomputers continues to increase in size and complexity, with millions of heterogeneous (mainly CPU-GPU) cores. Harnessing this scale of computing resources raises at least three challenging issues which are described and addressed in this paper. Indeed, as a step towards exascale computing, we revisit the design and implementation of tree search algorithms dealing with multiple GPUs, in addition to scalability and productivity-awareness using Chapel. The proposed algorithm exploits Chapel's distributed iterators by combining a partial search strategy with pre-compiled CUDA kernels for more efficient exploitation of the intra-node parallelism. Extensive experimentation on big N-Queens problem instances using 24 GPUs shows that up to 90% of the linear speedup can be achieved.Lire moins >
Langue :
Anglais
Comité de lecture :
Oui
Audience :
Internationale
Vulgarisation :
Non
Collections :
Source :
Fichiers
- https://hal.archives-ouvertes.fr/hal-03149394/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03149394/document
- Accès libre
- Accéder au document
- https://hal.archives-ouvertes.fr/hal-03149394/document
- Accès libre
- Accéder au document
- document
- Accès libre
- Accéder au document
- final_hpcs2020.pdf
- Accès libre
- Accéder au document