Technological advances in hardware such as processors, memory, and storage continue to serve as a catalyst for creating larger and more complex software applications that provide a richer user experience by handling many different types of data types of media (e.g., voice, text and video), development programs, and so on.
The hardware support counted on by these vendors in single-processor systems may be distant because historical circuit speedups associated with Moore's law no longer appear to be readily obtainable. The principle aspect of Moore's law is that approximately every eighteen months the number of transistors on a chip will double due, generally, to technological advances in device fabrication. Historically, when this was accomplished, the processor clock speed could also be increased. However, the heat density now associated with the more tightly packed transistors is so high that increasing the clock speed means heat cannot be efficiently and effectively dissipated. Thus, smaller devices no longer directly translate into faster and cooler running machines.
One alternative being exploited is to simply employ more of the devices. In other words, in the realm of processors, for example, design parallel or multi-processor systems to accommodate the software demands. However, parallel processing systems require sophisticated coordination techniques for handling algorithms or computational thread processing. Constraint solving is useful in testing these coordination techniques. Traditional sequential algorithms, however, are notoriously difficult to reconstruct in ways that make effective use of all available shared-memory parallel processors.
Constraint satisfaction problem (CSP) solvers—such as Boolean satisfiability (SAT) solvers—are in no way exceptions to the previous observation. Typically, sequential CSP solvers have a current state that includes a partial solution (an assignment to some of the constraint variables) from which the solver attempts to move to a new state with an augmented solution created by assigning one or more currently unassigned variables. The new assignmentation may engender other assignments through the propagation of constraints. Propagation of constraints, in turn, can lead to the detection of a conflict among the current assignments which (in order to relieve the conflict) must be partially undone, changed to new assignments, and re-propagated.
In parallel processing systems, a parallel implementation of this problem solving regime per force has several parallel computations propagating constraints in the fashion just described. A problem is to merge several conflict-free solver states (post propagation) into a single conflict-free solver state.