Towards Chapel-based Exascale Tree Search ...
Document type :
Communication dans un congrès avec actes
Title :
Towards Chapel-based Exascale Tree Search Algorithms: dealing with multiple GPU accelerators
Author(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]
Conference title :
HPCS 2020 - The 18th International Conference on High Performance Computing & Simulation
City :
Barcelona / Virtual
Country :
Espagne
Start date of the conference :
2021-03-22
Journal title :
Proceedings of HPCS 2020 - The 18th International Conference on High Performance Computing & Simulation
English keyword(s) :
Backtracking
GPU
PGAS
Chapel
GPU
PGAS
Chapel
HAL domain(s) :
Informatique [cs]/Recherche opérationnelle [cs.RO]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Files
- https://hal.archives-ouvertes.fr/hal-03149394/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03149394/document
- Open access
- Access the document
- https://hal.archives-ouvertes.fr/hal-03149394/document
- Open access
- Access the document
- document
- Open access
- Access the document
- final_hpcs2020.pdf
- Open access
- Access the document