Confidence-based Work Stealing in Parallel Constraint Programming

• 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.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

Constraint programming

Depth first search

Dynamic load balancing

Parallel search

Parallel search algorithm

Search trees

Solution density

Subtrees

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)