Title :
Communication in Parallel Algorithms for Constraint-Based Local Search
Author :
Caniou, Yves ; Codognet, Philippe
Author_Institution :
JFLI, CNRS/NII, Tokyo, Japan
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 transferred. 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.
Keywords :
parallel algorithms; parallel architectures; search problems; constraint solvers; constraint-based local search; multiple-walk algorithm; parallel algorithm; parallel architectures; processors; Approximation methods; Benchmark testing; Computer architecture; Optimization; Program processors; Search problems;
Conference_Titel :
Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on
Conference_Location :
Shanghai
Print_ISBN :
978-1-61284-425-1
Electronic_ISBN :
1530-2075
DOI :
10.1109/IPDPS.2011.357