Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41101
Title: Scalable distributed depth-first search with greedy work stealing
Authors: Jaffar, J. 
Santosa, A.E. 
Yap, R.H.C. 
Zhu, K.Q. 
Issue Date: 2004
Source: Jaffar, J.,Santosa, A.E.,Yap, R.H.C.,Zhu, K.Q. (2004). Scalable distributed depth-first search with greedy work stealing. Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI : 98-103. ScholarBank@NUS Repository.
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. © 2004 IEEE.
Source Title: Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
URI: http://scholarbank.nus.edu.sg/handle/10635/41101
ISSN: 10823409
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

62
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.