A Variant of Concurrent Constraint Programming on GPU

[en] The number of cores on graphical computing units (GPUs) is reaching thousands nowadays, whereas the clock speed of processors stagnates. Unfortunately, constraint programming solvers do not take advantage yet of GPU parallelism. One reason is that constraint solvers were primarily designed within the mental frame of sequential computation. To solve this issue, we take a step back and contribute to a simple, intrinsically parallel, lock-free and formally correct programming language based on concurrent constraint programming. We then re-examine parallel constraint solving on GPUs within this formalism, and develop Turbo, a simple constraint solver entirely programmed on GPUs. Turbo validates the correctness of our approach and compares positively to a parallel CPU-based solver.

Research center :

ULHPC - University of Luxembourg: High Performance Computing

Disciplines :

Computer science

Author, co-author :

TALBOT, Pierre ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PCOG

PINEL, Frederic ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

BOUVRY, Pascal ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)

External co-authors :

Language :

English

Title :

A Variant of Concurrent Constraint Programming on GPU

Publication date :

June 2022

Event name :

36th AAAI Conference on Artificial Intelligence

Event date :

from 22-02-2022 to 01-03-2022

Audience :

International

Journal title :

Proceedings of the AAAI Conference on Artificial Intelligence

Volume :

Issue :

Pages :

3830-3839

Peer reviewed :

Peer reviewed

Focus Area :

Computational Sciences

Additional URL :

https://arxiv.org/abs/2207.12116

FnR Project :

FNR16101289 - A Concurrent Model Of Computation For Trustworthy Gpu Programming, 2021 (01/01/2022-31/12/2024) - Pascal Bouvry

Available on ORBilu :

since 01 September 2022

Statistics

Number of views

159 (24 by Unilu)

Number of downloads

58 (9 by Unilu)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

Bibliography

2019. IEEE Standard for Floating-Point Arithmetic. IEEE Std 754-2019 (Revision of IEEE 754-2008). https://doi.org/10.1109/IEEESTD.2019.8766229.
2020. Programming languages-C++. ISO/IEC 14882:2020.
Apt, K. R. 1999. The essence of constraint propagation. Theoretical computer science, 221(1-2): 179-210. https://doi.org/10.1016/S0304-3975(99)00032-8.
Arbelaez, A.; and Codognet, P. 2014. A GPU Implementation of Parallel Constraint-Based Local Search. In 2014 22nd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing, 648-655. Torino, Italy: IEEE. https://doi.org/10.1109/PDP.2014.28.
Bessiere, C.; Hebrard, E.; Hnich, B.; Kiziltan, Z.; and Walsh, T. 2009. Range and Roots: Two common patterns for specifying and propagating counting and occurrence constraints. Artificial Intelligence, 173(11): 1054-1078. https://doi.org/10.1016/j.artint.2009.03.001.
Boehm, H.-J.; and Demsky, B. 2014. Outlawing ghosts: avoiding out-of-thin-air results. In Proceedings of the workshop on Memory Systems Performance and Correctness, 1-6. Edinburgh United Kingdom: ACM. https://doi.org/10.1145/2618128.2618134.
Campeotto, F.; Dal Palu, A.; Dovier, A.; Fioretto, F.; and Pontelli, E. 2014a. Exploring the use of GPUs in constraint solving. In International Symposium on Practical Aspects of Declarative Languages, 152-167. Springer. https://doi.org/10.1007/978-3-319-04132-2.
Campeotto, F.; Dovier, A.; Fioretto, F.; and Pontelli, E. 2014b. A GPU Implementation of Large Neighborhood Search for Solving Constraint Optimization Problems. In European Conference on Artificial Intelligence, 189-194. https://doi.org/10.3233/978-1-61499-419-0-189.
Carlson, B.; Carlsson, M.; and Diaz, D. 1994. Entailment of finite domain constraints. In International Conference on Logic Programming. https://doi.org/10.7551/mitpress/4316.003.0038.
Carlsson, M.; Ottosson, G.; and Carlson, B. 1997. An open-ended finite domain constraint solver. Programming Languages: Implementations, Logics, and Programs. https://doi.org/10.1007/bfb0033845.
Cousot, P. 1977. Asynchronous iterative methods for solving a fixed point system of monotone equations in a complete lattice. Research Report 88, Laboratoire IMAG, Université scientifique et médicale de Grenoble, Grenoble, France.
Cousot, P.; and Cousot, R. 1977a. Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints. In Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, 238-252. ACM. https://doi.org/10.1145/512950.512973.
Cousot, P.; and Cousot, R. 1977b. Automatic Synthesis of Optimal Invariant Assertions: Mathematical Foundations. In Proceedings of the 1977 Symposium on Artificial Intelligence and Programming Languages, 1-12. New York, NY, USA: ACM. https://doi.org/10.1145/872734.806926.
Cousot, P.; Cousot, R.; and Mauborgne, L. 2013. Theories, Solvers and Static Analysis by Abstract Interpretation. Journal of the ACM, 59(6). https://doi.org/10.1145/2395116.2395120.
Davey, B. A.; and Priestley, H. A. 2002. Introduction to lattices and order. Cambridge University Press. https://doi.org/10.1017/cbo9780511809088.
D'Silva, V.; Haller, L.; and Kroening, D. 2014. Abstract satisfaction. In Proceedings of the 41st ACM SIGPLANSIGACT Symposium on Principles of Programming Languages (POPL'14), 139-150. San Diego, California, USA: ACM Press. https://doi.org/10.1145/2535838.2535868.
Fioretto, F.; Pontelli, E.; Yeoh, W.; and Dechter, R. 2018. Accelerating exact and approximate inference for (distributed) discrete optimization with GPUs. Constraints, 23(1): 1-43. https://doi.org/10.1007/s10601-017-9274-1.
Gent, I. P.; Miguel, I.; Nightingale, P.; McCreesh, C.; Prosser, P.; Moore, N. C.; and Unsworth, C. 2018. A review of literature on parallel constraint solving. Theory and Practice of Logic Programming, 18(5-6): 725-758. https://doi.org/10.1017/S1471068418000340.
Gupta, G.; Pontelli, E.; Ali, K. A.; Carlsson, M.; and Hermenegildo, M. V. 2001. Parallel execution of Prolog programs: a survey. ACM Transactions on Programming Languages and Systems (TOPLAS), 23(4): 472-602. https://doi.org/10.1145/504083.504085.
Hamadi, Y.; and Sais, L., eds. 2018. Handbook of Parallel Constraint Reasoning. Cham: Springer International Publishing. https://doi.org/10.1007/978-3-319-63516-3.
Kim, S. K.; Venet, A. J.; and Thakur, A. V. 2020. Deterministic parallel fixpoint computation. Proceedings of the ACM on Programming Languages, 4(POPL): 1-33. https://doi.org/10.1145/3371082.
Kolisch, R.; and Sprecher, A. 1997. PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program. European journal of operational research, 96(1): 205-216. https://doi.org/10.1016/S0377-2217(96)00170-1.
Lee, E. A. 2006. The Problem with Threads. Computer, 39(5): 33-42. https://doi.org/10.1109/MC.2006.180.
Lustig, D.; Sahasrabuddhe, S.; and Giroux, O. 2019. A Formal Analysis of the NVIDIA PTX Memory Consistency Model. In Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, 257-270. Providence RI USA: ACM. https://doi.org/10.1145/3297858.3304043.
Mackworth, A. K. 1977. Consistency in networks of relations. Artificial intelligence, 8(1): 99-118. https://doi.org/10.1016/0004-3702(77)90007-8.
Malapert, A.; Régin, J.-C.; and Rezgui, M. 2016. Embarrassingly Parallel Search in Constraint Programming. Journal of Artificial Intelligence Research, 57: 421-464. https://doi.org/10.1613/jair.5247.
Monette, J.-N.; Flener, P.; and Pearson, J. 2012. Towards Solver-Independent Propagators. In Principles and Practice of Constraint Programming, 544-560. Berlin, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-33558-7_40.
Nagarajan, V.; Sorin, D. J.; Hill, M. D.; and Wood, D. A. 2020. A Primer on Memory Consistency and Cache Coherence, Second Edition. Synthesis Lectures on Computer Architecture, 15(1): 1-294. https://doi.org/10.2200/S00962ED2V01Y201910CAC049.
Narodytska, N. 2011. Reformulation of global constraints. Ph.D. thesis, University of New South Wales, Sydney, Australia.
Nethercote, N.; Stuckey, P. J.; Becket, R.; Brand, S.; Duck, G. J.; and Tack, G. 2007. MiniZinc: Towards a standard CP modelling language. In Principles and Practice of Constraint Programming-CP 2007, 529-543. Springer. https://doi.org/10.1007/978-3-540-74970-7_38.
Ohrimenko, O.; Stuckey, P. J.; and Codish, M. 2009. Propagation via Lazy Clause Generation. Constraints, 14(3): 357-391. https://doi.org/10.1007/s10601-008-9064-x.
Patterson, J. H. 1984. A Comparison of Exact Approaches for Solving the Multiple Constrained Resource, Project Scheduling Problem. Management Science, 30(7): 854-867. https://doi.org/10.1287/mnsc.30.7.854.
Pelleau, M.; Miné, A.; Truchet, C.; and Benhamou, F. 2013. A constraint solver based on abstract domains. In Verification, Model Checking, and Abstract Interpretation, 434-454. Springer. https://doi.org/10.1007/978-3-642-35873-9_26.
Perron, L. 1999. Search procedures and parallelism in constraint programming. In International Conference on Principles and Practice of Constraint Programming, 346-360. Springer. https://doi.org/10.1007/978-3-540-48085-3_25.
Rolf, C. C.; and Kuchcinski, K. 2009. Parallel Consistency in Constraint Programming. In Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2009, 638-644.
Roque, P.; Pedro, V.; Diaz, D.; and Abreu, S. 2018. Improving Constraint Solving on Parallel Hybrid Systems. In 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI), 726-732. IEEE. https://doi.org/10.1109/ICTAI.2018.00114.
Saraswat, V. A. 1993. Concurrent constraint programming. ACM Doctoral dissertation awards. MIT Press. https://doi.org/10.7551/mitpress/2086.001.0001.
Saraswat, V. A.; Rinard, M.; and Panangaden, P. 1991. The Semantic Foundations of Concurrent Constraint Programming. In Proceedings of the 18th ACM SIGPLAN-
SIGACT Symposium on Principles of Programming Languages, POPL'91, 333-352. New York, NY, USA: ACM. https://doi.org/10.1145/99583.99627.
Schulte, C. 1999. Comparing trailing and copying for constraint programming. In In Proceedings of the International Conference on Logic Programming, 275-289. The MIT Press. https://doi.org/10.7551/mitpress/4304.003.0027.
Schulte, C. 2000. Parallel Search Made Simple. In Proceedings of TRICS: Techniques foR Implementing Constraint programming Systems, a post-conference workshop of CP, 41-57.
Schulte, C.; and Stuckey, P. J. 2008. Efficient Constraint Propagation Engines. ACM Trans. Program. Lang. Syst., 31(1): 2:1-2:43. https://doi.org/10.1145/1452044.1452046.
Schulte, C.; Tack, G.; and Lagerkvist, M. 2020. Modeling and Programming with Gecode.
Schutt, A.; Feydy, T.; Stuckey, P. J.; and Wallace, M. G. 2009. Why cumulative decomposition is not as bad as it sounds. In International Conference on Principles and Practice of Constraint Programming, 746-761. Springer. https://doi.org/10.1007/978-3-642-04244-7_58.
Schutt, A.; Feydy, T.; Stuckey, P. J.; and Wallace, M. G. 2013. Solving RCPSP/max by lazy clause generation. Journal of Scheduling, 16(3): 273-289. https://doi.org/10.1007/s10951-012-0285-x.
Tack, G. 2009. Constraint Propagation - Models, Techniques, Implementation. Ph.D. thesis, Saarland University.
Thompson, N. C.; and Spanuth, S. 2021. The Decline of Computers as a General Purpose Technology. Communications of the ACM, 64(3): 64-72. https://doi.org/10.1145/3430936.
Van Hentenryck, P.; Saraswat, V.; and Deville, Y. 1998. Design, implementation, and evaluation of the constraint language cc(FD). The Journal of Logic Programming, 37(1-3): 139-164. http://doi.org/10.1016/S0743-1066(98)10006-7.
Yokoo, M.; and Hirayama, K. 2000. Algorithms for distributed constraint satisfaction: A review. Autonomous Agents and Multi-Agent Systems, 3(2): 185-207. https://doi.org/10.1023/A:1010078712316.