Flexible cooperation in parallel local search (extended abstract) - Archive ouverte HAL Access content directly
Conference Papers Year : 2014

Flexible cooperation in parallel local search (extended abstract)

(1) , (1) , (2) , (3, 4)
1
2
3
4

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.
Fichier principal
Vignette du fichier
sac14-ncr.pdf (181.7 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01117539 , version 1 (17-02-2015)

Identifiers

Cite

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, ⟨10.1145/2554850.2555140⟩. ⟨hal-01117539⟩
96 View
156 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More