Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [5 references]  Display  Hide  Download
Contributor : Danny Munera Connect in order to contact the contributor
Submitted on : Tuesday, February 17, 2015 - 2:13:29 PM
Last modification on : Friday, April 29, 2022 - 10:12:49 AM
Long-term archiving on: : Thursday, May 28, 2015 - 3:47:02 PM


Files produced by the author(s)



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⟩



Record views


Files downloads