An Incremental Parallel PGAS-based Tree Search Algorithm

Carneiro, Tiago; Melab, Nouredine

Type de document :

Communication dans un congrès avec actes

Titre :

An Incremental Parallel PGAS-based Tree Search Algorithm

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]

Titre de la manifestation scientifique :

HPCS 2019 - International Conference on High Performance Computing & Simulation

Ville :

Dublin

Pays :

Irlande

Date de début de la manifestation scientifique :

2019-07-15

Mot(s)-clé(s) en anglais :

Tree Search Algorithms
MPI+OpenMP
Chapel
PGAS
High-productivity Language

Discipline(s) HAL :

Informatique [cs]/Calcul parallèle, distribué et partagé [cs.DC]

Résumé en anglais : [en]

In this work, we show that the Chapel high-productivity language is suitable for the design and implementation of all aspects involved in the conception of parallel tree search algorithms for solving combinatorial problems. ...
Lire la suite >In this work, we show that the Chapel high-productivity language is suitable for the design and implementation of all aspects involved in the conception of parallel tree search algorithms for solving combinatorial problems. Initially, it is possible to hand-optimize the data structures involved in the search process in a way equivalent to C. As a consequence, the single-threaded search in Chapel is on average only 7% slower than its counterpart written in C. Whereas programming a multicore tree search in Chapel is equivalent to C-OpenMP in terms of performance and programmability, its productivity-aware features for distributed programming stand out. It is possible to incrementally conceive a distributed tree search algorithm starting from its multicore counterpart by adding few lines of code. The distributed implementation performs load balancing among different computer nodes and also exploits all CPU cores of the system. Chapel presents an interesting trade-off between programmability and performance despite the high level of its features. The distributed tree search in Chapel is on average 16% slower and reaches up to 80% of the scalability achieved by its C-MPI+OpenMP counterpart.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.archives-ouvertes.fr/hal-02170842/document
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-02170842/document
Accès libre
Accéder au document

https://hal.archives-ouvertes.fr/hal-02170842/document
Accès libre
Accéder au document

document
Accès libre
Accéder au document

HPCS.pdf
Accès libre
Accéder au document

An Incremental Parallel PGAS-based Tree ... BibTeX CSV Excel RIS

Fichiers

An Incremental Parallel PGAS-based Tree ...

BibTeX

CSV

Excel

RIS