Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Confidence-based Work Stealing in Parallel Constraint Programming
KTH, School of Information and Communication Technology (ICT), Communication: Services and Infrastucture, Software and Computer Systems, SCS.ORCID iD: 0000-0002-6283-7004
2009 (English)In: Fifteenth International Conference on Principles and Practice of Constraint Programming, Springer Science+Business Media B.V., 2009, Vol. 5732, 226-241 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
Springer Science+Business Media B.V., 2009. Vol. 5732, 226-241 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 5732
Keyword [en]
Constraint programming, Depth first search, Dynamic load balancing, Parallel search, Parallel search algorithm, Search trees, Solution density, Subtrees
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-70422DOI: 10.1007/978-3-642-04244-7_20ISI: 000273241200017Scopus ID: 2-s2.0-70350393893ISBN: 978-364204243-0 ISBN: 3642042430 (print)OAI: oai:DiVA.org:kth-70422DiVA: diva2:486347
Conference
15th International Conference on Principles and Practice of Constraint Programming (CP 2009), Lisbon, PORTUGAL, SEP 20-24, 2009
Note
QC 20120207Available from: 2012-01-30 Created: 2012-01-30 Last updated: 2012-02-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopushttp://www.ict.kth.se/~cschulte/paper.php?id=ChuSchulteStuckey:CP:2009

Authority records BETA

Schulte, Christian

Search in DiVA

By author/editor
Schulte, Christian
By organisation
Software and Computer Systems, SCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 34 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf