Communication in Parallel Algorithms for Constraint-Based Local Search

Abstract : We address the issue of parallelizing constraint solvers based on local search methods for massively parallel architectures, involving several thousands of CPUs. We present a family of a constraint-based local search algorithms and investigate their performance results on hardwares with several hundreds of processors. The first method is a basic independent multiple-walk algorithm: each processor runs a local search starting from a distinct initial configuration and the first one which will reach a solution will notify the others and stop all computations. These simple methods have good performances, and good speedups can be achieved up to a few hundreds of processors. Then we consider 2 versions with communication between processors: 1) every $c$ iterations, each processor sends the current value (cost) of its configuration to others and a processor who received a better cost from another processor can decide to stop its current search with a probability $p$; 2) the number of iterations corresponding to the cost is also transfered. Both the received cost and the number of iterations have to be better for a processor to decide to draw a probability and restart. Several experiments involving more than 100 processors have been conducted and different values of $p$ have been tried to consider more or less "autistic" processors. However results show that it is very difficult to achieve better performance than the initial method without communication.
Type de document :
Communication dans un congrès
PCO - IEEE Workshop on new trends in Parallel Computing and Optimization in conjonction with IPDPS, May 2011, Anchorage, United States. 2011
Liste complète des métadonnées

https://hal.inria.fr/hal-00751702
Contributeur : Yves Caniou <>
Soumis le : mercredi 14 novembre 2012 - 09:29:12
Dernière modification le : mardi 24 avril 2018 - 13:52:36

Identifiants

  • HAL Id : hal-00751702, version 1

Collections

Citation

Yves Caniou, Philippe Codognet. Communication in Parallel Algorithms for Constraint-Based Local Search. PCO - IEEE Workshop on new trends in Parallel Computing and Optimization in conjonction with IPDPS, May 2011, Anchorage, United States. 2011. 〈hal-00751702〉

Partager

Métriques

Consultations de la notice

182