Confidence-based work stealing in parallel constraint programming

Geoffrey Chu, Christian Schulte, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

54 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming - CP 2009 - 15th International Conference, CP 2009, Proceedings
PublisherSpringer
Pages226-241
Number of pages16
ISBN (Print)3642042430, 9783642042430
DOIs
Publication statusPublished - 2 Nov 2009
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2009 - Lisbon, Portugal
Duration: 22 Sep 200924 Sep 2009
Conference number: 15th
https://link.springer.com/book/10.1007%2F978-3-642-04244-7 (Conference Proceedings)

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5732 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2009
Abbreviated titleCP 2009
CountryPortugal
CityLisbon
Period22/09/0924/09/09
Internet address

Cite this