Confidence based Work Stealing
Geoffrey Chu, Christian Schulte, Peter J. Stuckey.
In parallel constraint solving, 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. In this paper we examine quantitatively how optimal work stealing can be performed given an estimate of the relative solution densities of the subtrees at each node in the search tree and show how this is related to the branching heuristic strength. We propose an adaptive work stealing algorithm that automatically performs different work stealing strategies based on the strength of the branching heuristic at each node. Search patterns such as parallel versions of DFS, IDFS, LDS, DDS and many others arise naturally from our algorithm. Our algorithm is able to produce near perfect or super linear algorithmic efficiencies on all problems tested. Real speedups using 8 threads ranged from 4-5 times speedup to super linear speedup.
In: Manuel Carro, Bart Demoen, editors, Proceedings of the Eigth International Colloquium on Implementation of Constraint and Logic Programming Systems, Udine, Italy. December, 2008.