Programming model

BS-Solve has been designed for the explicit cooperation and parallelization of constraint solvers. It uses the BSP (bulk-synchronous processing) paradigm of parallel programming: computation alternates between p independent computations and global operations, where p is the number of available processors. The resulting system called BS-Solve is available as a library called from KLIC programs and where existing sequential solvers can be re-used.

The BSP realization of a set of concurrent-cooperating parallel solvers uses the following correspondences.

1. Resolution strategies are written as computation phases (or supersteps) of p independent sequential computations. Each one is driven by an agent. An agent is either an existing solver or a program issuing calls to the BS-Solve system.
2. Cooperation strategies are written as so-called contractions and expansions, alternating with computation phases. These operations trigger all the communications and synchronizations in global (bulk-synchronous) mode. In other words, no subset of the network may communicate or synchronise without global synchronization. The global communication event may not relate every node to every other one. Any subset of the complete P x P communication graph is allowed.