PGAS Data Structure for Unbalanced Tree-Based Algorithms at Scale - Bibliographie de l’équipe BONUS Accéder directement au contenu
Communication Dans Un Congrès Année : 2024

PGAS Data Structure for Unbalanced Tree-Based Algorithms at Scale

Résumé

The design and implementation of algorithms for increasingly large and complex modern supercomputers requires the definition of data structures and workload distribution mechanisms in a productive and scalable way. In this paper, we propose a PGAS data structure along with a Work-Stealing mechanism for the class of parallel tree-based algorithms that explore unbalanced trees using the depth-first search strategy. The contribution has been implemented and packaged as an open-source module in the Chapel PGAS language. The experimentation of the contribution in a single-node setting using backtracking applied to fine-grained Unbalanced Tree-Search benchmark shows that 68% of the linear speed-up can be achieved. In addition, the scalability of the contribution has been evaluated using the Branch-and-Bound algorithm to solve big instances of the Flowshop Scheduling problem on a large cluster. The reported results reveal that 50% of strong scaling efficiency is achieved using 400 computer nodes (51,200 processing cores).
Fichier principal
Vignette du fichier
ICCS2024_Helbecque_et_al_preprint.pdf (539.97 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
licence

Dates et versions

hal-04636184 , version 1 (05-07-2024)

Licence

Identifiants

Citer

Guillaume Helbecque, Tiago Carneiro, Nouredine Melab, Jan Gmys, Pascal Bouvry. PGAS Data Structure for Unbalanced Tree-Based Algorithms at Scale. ICCS 2024 - 24th International Conference on Computational Science, Jul 2024, Malaga, Spain. pp.103-111, ⟨10.1007/978-3-031-63759-9_13⟩. ⟨hal-04636184⟩
0 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Mastodon Facebook X LinkedIn More