Flexible cooperation in parallel local search (extended abstract)

Abstract : Constraint-Based Local Search (CBLS) consist in using Local Search methods [4] for solving Constraint Satisfac- tion Problems (CSP). In order to further improve the per- formance of Local Search, one possible option is to take advantage of the increasing availability of parallel compu- tational resources. Parallel implementation of local search meta-heuristics has been studied since the early 90’s, when multiprocessor machines started to become widely available, see [6]. One usually distinguishes between single-walk and multiple-walk methods: Single-walk methods consist in us- ing parallelism inside a single search process, e.g. for paral- lelizing the exploration of the neighborhood, while multiple- walk methods (also called multi-start methods) consist in de- veloping concurrent explorations of the search space, either independently (IW) or cooperatively (CW) with some com- munication between concurrent processes. Although good results can be achieved just with IW [1], a more sophisticated paradigm featuring cooperation between independent walks should bring better performance. We thus propose a gen- eral framework for cooperative search, which defines a flexi- ble and parametric strategy based on the cooperative multi- walk (CW) scheme. The framework is oriented towards dis- tributed architectures based on clusters of nodes, with the notion of “teams” running on nodes which group several in- dividual search engines (e.g. multicore nodes). The idea is that teams are distributed and thus have limited inter-node communication. This framework allows the programmer to define aspects such as the degree of intensification and di- versification present in the parallel search process. A good trade-off is essential to reach high performance. A prelimi- nary implementation of the general CW framework has been done in the X10 programming language [5], and performance evaluation over a set of well-known benchmark CSPs shows that CW consistently outperforms IW.
Type de document :
Communication dans un congrès
ACM Symposium on Applied Computing (SAC), Mar 2014, Gyeongju, South Korea. pp.1360 - 1361, 2014, 〈10.1145/2554850.2555140〉
Liste complète des métadonnées

Littérature citée [5 références]  Voir  Masquer  Télécharger

https://hal-paris1.archives-ouvertes.fr/hal-01117539
Contributeur : Danny Munera <>
Soumis le : mardi 17 février 2015 - 14:13:29
Dernière modification le : mercredi 21 mars 2018 - 18:57:49
Document(s) archivé(s) le : jeudi 28 mai 2015 - 15:47:02

Fichier

sac14-ncr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Danny Munera, Daniel Diaz, Salvador Abreu, Philippe Codognet. Flexible cooperation in parallel local search (extended abstract). ACM Symposium on Applied Computing (SAC), Mar 2014, Gyeongju, South Korea. pp.1360 - 1361, 2014, 〈10.1145/2554850.2555140〉. 〈hal-01117539〉

Partager

Métriques

Consultations de la notice

104

Téléchargements de fichiers

89