Transparent Parallelization of Constraint Programming
Laurent Michel, Andrew See, Pascal Van Hentenryck
INFORMS Journal on Computing · 2009 · Volume 21 · Issue 3
Abstract
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.
Keywords
constraint programming, parallel computing, distributed computing, programming languages
Enable JavaScript for citation tools and additional paper interactions.