High performance constraint satisfaction problem solving: state-recomputation versus state-copying

Constraint satisfaction problems (CSPs) in artificial intelligence have been an important focus of research and have been a useful model for various applications. Most CSP solving techniques rely on a single processor. With the increasing popularization of multiple processors, parallel search methods are becoming alternatives to speed up search processing. In this paper, we present a forward checking algorithm that solves non-binary CSPs by distributing different branches of the search tree to different processors, i.e., an OR-parallel approach. However, the problem is how to efficiently communicate the state of the search among processors. Two parallel communication models, namely, state-recomputation and state-copying via message passing, are implemented and evaluated. The experimental results demonstrate that when constraints are tight, the state-recomputation model has better performance than the state-copying model, but when constraints are loose, the state-copying model is a better choice.