Parallel Search in Comet
Comet features high-level abstractions for parallel and distributed computing. The goal is to reduce the distance between sequential and parallel programs for combinatorial optimization in order to leverage the availability of commodity multi-processors or clusters of multi-processors.
Comet offers such abstractions as parallel loops, software interruptions, events, as well as thread pools to provide a natural mapping between the Comet program and the underlying architecture. For distributed computing, Comet features shared (distributed) objects and machine pools. These high-level abstractions are implemented using source-to-source transformations and uses language concepts such as threads and processes and various synchronization primitives (e.g., monitors).
These high-level abstractions make it possible to implement multi-start local search algorithms or hybrid evolutionary algorithms combining a local search and an evolutionary diversification component naturally, keeping the distance between sequential and parallel/distributed programs small.
The abstractions, together with a dedicated but generic search controller, allow for a transparent parallelization of constraint programs using a work-stealing model. The key insight is to replace the search controller of the constraint program (which implements the search strategy) by a parallel controller which alternates between two modes: a search mode in which it solves a particular subproblem using the original controller and a generation mode in which it generates subproblems for other workers. Comet is the first language to support such a complete transparent parallelization of constraint programs.
