GPU-Accelerated Tree-Search in Chapel ...
Document type :
Communication dans un congrès avec actes
Title :
GPU-Accelerated Tree-Search in Chapel versus CUDA and HIP
Author(s) :
Helbecque, Guillaume [Auteur]
Université du Luxembourg [Uni.lu]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Inria Lille - Nord Europe
Optimisation de grande taille et calcul large échelle [BONUS]
Krishnasamy, Ezhilmathi [Auteur]
Université du Luxembourg [Uni.lu]
Melab, Nouredine [Auteur]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Inria Lille - Nord Europe
Optimisation de grande taille et calcul large échelle [BONUS]
Bouvry, Pascal [Auteur]
Université du Luxembourg [Uni.lu]
Université du Luxembourg [Uni.lu]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Inria Lille - Nord Europe
Optimisation de grande taille et calcul large échelle [BONUS]
Krishnasamy, Ezhilmathi [Auteur]
Université du Luxembourg [Uni.lu]
Melab, Nouredine [Auteur]
Université de Lille
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Inria Lille - Nord Europe
Optimisation de grande taille et calcul large échelle [BONUS]
Bouvry, Pascal [Auteur]
Université du Luxembourg [Uni.lu]
Conference title :
14th IEEE Workshop Parallel / Distributed Combinatorics and Optimization (PDCO 2024)
City :
San Francisco
Country :
Etats-Unis d'Amérique
Start date of the conference :
2024-05-31
English keyword(s) :
Chapel
Tree-Search
GPU computing
CUDA
HIP
N-Queens
Nvidia
AMD
Tree-Search
GPU computing
CUDA
HIP
N-Queens
Nvidia
AMD
HAL domain(s) :
Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]
English abstract : [en]
In the context of exascale programming, the PGAS-based Chapel is among the rare languages targeting the holistic handling of high-performance computing issues including the productivity-aware harnessing of Nvidia and AMD ...
Show more >In the context of exascale programming, the PGAS-based Chapel is among the rare languages targeting the holistic handling of high-performance computing issues including the productivity-aware harnessing of Nvidia and AMD GPUs. In this paper, we propose a pioneering proof-of-concept dealing with this latter issue in the context of tree-based exact optimization. Actually, we revisit the design and implementation of a generic multi-pool GPU-accelerated tree-search algorithm using Chapel. This algorithm is instantiated on the backtracking method and experimented on the N-Queens problem. For performance evaluation, the Chapel-based approach is compared to Nvidia CUDA and AMD HIP low-level counterparts. The reported results show that in a single-GPU setting, the high GPU abstraction of Chapel results in a loss of only 8% (resp. 16%) compared to CUDA (resp. HIP). In a multi-GPU setting, up to 80% (resp. 71%) of the baseline speed-up is achieved for coarse-grained problem instances on Nvidia (resp. AMD) GPUs.Show less >
Show more >In the context of exascale programming, the PGAS-based Chapel is among the rare languages targeting the holistic handling of high-performance computing issues including the productivity-aware harnessing of Nvidia and AMD GPUs. In this paper, we propose a pioneering proof-of-concept dealing with this latter issue in the context of tree-based exact optimization. Actually, we revisit the design and implementation of a generic multi-pool GPU-accelerated tree-search algorithm using Chapel. This algorithm is instantiated on the backtracking method and experimented on the N-Queens problem. For performance evaluation, the Chapel-based approach is compared to Nvidia CUDA and AMD HIP low-level counterparts. The reported results show that in a single-GPU setting, the high GPU abstraction of Chapel results in a loss of only 8% (resp. 16%) compared to CUDA (resp. HIP). In a multi-GPU setting, up to 80% (resp. 71%) of the baseline speed-up is achieved for coarse-grained problem instances on Nvidia (resp. AMD) GPUs.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
Source :
Files
- document
- Open access
- Access the document
- PDCO2024_Helbecque_et_al_preprint.pdf
- Open access
- Access the document