Decomposition techniques for parallel resolution of constraint satisfaction problems in shared memory: a comparative study. (8th May 2006)

• Record Type: Journal Article
• Authors: Habbas, Zineb; Krajecki, Michael; Singer, Daniel
• Is Part Of: International journal of computational science and engineering. Volume 1:Number 2/3/4(2005)
• Page Start: 192
• Page End: 206
• Publication Date: 2006-05-08
• Subjects: constraint satisfaction problems -- CSP -- decomposition -- OpenMP -- parallel processing -- shared memory -- parallel computing -- backtrack search -- irregularity; Computer science -- Mathematics -- Periodicals; Computer simulation -- Mathematical aspects -- Periodicals; Computational intelligence -- Periodicals; 004.015105
• Languages: English
• ISSNs: 1742-7185

Abstract

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.