Title :

Towards ultra-scale Branch-and-Bound using a high-productivity language

Author(s) :

Carneiro, Tiago [Auteur correspondant]
Optimisation de grande taille et calcul large échelle [BONUS]
Gmys, Jan [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Melab, Nouredine [Auteur]
Optimisation de grande taille et calcul large échelle [BONUS]
Tuyttens, Daniel [Auteur]
Université de Mons / University of Mons [UMONS]

Journal title :

Future Generation Computer Systems
SI: On The Road to Exascale II: Advances on High Performance Computing and Simulations

Pages :

196-209

Publisher :

Elsevier

Publication date :

2020-04

ISSN :

0167-739X

English keyword(s) :

Ultra-scale optimization
Branch-and-Bound
PGAS
Chapel
MPI+X

HAL domain(s) :

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

English abstract : [en]

Due to the highly irregular nature and prohibitive execution times of Branch-and-Bound (B&B) algorithms applied to combinatorial optimization problems (COPs), their parallelization has received these two last decades great ...
Show more >Due to the highly irregular nature and prohibitive execution times of Branch-and-Bound (B&B) algorithms applied to combinatorial optimization problems (COPs), their parallelization has received these two last decades great attention. Indeed, significant efforts have been made to revisit the parallelization of B&B following the rapid evolution of high-performance computing technologies dealing with their associated scientific and technical challenges. However, these parallelization efforts have always been guided by the performance objective setting aside programming productivity. Nevertheless, this latter is crucial for designing ultra-scale algorithms able to harness modern supercomputers which are increasingly complex, including millions of processing cores and heterogeneous building-block devices. In this paper, we investigate the partitioned global address space (PGAS)-based approach using Chapel for the productivity-aware design and implementation of distributed B&B for solving large COPs. The proposed algorithms are intensively experimented using the Flow-shop scheduling problem as a test-case. The Chapel-based implementation is compared to its MPI+X-based traditionally used counterpart in terms of performance, scalabil-ity, and productivity. The results show that Chapel is much more expressive and up to 7.8× more productive than MPI+Pthreads. In addition, the Chapel-based search presents performance equivalent to MPI+Pthreads for its best results on 1024 cores and reaches up to 84% of the linear speedup. However, there are cases where the built-in load balancing provided by Chapel cannot produce regular load among computer nodes. In such cases, the MPI-based search can be up to 4.2× faster and reaches speedups up to 3× higher than its Chapel-based counterpart. Thorough feedback on the experience is given, pointing out the strengths and limitations of the two opposite approaches (Chapel vs. MPI+X). To the best of our knowledge, the present study is pioneering within the context of exact parallel optimization.Show less >

Language :

Anglais

Popular science :

Non

Collections :

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

Source :

Harvested from HAL