This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Michel, L. Articles by Van Hentenryck, P.

Transparent Parallelization of Constraint Programming

Computer Science and Engineering, University of Connecticut, Storrs, Connecticut 06269
Computer Science and Engineering, University of Connecticut, Storrs, Connecticut 06269
Brown University, Providence, Rhode Island 02912
ldm{at}engr.uconn.edu
andysee{at}engr.uconn.edu
pvh{at}cs.brown.edu

The availability of commodity multicore and multiprocessor machines and the inherent parallelism in constraint programming search offer significant opportunities for constraint programming. These opportunities also present a fundamental challenge: how to exploit parallelism transparently to speed up constraint programs. This paper shows how to parallelize constraint programs transparently without changes to the sequential code. The main technical idea consists of automatically lifting a sequential exploration strategy into its parallel counterpart, allowing workers to share and steal subproblems. Experimental results show that the parallel implementation may produce significant speedups on multicore machines.

Key words: constraint programming; parallel computing; distributed computing; programming languages
History: received October 2007; revised June 2008; accepted July 2008.