{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T13:43:24Z","timestamp":1782999804415,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":69,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,5]],"date-time":"2026-07-05T00:00:00Z","timestamp":1783209600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100016263","name":"University Research Board, American University of Beirut","doi-asserted-by":"publisher","award":["28005-104631"],"award-info":[{"award-number":["28005-104631"]}],"id":[{"id":"10.13039\/501100016263","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,6]]},"DOI":"10.1145\/3797905.3805620","type":"proceedings-article","created":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T11:50:37Z","timestamp":1782993037000},"page":"382-394","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Parallel Bidirectional A* Search for GPU-Accelerated Pathfinding"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-7803-2833","authenticated-orcid":false,"given":"Hadi","family":"Al Khansa","sequence":"first","affiliation":[{"name":"American University of Beirut, Beirut, Lebanon"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6514-1571","authenticated-orcid":false,"given":"Juan","family":"G\u00f3mez Luna","sequence":"additional","affiliation":[{"name":"NVIDIA, Santa Clara, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2481-4968","authenticated-orcid":false,"given":"Amer","family":"Mouawad","sequence":"additional","affiliation":[{"name":"American University of Beirut, Beirut, Lebanon and University of Waterloo, Waterloo, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3356-6898","authenticated-orcid":false,"given":"Izzat","family":"El Hajj","sequence":"additional","affiliation":[{"name":"American University of Beirut, Beirut, Lebanon"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7,5]]},"reference":[{"key":"e_1_3_3_2_2_2","first-page":"287","volume-title":"Edsger Wybe Dijkstra: his life, work, and legacy","year":"2022","unstructured":"2022. A note on two problems in connexion with graphs. In Edsger Wybe Dijkstra: his life, work, and legacy. 287\u2013290."},{"key":"e_1_3_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCGRID.2018.00008"},{"key":"e_1_3_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS64566.2025.00034"},{"key":"e_1_3_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/PACT58117.2023.00022"},{"key":"e_1_3_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3524059.3532382"},{"key":"e_1_3_3_2_7_2","unstructured":"Momodou Bah Ioanna Giorgi and Giovanni\u00a0Luca Masala. 2025. A lightweight and rapid bidirectional search algorithm. Robot Learning 2 2 (2025)."},{"key":"e_1_3_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/MASCOTS.2017.15"},{"key":"e_1_3_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2742854.2742887"},{"key":"e_1_3_3_2_10_2","unstructured":"Kyle Berney John Iacono Ben Karsin and Nodari Sitchinava. 2019. A parallel priority queue with fast updates for GPU architectures. arXiv preprint arXiv:https:\/\/arXiv.org\/abs\/1908.09378 (2019)."},{"key":"e_1_3_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/1413957.1413968"},{"key":"e_1_3_3_2_12_2","doi-asserted-by":"crossref","unstructured":"Antonios Chatzisavvas Michael Dossis and Minas Dasygenis. 2024. Optimizing mobile robot navigation based on A-star algorithm for obstacle avoidance in smart agriculture. Electronics 13 11 (2024) 2057.","DOI":"10.3390\/electronics13112057"},{"key":"e_1_3_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2830772.2830818"},{"key":"e_1_3_3_2_14_2","first-page":"857","volume-title":"16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22)","author":"Chen Xuhao","year":"2022","unstructured":"Xuhao Chen et\u00a0al. 2022. Efficient and scalable graph pattern mining on { GPUs}. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 857\u2013877."},{"key":"e_1_3_3_2_15_2","doi-asserted-by":"crossref","unstructured":"Xuhao Chen Roshan Dathathri Gurbinder Gill and Keshav Pingali. 2020. Pangolin: An efficient and flexible graph mining system on cpu and gpu. Proceedings of the VLDB Endowment 13 8 (2020) 1190\u20131205.","DOI":"10.14778\/3389133.3389137"},{"key":"e_1_3_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3472456.3472463"},{"key":"e_1_3_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004254"},{"key":"e_1_3_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2014.45"},{"key":"e_1_3_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25090-3_26"},{"key":"e_1_3_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087580"},{"key":"e_1_3_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3694906.3743311"},{"key":"e_1_3_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2016.7783716"},{"key":"e_1_3_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1201\/9781003033707-22"},{"key":"e_1_3_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/SBAC-PAD55451.2022.00022"},{"key":"e_1_3_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004219"},{"key":"e_1_3_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3307681.3326606"},{"key":"e_1_3_3_2_27_2","doi-asserted-by":"crossref","unstructured":"Peter\u00a0E Hart Nils\u00a0J Nilsson and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4 2 (1968) 100\u2013107.","DOI":"10.1109\/TSSC.1968.300136"},{"key":"e_1_3_3_2_28_2","unstructured":"Xin He Yapeng Yao Zhiwen Chen Jianhua Sun and Hao Chen. 2021. Efficient parallel A* search on multi-GPU system. Future Generation Computer Systems 123 (2021) 35\u201347."},{"key":"e_1_3_3_2_29_2","doi-asserted-by":"crossref","unstructured":"Galen\u00a0C Hunt Maged\u00a0M Michael Srinivasan Parthasarathy and Michael\u00a0L Scott. 1996. An efficient algorithm for concurrent priority queue heaps. Inform. Process. Lett. 60 3 (1996) 151\u2013157.","DOI":"10.1016\/S0020-0190(96)00148-2"},{"key":"e_1_3_3_2_30_2","volume-title":"Programming Massively Parallel Processors: A Hands-on Approach","author":"Hwu Wen-mei\u00a0W","year":"2022","unstructured":"Wen-mei\u00a0W Hwu, David\u00a0B Kirk, and Izzat El\u00a0Hajj. 2022. Programming Massively Parallel Processors: A Hands-on Approach. Morgan Kaufmann."},{"key":"e_1_3_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPSW59300.2023.00045"},{"key":"e_1_3_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/3205289.3205291"},{"key":"e_1_3_3_2_33_2","doi-asserted-by":"crossref","unstructured":"Bernhard Kerbl J\u00f6rg M\u00fcller Michael Kenzel Dieter Schmalstieg and Markus Steinberger. 2018. A scalable queue for work distribution on gpus. ACM SIGPLAN Notices 53 1 (2018) 401\u2013402.","DOI":"10.1145\/3200691.3178526"},{"key":"e_1_3_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2600212.2600227"},{"key":"e_1_3_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882959"},{"key":"e_1_3_3_2_36_2","first-page":"263","volume-title":"International Parallel and Distributed Processing Symposium","author":"Lotan Itay","year":"2000","unstructured":"Itay Lotan and Nir Shavit. 2000. Skiplist-based concurrent priority queues. In International Parallel and Distributed Processing Symposium. 263\u2013268."},{"key":"e_1_3_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1837274.1837289"},{"key":"e_1_3_3_2_38_2","doi-asserted-by":"crossref","unstructured":"Enrico Mastrostefano and Massimo Bernaschi. 2013. Efficient breadth first search on multi-GPU systems. J. Parallel and Distrib. Comput. 73 9 (2013) 1292\u20131305.","DOI":"10.1016\/j.jpdc.2013.05.007"},{"key":"e_1_3_3_2_39_2","doi-asserted-by":"crossref","unstructured":"Duane Merrill Michael Garland and Andrew Grimshaw. 2012. Scalable GPU graph traversal. ACM Sigplan Notices 47 8 (2012) 117\u2013128.","DOI":"10.1145\/2145816.2145832"},{"key":"e_1_3_3_2_40_2","unstructured":"Ulrich Meyer and Peter Sanders. 2003. \u0394 -stepping: a parallelizable shortest path algorithm. Journal of Algorithms 49 1 (2003) 114\u2013152."},{"key":"e_1_3_3_2_41_2","doi-asserted-by":"crossref","unstructured":"Takuji Mitsuishi Jun Suzuki Yuki Hayashi Masaki Kan and Hideharu Amano. 2016. Breadth first search on cost-efficient multi-GPU systems. ACM SIGARCH Computer Architecture News 43 4 (2016) 58\u201363.","DOI":"10.1145\/2927964.2927975"},{"key":"e_1_3_3_2_42_2","doi-asserted-by":"crossref","unstructured":"Amir\u00a0Hossein Nodehi\u00a0Sabet Junqiao Qiu and Zhijia Zhao. 2018. Tigr: Transforming irregular graphs for gpu-friendly graph processing. ACM SIGPLAN Notices 53 2 (2018) 622\u2013636.","DOI":"10.1145\/3296957.3173180"},{"key":"e_1_3_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/CGO53902.2022.9741284"},{"key":"e_1_3_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01863.x"},{"key":"e_1_3_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2018.00118"},{"key":"e_1_3_3_2_46_2","doi-asserted-by":"crossref","unstructured":"John\u00a0A Pavlik Edward\u00a0C Sewell and Sheldon\u00a0H Jacobson. 2021. Two new bidirectional search algorithms. Computational Optimization and Applications 80 2 (2021) 377\u2013409.","DOI":"10.1007\/s10589-021-00303-5"},{"key":"e_1_3_3_2_47_2","volume-title":"A new bidirectional algorithm for shortest paths","author":"Pijls Wim","year":"2008","unstructured":"Wim Pijls and Henk Post. 2008. A new bidirectional algorithm for shortest paths. Technical Report."},{"key":"e_1_3_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3677333.3678269"},{"key":"e_1_3_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3342195.3387537"},{"key":"e_1_3_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/SBGAMES.2011.35"},{"key":"e_1_3_3_2_51_2","doi-asserted-by":"crossref","unstructured":"N. Sturtevant. 2012. Benchmarks for Grid-Based Pathfinding. Transactions on Computational Intelligence and AI in Games 4 2 (2012) 144 \u2013 148. http:\/\/web.cs.du.edu\/\u00a0sturtevant\/papers\/benchmarks.pdf","DOI":"10.1109\/TCIAIG.2012.2197681"},{"key":"e_1_3_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v32i1.12218"},{"key":"e_1_3_3_2_53_2","doi-asserted-by":"crossref","unstructured":"H\u00e5kan Sundell and Philippas Tsigas. 2005. Fast and lock-free concurrent priority queues for multi-thread systems. J. Parallel and Distrib. Comput. 65 5 (2005) 609\u2013627.","DOI":"10.1016\/j.jpdc.2004.12.005"},{"key":"e_1_3_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA.2017.14"},{"key":"e_1_3_3_2_55_2","doi-asserted-by":"crossref","unstructured":"Lalinthip Tangjittaweechai Mongkol Ekpanyapong Thaisiri Watewai Krit Athikulwongse Sung\u00a0Kyu Lim and Adriano Tavares. 2016. Fast bidirectional shortest path on GPU. IEICE Electronics Express 13 6 (2016) 20160036\u201320160036.","DOI":"10.1587\/elex.13.20160036"},{"key":"e_1_3_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2013.6799136"},{"key":"e_1_3_3_2_57_2","doi-asserted-by":"crossref","unstructured":"Jin Wang Norm Rubin Albert Sidelnik and Sudhakar Yalamanchili. 2016. Laperm: Locality aware scheduler for dynamic parallelism on gpus. ACM SIGARCH Computer Architecture News 44 3 (2016) 583\u2013595.","DOI":"10.1145\/3007787.3001199"},{"key":"e_1_3_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/IISWC.2014.6983039"},{"key":"e_1_3_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/3437801.3441605"},{"key":"e_1_3_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1145\/2851141.2851145"},{"key":"e_1_3_3_2_61_2","doi-asserted-by":"crossref","unstructured":"Yangzihao Wang Yuechao Pan Andrew Davidson Yuduo Wu Carl Yang Leyuan Wang Muhammad Osama Chenshan Yuan Weitang Liu Andy\u00a0T Riffel et\u00a0al. 2017. Gunrock: GPU graph analytics. ACM Transactions on Parallel Computing (TOPC) 4 1 (2017) 1\u201349.","DOI":"10.1145\/3108140"},{"key":"e_1_3_3_2_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2016.98"},{"key":"e_1_3_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC67600.2025.11196089"},{"key":"e_1_3_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS53621.2022.00028"},{"key":"e_1_3_3_2_65_2","doi-asserted-by":"crossref","unstructured":"Yi Yang and Huiyang Zhou. 2014. CUDA-NP: Realizing nested thread-level parallelism in GPGPU applications. ACM SIGPLAN Notices 49 8 (2014) 93\u2013106.","DOI":"10.1145\/2692916.2555254"},{"key":"e_1_3_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00244"},{"key":"e_1_3_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3626183.3659962"},{"key":"e_1_3_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/3368826.3377909"},{"key":"e_1_3_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3605731.3605746"},{"key":"e_1_3_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9367"}],"event":{"name":"ICS '26: 2026 International Conference on Supercomputing","location":"Belfast United Kingdom","acronym":"ICS '26","sponsor":["SIGHPC ACM Special Interest Group on High Performance Computing, Special Interest Group on High Performance Computing","SIGARCH ACM Special Interest Group on Computer Architecture"]},"container-title":["Proceedings of the 40th ACM International Conference on Supercomputing"],"original-title":[],"deposited":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T12:47:52Z","timestamp":1782996472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3797905.3805620"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,5]]},"references-count":69,"alternative-id":["10.1145\/3797905.3805620","10.1145\/3797905"],"URL":"https:\/\/doi.org\/10.1145\/3797905.3805620","relation":{},"subject":[],"published":{"date-parts":[[2026,7,5]]},"assertion":[{"value":"2026-07-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}