Exploring the use of GPUs in constraint solving

Federico Campeotto, Alessandro Dal Palù, Agostino Dovier, Ferdinando Fioretto, Enrico Pontelli

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationPractical Aspects of Declarative Languages - 16th International Symposium, PADL 2014, Proceedings
Pages152-167
Number of pages16
DOIs
StatePublished - 2014
Event15th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2014 - San Diego, CA, United States
Duration: Jan 20 2014Jan 21 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8324 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2014
CountryUnited States
CitySan Diego, CA
Period1/20/141/21/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Exploring the use of GPUs in constraint solving'. Together they form a unique fingerprint.

  • Cite this

    Campeotto, F., Dal Palù, A., Dovier, A., Fioretto, F., & Pontelli, E. (2014). Exploring the use of GPUs in constraint solving. In Practical Aspects of Declarative Languages - 16th International Symposium, PADL 2014, Proceedings (pp. 152-167). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8324 LNCS). https://doi.org/10.1007/978-3-319-04132-2_11