Exploring the use of GPUs in constraint solving

Abstract

This paper presents an experimental study aimed at assessing the feasibility of parallelizing constraint propagation - with particular 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. © 2014 Springer International Publishing.

Publication
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Date
Links