id:"swepub:oai:DiVA.org:kth-70422"
Search: id:"swepub:oai:DiVA.org:kth-70422" > Confidence-based Wo...
- 1 of 1
- Previous record
- Next record
- To hitlist
Confidence-based Work Stealing in Parallel Constraint Programming
- Chu, Geoffrey (author)
-
- Schulte, Christian (author)
- KTH,Programvaru- och datorsystem, SCS
- Stuckey, Peter J. (author)
- (creator_code:org_t)
- Berlin, Heidelberg : Springer Science+Business Media B.V. 2009
- 2009
- English.
- In: Fifteenth International Conference on Principles and Practice of Constraint Programming. - Berlin, Heidelberg : Springer Science+Business Media B.V.. - 9783642042430 - 3642042430 ; , s. 226-241
- Conference paper (peer-reviewed)
Abstract
Subject headings
Close
- The most popular architecture for parallel search is work stealing: threads that have run out of work (nodes to be searched) steal from threads that still have work. Work stealing not only allows for dynamic load balancing, but also determines which parts of the search tree are searched next. Thus the place from where work is stolen has a dramatic effect on the efficiency of a parallel search algorithm. This paper examines quantitatively how optimal work stealing can be performed given an estimate of the relative solution densities of the subtrees at each search tree node and relates it to the branching heuristic strength. An adaptive work stealing algorithm is presented that automatically performs different work stealing strategies based on the confidence of the branching heuristic at each node. Many parallel depth-first search patterns arise naturally from this algorithm. The algorithm produces near perfect or super linear algorithmic efficiencies on all problems tested. Real speedups using 8 threads range from 7 times to super linear.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- Constraint programming
- Depth first search
- Dynamic load balancing
- Parallel search
- Parallel search algorithm
- Search trees
- Solution density
- Subtrees
Publication and Content Type
- ref (subject category)
- kon (subject category)
Find in a library
- Fifteenth International Conference on Principles and Practice of Constraint Prog... (Search for host publication in LIBRIS)
To the university's database
- 1 of 1
- Previous record
- Next record
- To hitlist
Find more in SwePub
- By the author/editor
- Chu, Geoffrey
- Schulte, Christi ...
- Stuckey, Peter J ...
- About the subject
-
- NATURAL SCIENCES
- NATURAL SCIENCES
- and Computer and Inf ...
- and Computer Science ...
- Articles in the publication
- Fifteenth Intern ...
- By the university
- Royal Institute of Technology
Search outside SwePub
- Extend your search to:
- Google Book Search
- Google Scholar
Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.
- Copyright © LIBRIS - National Library Systems
- LIBRIS.kb.se
