A Local Search for Automatic Parameterization of Distributed Tree Search Algorithms

Carneiro, Tiago; Koutsantonis, Loizos; Melab, Nouredine; Kieffer, Emmanuel; Bouvry, Pascal

Document type :

Autre communication scientifique (congrès sans actes - poster - séminaire...): Communication dans un congrès avec actes

Title :

A Local Search for Automatic Parameterization of Distributed Tree Search Algorithms

Author(s) :

Carneiro, Tiago [Auteur]
Université du Luxembourg [Uni.lu]
Koutsantonis, Loizos [Auteur]
Université du Luxembourg [Uni.lu]
Melab, Nouredine [Auteur]

Optimisation de grande taille et calcul large échelle [BONUS]
Kieffer, Emmanuel [Auteur]
Université du Luxembourg [Uni.lu]
Bouvry, Pascal [Auteur]
Université du Luxembourg [Uni.lu]

Conference title :

PDCO 2022 - 12th IEEE Workshop Parallel / Distributed Combinatorics and Optimization

City :

Lyon

Country :

France

Start date of the conference :

2022-05-30

English keyword(s) :

Parallel tree-based search
Combinatorial optimization
Parameter configuration
High-productivity languages
Chapel

HAL domain(s) :

Informatique [cs]

English abstract : [en]

Tree-based search algorithms applied to combinatorial optimization problems are highly irregular and timeconsuming when solving instances of NP-Hard problems. Due to their parallel nature, algorithms for this class of ...
Show more >Tree-based search algorithms applied to combinatorial optimization problems are highly irregular and timeconsuming when solving instances of NP-Hard problems. Due to their parallel nature, algorithms for this class of complexity have been revisited for different architectures over the years. However, parallelization efforts have always been guided by the performance objective setting aside productivity. Using Chapel's high productivity for the design and implementation of distributed tree search algorithms keeps the programmer from lower-level details, such as communication and load balancing. However, the parameterization of such parallel applications is complex, consisting of several parameters, even if a high-productivity language is used in their conception. This work presents a local search for automatic parameterization of ChapelBB, a distributed tree search application for solving combinatorial optimization problems written in Chapel. The main objective of the proposed heuristic is to overcome the limitation of manual parameterization, which covers a limited feasible space. The reported results show that the heuristic-based parameterization increases up to 30% the performance of ChapelBB on 2048 cores (4096 threads) solving the N-Queens problem and up to 31% solving instances of the Flow-shop scheduling problem to the optimality.Show less >

Language :

Anglais

Peer reviewed article :

Oui

Audience :

Internationale

Popular science :

Non

Collections :

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

Source :

Harvested from HAL

Files

https://hal.archives-ouvertes.fr/hal-03619760/document
Open access
Access the document

https://hal.archives-ouvertes.fr/hal-03619760/document
Open access
Access the document

https://hal.archives-ouvertes.fr/hal-03619760/document
Open access
Access the document

A Local Search for Automatic Parameterization ... BibTeX CSV Excel RIS

Files

A Local Search for Automatic Parameterization ...

BibTeX

CSV

Excel

RIS