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.
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-paris1.archives-ouvertes.fr/hal-01117539
Contributor : Danny Munera <>
Submitted on : Tuesday, February 17, 2015 - 2:13:29 PM
Last modification on : Friday, September 27, 2019 - 12:16:02 PM
Long-term archiving on : Thursday, May 28, 2015 - 3:47:02 PM

File

sac14-ncr.pdf
Files produced by the author(s)

Identifiers

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

Share

Metrics

Record views

146

Files downloads

152