Decomposition techniques for parallel resolution of constraint satisfaction problems in shared memory: a comparative study. (8th May 2006) - Habbas, Zineb; Krajecki, Michael; Singer, Daniel
This paper provides both a formal and an empirical study of decomposition techniques for parallel resolution of Constraint Satisfaction Problems (CSP) in shared memory. The main contribution of this study is to bring together decomposition techniques with Backtrack search to solve CSP on parallel architectures in shared memory. Another contribution is to demonstrate how to obtain good scalability up to hundreds of processors in shared memory for CSP resolution and more generally for Irregular Applications.