The paper: Exploring the Use of GPUs in Constraint Solving, by F. Campeotto, A. Dal Palù, A. Dovier, F. Fioretto, and E. Pontelli is accepted in PADL 2014 conference http://www.ist.unomaha.edu/padl2014/ (Springer), San Diego, CA, January 22-23, 2014.
Abstract
This paper presents an experimental study aimed at assessing the feasibility of parallelizing constraint propagation|with particu lar focus on arc-consistency using Graphical Processing Units (GPUs). GPUs support a form of data parallelism that appears to be suitable to the type of processing required to cycle through constraints and domain values during consistency checking and propagation. The paper illustrates an implementation of a constraint solver capable of hybrid propagations (i.e., alternating CPU and GPU), and demonstrates the potential for competitiveness against sequential implementations.