Loading...
Please wait, while we are loading the content...
Similar Documents
Parallelizing constraint programs
| Content Provider | ACM Digital Library |
|---|---|
| Author | Michel, Laurent D. |
| Abstract | The availability of commodity multicore and multiprocessor machines and the inherent parallelism in constraint programming search offer significant opportunities for constraint programming. Both constraint-based local search and finite-domain techniques can dramatically benefit from parallelization. Yet, currently available libraries and languages offer very limited support to exploit the inherent parallelism and the high human cost incurred to develop parallel solutions confine programmers to sequential implementation. The fundamental challenge boils down to: how to exploit parallelism transparently to speed up constraint programs. This talk shows how to parallelize constraint programs (both constraint-based local search and finite-domain programs) transparently with minimal changes to the code and illustrates all the ideas with the COMET platform. Constraint-Based local search programs written in COMET separate the specification of the constraints from the specification of the search and meta-heuristics. While multi-start search strategies, heterogeneous neighborhood structures and population based meta-heuristics offer a bounty of opportunities, the efficient parallel implementation is typically intrusive and requires significant changes to the models. The parallel linguistic extensions of COMET side step the issue and allow programmers to trivially move from a sequential to a parallel and possibly distributed implementation with minimal changes to their programs. Empirical results demonstrate that the parallel COMET program deliver excellent speedups for negligible investments. Constraint programs expressed with COMET adopt the mantra that search is the combination of a non-deterministic program and a search controller devoted to the management of the adopted search strategy. Automatic parallelization further exploits this separation to transparently capture, share, steal and execute sub problems in parallel. The techniques not only apply to multicore architectures but scale to distributed settings. Specifically, the technical contributions include new control primitives for parallel loops, pools of threads, asynchronous events and the systematic use of functional closures and continuations. Experimental results show that the parallel implementation often produces significant speedups on multi-core machines. |
| Starting Page | 3 |
| Ending Page | 4 |
| Page Count | 2 |
| File Format | |
| ISBN | 9781605588599 |
| DOI | 10.1145/1708046.1708050 |
| Language | English |
| Publisher | Association for Computing Machinery (ACM) |
| Publisher Date | 2010-01-19 |
| Publisher Place | New York |
| Access Restriction | Subscribed |
| Subject Keyword | Parallel programming Constraint programming Constraint-based local search |
| Content Type | Text |
| Resource Type | Article |
