Exploring the use of GPUs in constraint solving

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

doi:10.1007/978-3-319-04132-2_11

Exploring the use of GPUs in constraint solving

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

Research output: Chapter in Book/Entry/Poem › Conference contribution

25 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 language	English (US)
Title of host publication	Practical Aspects of Declarative Languages - 16th International Symposium, PADL 2014, Proceedings
Pages	152-167
Number of pages	16
DOIs	https://doi.org/10.1007/978-3-319-04132-2_11
State	Published - 2014
Externally published	Yes
Event	15th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2014 - San Diego, CA, United States Duration: Jan 20 2014 → Jan 21 2014

Publication series

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

Conference

Conference	15th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2014
Country/Territory	United States
City	San Diego, CA
Period	1/20/14 → 1/21/14

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-04132-2_11

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

Exploring the use of GPUs in constraint solving. / Campeotto, Federico; Dal Palù, Alessandro; Dovier, Agostino et al.
Practical Aspects of Declarative Languages - 16th International Symposium, PADL 2014, Proceedings. 2014. p. 152-167 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8324 LNCS).

Research output: Chapter in Book/Entry/Poem › Conference contribution

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8324 LNCS, pp. 152-167, 15th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2014, San Diego, CA, United States, 1/20/14. https://doi.org/10.1007/978-3-319-04132-2_11

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

Campeotto, Federico ; Dal Palù, Alessandro ; Dovier, Agostino et al. / Exploring the use of GPUs in constraint solving. Practical Aspects of Declarative Languages - 16th International Symposium, PADL 2014, Proceedings. 2014. pp. 152-167 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{578356a70d7f43ecb1bc260a9ef37517,

title = "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.",

author = "Federico Campeotto and {Dal Pal{\`u}}, Alessandro and Agostino Dovier and Ferdinando Fioretto and Enrico Pontelli",

year = "2014",

doi = "10.1007/978-3-319-04132-2_11",

language = "English (US)",

isbn = "9783319041315",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "152--167",

booktitle = "Practical Aspects of Declarative Languages - 16th International Symposium, PADL 2014, Proceedings",

note = "15th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2014 ; Conference date: 20-01-2014 Through 21-01-2014",

}

TY - GEN

T1 - Exploring the use of GPUs in constraint solving

AU - Campeotto, Federico

AU - Dal Palù, Alessandro

AU - Dovier, Agostino

AU - Fioretto, Ferdinando

AU - Pontelli, Enrico

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84893517838&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893517838&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-04132-2_11

DO - 10.1007/978-3-319-04132-2_11

M3 - Conference contribution

AN - SCOPUS:84893517838

SN - 9783319041315

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 152

EP - 167

BT - Practical Aspects of Declarative Languages - 16th International Symposium, PADL 2014, Proceedings

T2 - 15th International Conference on Verification, Model Checking, and Abstract Interpretation, VMCAI 2014

Y2 - 20 January 2014 through 21 January 2014

ER -

Exploring the use of GPUs in constraint solving

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this