{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T09:06:54Z","timestamp":1762938414522,"version":"3.45.0"},"reference-count":37,"publisher":"Wiley","issue":"25-26","license":[{"start":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T00:00:00Z","timestamp":1759363200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR\u201022\u2010CE46\u20100011"],"award-info":[{"award-number":["ANR\u201022\u2010CE46\u20100011"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001866","name":"Fonds National de la Recherche Luxembourg","doi-asserted-by":"publisher","award":["INTER\/ANR\/22\/17133848","C22\/IS\/17395419"],"award-info":[{"award-number":["INTER\/ANR\/22\/17133848","C22\/IS\/17395419"]}],"id":[{"id":"10.13039\/501100001866","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Concurrency and Computation"],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:title>ABSTRACT<\/jats:title>\n                  <jats:p>The Branch\u2010and\u2010Bound (B&amp;B) technique plays a key role in solving many combinatorial optimization problems, enabling efficient problem\u2010solving and decision\u2010making in a wide range of applications. It incrementally constructs a tree by building candidates to the solutions and abandoning a candidate as soon as it determines that it cannot lead to an optimal solution. With modern problems growing increasingly large, accelerating B&amp;B algorithms through parallelization has become a critical challenge for handling large solution spaces. At the same time, modern parallel computing systems themselves are becoming larger, more heterogeneous, and more diverse, requiring programming approaches capable of effectively exploiting such complexity. To address these challenges, this work presents a GPU\u2010accelerated B&amp;B algorithm based on the Partitioned Global Address Space (PGAS) programming model, implemented using the Chapel language. The PGAS\u2010based design is motivated by the high\u2010level abstraction provided by this programming model, which favors programmability, whereas vendor\u2010neutral GPU features of the Chapel language favor GPU portability. The algorithm uses a pool\u2010based approach for generality and exploits a dynamic load balancing mechanism for performance scalability. Extensive experimentation on the N\u2010Queens and permutation flowshop scheduling problems demonstrated both code performance and code portability of the proposed algorithm on several GPU architectures compared to optimized CUDA\u2010based implementations. Moreover, the strong scaling efficiency of the proposed algorithm is investigated on a TOP500 pre\u2010exascale supercomputer up to 1024 GPUs.<\/jats:p>","DOI":"10.1002\/cpe.70321","type":"journal-article","created":{"date-parts":[[2025,10,3]],"date-time":"2025-10-03T00:01:12Z","timestamp":1759449672000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Portable\n                    <scp>PGAS<\/scp>\n                    \u2010Based\n                    <scp>GPU<\/scp>\n                    \u2010Accelerated Branch\u2010And\u2010Bound Algorithms at Scale"],"prefix":"10.1002","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8697-3721","authenticated-orcid":false,"given":"Guillaume","family":"Helbecque","sequence":"first","affiliation":[{"name":"University of Luxembourg, DCS\u2010FSTM\/SnT  Esch\u2010sur\u2010Alzette Luxembourg"},{"name":"Universit\u00e9 de Lille, CNRS\/CRIStAL UMR 9189, Centre Inria de l'Universit\u00e9 de Lille  Lille France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1971-4973","authenticated-orcid":false,"given":"Ezhilmathi","family":"Krishnasamy","sequence":"additional","affiliation":[{"name":"University of Luxembourg, DCS\u2010FSTM\/SnT  Esch\u2010sur\u2010Alzette Luxembourg"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6145-8352","authenticated-orcid":false,"given":"Tiago","family":"Carneiro","sequence":"additional","affiliation":[{"name":"Interuniversity Microelectronics Centre (IMEC)  Leuven Belgium"}]},{"given":"Nouredine","family":"Melab","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Lille, CNRS\/CRIStAL UMR 9189, Centre Inria de l'Universit\u00e9 de Lille  Lille France"}]},{"given":"Pascal","family":"Bouvry","sequence":"additional","affiliation":[{"name":"University of Luxembourg, DCS\u2010FSTM\/SnT  Esch\u2010sur\u2010Alzette Luxembourg"}]}],"member":"311","published-online":{"date-parts":[[2025,10,2]]},"reference":[{"key":"e_1_2_12_2_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.6.1042"},{"key":"e_1_2_12_3_1","unstructured":"TOP500.org \u201cTOP500 the List (June 2025) \u201dhttps:\/\/www.top500.org\/lists\/top500\/2025\/06\/."},{"key":"e_1_2_12_4_1","first-page":"1539","volume-title":"Encyclopedia of Parallel Computing","author":"Almasi G.","year":"2011"},{"key":"e_1_2_12_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-90200-0_37"},{"key":"e_1_2_12_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.01.039"},{"key":"e_1_2_12_7_1","unstructured":"N.Melab \u201cContributions \u00e0 la R\u00e9solution de Probl\u00e8mes D'optimisation Combinatoire Sur Grilles de Calcul. Universit\u00e9 Des Sciences et Technologies de Lille. Th\u00e8se HDR \u201d(2005)."},{"key":"e_1_2_12_8_1","first-page":"618","volume-title":"APCCAS 2008\u20132008 IEEE Asia Pacific Conference on Circuits and Systems","author":"Wu E. H.","year":"2008"},{"key":"e_1_2_12_9_1","first-page":"747","volume-title":"IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW)","author":"Dabah A.","year":"2016"},{"key":"e_1_2_12_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.2022.1193"},{"key":"e_1_2_12_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2015.10.009"},{"key":"e_1_2_12_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW.2012.219"},{"key":"e_1_2_12_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4954"},{"key":"e_1_2_12_14_1","first-page":"160","volume-title":"In Australasian Conference on Information Security and Privacy","author":"Yeoh W. Z.","year":"2020"},{"key":"e_1_2_12_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11227\u2010016\u20101784\u2010x"},{"key":"e_1_2_12_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2345054"},{"key":"e_1_2_12_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14390-8_47"},{"key":"e_1_2_12_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2013.6799105"},{"key":"e_1_2_12_19_1","first-page":"41","volume-title":"Proceedings of the 2011 23rd International Symposium on Computer Architecture and High Performance Computing","author":"Carneiro T.","year":"2011"},{"key":"e_1_2_12_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2013.07.023"},{"key":"e_1_2_12_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.4019"},{"key":"e_1_2_12_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-19595-2_11"},{"key":"e_1_2_12_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2212736.2212744"},{"key":"e_1_2_12_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-23220-6_7"},{"key":"e_1_2_12_25_1","unstructured":"T.Carneiro N.Melab A.Hayashi andV.Sarkar \u201cTowards Chapel\u2010Based Exascale Tree Search Algorithms: Dealing With Multiple GPU Accelerators \u201d(2021) 18th International Conference on High Performance Computing & Simulation."},{"key":"e_1_2_12_26_1","unstructured":"B. L.Chamberlain E.Ronaghan B.Albrecht et al. \u201cChapel Comes of Age: Making Scalable Programming Productive \u201d(2018) Cray User Group."},{"key":"e_1_2_12_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW63119.2024.00011"},{"key":"e_1_2_12_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-69583-4_27"},{"key":"e_1_2_12_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW63119.2024.00156"},{"key":"e_1_2_12_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324234"},{"key":"e_1_2_12_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1.2.117"},{"key":"e_1_2_12_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.26.1.53"},{"key":"e_1_2_12_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377\u20102217(93)90182\u2010M"},{"key":"e_1_2_12_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/131214.131227"},{"volume-title":"Advanced Compiler Design and Implementation","year":"1998","author":"Muchnick S.","key":"e_1_2_12_35_1"},{"key":"e_1_2_12_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-63759-9_13"},{"key":"e_1_2_12_37_1","first-page":"389","volume-title":"IEEE 14th International Conference on High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems","author":"Chakroun I.","year":"2012"},{"key":"e_1_2_12_38_1","doi-asserted-by":"publisher","DOI":"10.1177\/1094342009106189"}],"container-title":["Concurrency and Computation: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/cpe.70321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,12]],"date-time":"2025-11-12T09:04:29Z","timestamp":1762938269000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/cpe.70321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,2]]},"references-count":37,"journal-issue":{"issue":"25-26","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1002\/cpe.70321"],"URL":"https:\/\/doi.org\/10.1002\/cpe.70321","archive":["Portico"],"relation":{},"ISSN":["1532-0626","1532-0634"],"issn-type":[{"type":"print","value":"1532-0626"},{"type":"electronic","value":"1532-0634"}],"subject":[],"published":{"date-parts":[[2025,10,2]]},"assertion":[{"value":"2024-11-30","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-02","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"e70321"}}