Paper Info
Title
Scalable Distributed Depth-First Search with Greedy Work Stealing
Abstract
We present a framework for the parallelization of depth-first combinatorial search algorithms on a network of computers. Our architecture is intended for a distributed setting and uses a work stealing strategy coupled with a small number of primitives for the processors (which we call workers) to obtain new work and to communicate to other workers. These primitives are a minimal imposition and integrate easily with constraint programming systems. The main contribution is an adaptive architecture which allows workers to incrementally join and leave and has good scaling properties as the number of workers increases. Our empirical results illustrate that near-linear speedup for backtrack search is achieved for up to 61 workers. It suggests that near-linear speedup is possible with even more workers. The experiments also demonstrate where departures from linearity can occur for small problems, and also for problems where the parallelism can itself affect the search as in branch and bound.
Year
DOI
Venue
2004
10.1109/ICTAI.2004.107
ICTAI
Keywords
Field
DocType
empirical result,new work,greedy work stealing,depth-first search,constraint programming system,small problem,adaptive architecture,backtrack search,workers increase,near-linear speedup,small number,depth-first combinatorial search algorithm,constraint programming,parallel algorithms,backtracking,search algorithm,branch and bound,depth first search,greedy algorithms,linear programming
Branch and bound,Computer science,Constraint programming,Breadth-first search,Greedy algorithm,Theoretical computer science,Work stealing,Artificial intelligence,Combinatorial search,Backtracking,Machine learning,Speedup
Conference
ISSN
ISBN
Citations 
1082-3409
0-7695-2236-X
9
PageRank 
References 
Authors
0.69
8
4
Name
Order
Citations
PageRank
Joxan Jaffar12350283.50
Andrew Santosa214613.36
Roland H. C. Yap31187133.09
Kenny Qili Zhu440039.16