{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T21:30:09Z","timestamp":1781386209165,"version":"3.54.1"},"reference-count":48,"publisher":"Oxford University Press (OUP)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,12,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>The AllDifferent constraint is a fundamental tool in Constraint Programming. It naturally arises in many problems, from puzzles to scheduling and routing applications. Such popularity has prompted an extensive literature on filtering and propagation for this constraint. This paper investigates the use of General Processing Units (GPUs) to accelerate filtering and propagation. In particular, the paper presents an efficient parallelization of the AllDifferent constraint on GPU, along with an analysis of different design and implementation choices and evaluation of the performance of the resulting system on several benchmarks.<\/jats:p>","DOI":"10.1093\/logcom\/exad033","type":"journal-article","created":{"date-parts":[[2023,6,8]],"date-time":"2023-06-08T00:24:57Z","timestamp":1686183897000},"page":"1734-1752","source":"Crossref","is-referenced-by-count":3,"title":["Constraint propagation on GPU: A case study for the AllDifferent constraint"],"prefix":"10.1093","volume":"33","author":[{"given":"Fabio","family":"Tardivo","sequence":"first","affiliation":[{"name":"Department of Computer Science, New Mexico State University , Las Cruces, 88003, New Mexico, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Agostino","family":"Dovier","sequence":"additional","affiliation":[{"name":"Department of Math, Computer Science, University of Udine , Udine, 33100, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"Formisano","sequence":"additional","affiliation":[{"name":"Department of Math, Computer Science, University of Udine , Udine, 33100, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laurent","family":"Michel","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Engineering, University of Connecticut , Storrs, Connecticut, 6269-4155, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Enrico","family":"Pontelli","sequence":"additional","affiliation":[{"name":"Department of Computer Science, New Mexico State University , Las Cruces, 88003, New Mexico, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2023,6,6]]},"reference":[{"key":"2023121103255106200_ref1","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1109\/IPDPS.2011.59","article-title":"Computing strongly connected components in parallel on CUDA","volume-title":"In 2011 IEEE International Parallel & Distributed Processing Symposium","author":"Barnat","year":"2011"},{"key":"2023121103255106200_ref2","volume-title":"Graphs and Hypergraphs","author":"Berge","year":"1985"},{"key":"2023121103255106200_ref3","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/978-3-319-04132-2_11","article-title":"Exploring the use of GPUs in constraint solving","volume-title":"Practical Aspects of Declarative Languages","author":"Campeotto","year":"2014"},{"key":"2023121103255106200_ref4","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1080\/0952813X.2014.954274","article-title":"CUD@SAT: SAT solving on GPUs","volume":"27","author":"Dal Pal\u00f9","year":"2014","journal-title":"Journal of Experimental & Theoretical Artificial Intelligence"},{"key":"2023121103255106200_ref5","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1007\/978-3-642-40047-6_84","article-title":"GPU accelerated maximum cardinality matching algorithms for bipartite graphs","volume-title":"Euro-Par 2013 Parallel Processing","author":"Deveci","year":"2013"},{"key":"2023121103255106200_ref6","doi-asserted-by":"crossref","first-page":"905","DOI":"10.1017\/S1471068422000059","article-title":"Parallel logic programming: a sequel","volume":"22","author":"Dovier","year":"2022","journal-title":"Theory and Practice of Logic Programming"},{"key":"2023121103255106200_ref7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1007\/978-3-319-63516-3_7","article-title":"Parallel answer set programming","volume-title":"Handbook of Parallel Constraint Reasoning","author":"Dovier","year":"2018"},{"key":"2023121103255106200_ref8","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1007\/978-3-319-28228-2_3","article-title":"A GPU implementation of the ASP computation","volume-title":"Practical Aspects of Declarative Languages","author":"Dovier","year":"2016"},{"key":"2023121103255106200_ref9","first-page":"3","article-title":"GPU-based parallelism for ASP-solving","volume-title":"Declarative Programming and Knowledge Management, DECLARE 2019, Cottbus, Germany, September 9\u201312, 2019, Revised Selected Papers","author":"Dovier","year":"2019"},{"key":"2023121103255106200_ref10","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1109\/SWAT.1971.4","article-title":"Boolean matrix multiplication and transitive closure","volume-title":"12th Annual Symposium on Switching and Automata Theory (Swat 1971)","author":"Fischer","year":"1971"},{"key":"2023121103255106200_ref11","first-page":"505","article-title":"On identifying strongly connected components in parallel","volume-title":"Lecture Notes in Computer Science","author":"Fleischer","year":"2000"},{"key":"2023121103255106200_ref12","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford","year":"1956","journal-title":"Canadian Journal of Mathematics"},{"key":"2023121103255106200_ref13","doi-asserted-by":"crossref","first-page":"1973","DOI":"10.1016\/j.artint.2008.10.006","article-title":"Generalised arc consistency for the AllDifferent constraint: an empirical survey","volume":"172","author":"Gent","year":"2008","journal-title":"Artificial Intelligence"},{"key":"2023121103255106200_ref14","doi-asserted-by":"crossref","first-page":"725","DOI":"10.1017\/S1471068418000340","article-title":"A review of literature on parallel constraint solving","volume":"18","author":"Gent","year":"2018","journal-title":"Theory and Practice of Logic Programming"},{"key":"2023121103255106200_ref15","doi-asserted-by":"crossref","first-page":"480","DOI":"10.1007\/978-3-540-48085-3_36","article-title":"CSPlib: a benchmark library for constraints","volume-title":"Principles and Practice of Constraint Programming\u2014CP\u201999","author":"Gent","year":"1999"},{"key":"2023121103255106200_ref16","first-page":"531","article-title":"HADDOCK: a language and architecture for decision diagram compilation","volume-title":"Lecture Notes in Computer Science","author":"Gentzel","year":"2020"},{"key":"2023121103255106200_ref17","first-page":"122","article-title":"A n5^\/2 algorithm for maximum matchings in bipartite graphs","volume-title":"12th Annual Symposium on Switching and Automata Theory, East Lansing, Michigan, USA, October 13\u201315, 1971","author":"Hopcroft","year":"1971"},{"key":"2023121103255106200_ref18","first-page":"2310","volume-title":"Review of Serial and Parallel Min-Cut\/Max-Flow Algorithms for Computer Vision","author":"Jensen","year":"2022"},{"key":"2023121103255106200_ref19","article-title":"Engineering boolean matrix multiplication for multiple-accelerator shared-memory architectures","author":"Karppa","year":"2019"},{"key":"2023121103255106200_ref20","first-page":"47","article-title":"All-pairs shortest-paths for large graphs on the GPU","volume-title":"Proceedings of the EUROGRAPHICS\/ACM SIGGRAPH Conference on Graphics Hardware 2008, Sarajevo, Bosnia and Herzegovina, 2008","author":"Katz","year":"2008"},{"key":"2023121103255106200_ref21","volume-title":"Jacop","author":"Kuchcinski","year":"2022"},{"key":"2023121103255106200_ref22","first-page":"1878","article-title":"Accelerating binarized neural networks via bit-tensor-cores in Turing GPUs","volume":"32","author":"Li","year":"2021","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"2023121103255106200_ref23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.sysarc.2013.10.014","article-title":"Efficient decomposition of strongly connected components on GPUs","volume":"60","author":"Li","year":"2014","journal-title":"Journal of Systems Architecture"},{"key":"2023121103255106200_ref24","first-page":"245","article-title":"A fast and simple algorithm for bounds consistency of the alldifferent constraint","volume-title":"IJCAI-03, Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, Acapulco, Mexico, August 9\u201315, 2003","author":"L\u00f3pez-Ortiz","year":"2003"},{"key":"2023121103255106200_ref25","first-page":"145","article-title":"Blocked all-pairs shortest paths algorithm for hybrid CPU-GPU system","volume-title":"In 2011 IEEE International Conference on High Performance Computing and Communications","author":"Matsumoto","year":"2011"},{"key":"2023121103255106200_ref26","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s12532-020-00190-7","article-title":"MiniCP: a lightweight solver for constraint programming","volume":"13","author":"Michel","year":"2021","journal-title":"Mathematical Programming Computation"},{"key":"2023121103255106200_ref27","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1007\/978-3-540-74970-7_38","article-title":"MiniZinc: towards a standard CP modelling language","volume-title":"Principles and Practice of Constraint Programming\u2014CP 2007","author":"Nethercote","year":"2007"},{"key":"2023121103255106200_ref28","volume-title":"Or-Tools","author":"Perron","year":"2022"},{"key":"2023121103255106200_ref29","first-page":"362","article-title":"A filtering algorithm for constraints of difference in CSPs","volume-title":"Proceedings of the Twelfth National Conference on Artificial Intelligence (Vol. 1), AAAI \u201994","author":"R\u00e9gin","year":"1994"},{"key":"2023121103255106200_ref30","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","article-title":"TSPLIB\u2014A traveling salesman problem library","volume":"3","author":"Reinelt","year":"1991","journal-title":"ORSA Journal on Computing"},{"key":"2023121103255106200_ref31","volume-title":"Handbook of Constraint Programming","author":"Rossi","year":"2006"},{"key":"2023121103255106200_ref32","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10601-010-9093-0","article-title":"Philosophy of the MiniZinc challenge","volume":"15","author":"Stuckey","year":"2010","journal-title":"Constraints"},{"key":"2023121103255106200_ref33","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1007\/978-3-031-08011-1_26","article-title":"A parallel algorithm for GAC filtering of the alldifferent constraint","volume-title":"Integration of Constraint Programming, Artificial Intelligence, and Operations Research","author":"Suijlen","year":"2022"},{"key":"2023121103255106200_ref34","volume-title":"Fzn-Minicpp","author":"Tardivo","year":"2022"},{"key":"2023121103255106200_ref35","volume-title":"Minicpp-Benchmarks","author":"Tardivo","year":"2022"},{"key":"2023121103255106200_ref36","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","article-title":"Depth-first search and linear graph algorithms","volume":"1","author":"Tarjan","year":"1972","journal-title":"SIAM Journal on Computing"},{"key":"2023121103255106200_ref37","volume-title":"Gecode","author":"Team Gecode","year":"2022"},{"key":"2023121103255106200_ref38","volume-title":"The MiniZinc Challenge","author":"Team MiniZinc","year":"2022"},{"key":"2023121103255106200_ref39","volume-title":"The MiniZinc Handbook","author":"Team MiniZinc","year":"2022"},{"key":"2023121103255106200_ref40","volume-title":"Cublas","author":"Team NVIDIA","year":"2022"},{"key":"2023121103255106200_ref41","volume-title":"CUDA Toolkit Documentation","author":"Team NVIDIA","year":"2022"},{"key":"2023121103255106200_ref42","doi-asserted-by":"crossref","first-page":"2086","DOI":"10.1007\/s11227-017-2225-1","article-title":"A survey of graph processing on graphics processing units","volume":"74","author":"Tran","year":"2018","journal-title":"The Journal of Supercomputing"},{"key":"2023121103255106200_ref43","volume-title":"The Alldifferent Constraint: A Survey","author":"van Hoeve","year":"2001"},{"key":"2023121103255106200_ref44","first-page":"42","article-title":"Bipartite graph matching computation on GPU","volume-title":"Lecture Notes in Computer Science","author":"Vasconcelos","year":"2009"},{"key":"2023121103255106200_ref45","doi-asserted-by":"crossref","DOI":"10.1145\/996546.996553","article-title":"A blocked all-pairs shortest-paths algorithm","volume":"8","author":"Venkataraman","year":"2003","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"2023121103255106200_ref46","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/321105.321107","article-title":"A theorem on Boolean matrices","volume":"9","author":"Warshall","year":"1962","journal-title":"Journal of the ACM"},{"key":"2023121103255106200_ref47","first-page":"55","article-title":"Efficient CUDA algorithms for the maximum network flow problem","volume-title":"GPU Computing Gems Jade Edition","author":"Jiadong","year":"2012"},{"key":"2023121103255106200_ref48","doi-asserted-by":"crossref","DOI":"10.24963\/ijcai.2018\/194","article-title":"A fast algorithm for generalized arc consistency of the alldifferent constraint","volume-title":"Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence","author":"Zhang","year":"2018"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/8\/1734\/54151390\/exad033.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/33\/8\/1734\/54151390\/exad033.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,11]],"date-time":"2023-12-11T03:26:23Z","timestamp":1702265183000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/33\/8\/1734\/7190989"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,6]]},"references-count":48,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2023,6,6]]},"published-print":{"date-parts":[[2023,12,11]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exad033","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,12]]},"published":{"date-parts":[[2023,6,6]]}}}