Title: Decomposition techniques for parallel resolution of constraint satisfaction problems in shared memory: a comparative study

Authors: Zineb Habbas, Michael Krajecki, Daniel Singer

Addresses: Universite Paul Verlaine de Metz, LITA, EA 3097, Ile du Saulcy, F 57 045 Metz Cedex, France. ' CReSTIC, EA 3804, Universite de Reims Champagne-Ardenne, Moulin de la Housse, BP 1039, F51687 Reims Cedex 2, France. ' Universite Paul Verlaine de Metz, LITA, EA 3097, Ile du Saulcy, F 57 045 Metz Cedex, France

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.

Keywords: constraint satisfaction problems; CSP; decomposition; OpenMP; parallel processing; shared memory; parallel computing; backtrack search; irregularity.

DOI: 10.1504/IJCSE.2005.009703

International Journal of Computational Science and Engineering, 2005 Vol.1 No.2/3/4, pp.192 - 206

Published online: 05 May 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article