{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,9]],"date-time":"2025-12-09T18:10:19Z","timestamp":1765303819340,"version":"build-2065373602"},"reference-count":36,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2020,12,2]],"date-time":"2020-12-02T00:00:00Z","timestamp":1606867200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computation"],"abstract":"<jats:p>Many modern applications are modeled using graphs of some kind. Given a graph, reachability, that is, discovering whether there is a path between two given nodes, is a fundamental problem as well as one of the most important steps of many other algorithms. The rapid accumulation of very large graphs (up to tens of millions of vertices and edges) from a diversity of disciplines demand efficient and scalable solutions to the reachability problem. General-purpose computing has been successfully used on Graphics Processing Units (GPUs) to parallelize algorithms that present a high degree of regularity. In this paper, we extend the applicability of GPU processing to graph-based manipulation, by re-designing a simple but efficient state-of-the-art graph-labeling method, namely the GRAIL (Graph Reachability Indexing via RAndomized Interval) algorithm, to many-core CUDA-based GPUs. This algorithm firstly generates a label for each vertex of the graph, then it exploits these labels to answer reachability queries. Unfortunately, the original algorithm executes a sequence of depth-first visits which are intrinsically recursive and cannot be efficiently implemented on parallel systems. For that reason, we design an alternative approach in which a sequence of breadth-first visits substitute the original depth-first traversal to generate the labeling, and in which a high number of concurrent visits is exploited during query evaluation. The paper describes our strategy to re-design these steps, the difficulties we encountered to implement them, and the solutions adopted to overcome the main inefficiencies. To prove the validity of our approach, we compare (in terms of time and memory requirements) our GPU-based approach with the original sequential CPU-based tool. Finally, we report some hints on how to conduct further research in the area.<\/jats:p>","DOI":"10.3390\/computation8040103","type":"journal-article","created":{"date-parts":[[2020,12,2]],"date-time":"2020-12-02T07:49:54Z","timestamp":1606895394000},"page":"103","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Graph Reachability on Parallel Many-Core Architectures"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6835-8277","authenticated-orcid":false,"given":"Stefano","family":"Quer","sequence":"first","affiliation":[{"name":"Department of Control and Computer Engineering, Politecnico di Torino, Corso Duca degli Abruzzi 24, I-10129 Turin, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrea","family":"Calabrese","sequence":"additional","affiliation":[{"name":"Department of Control and Computer Engineering, Politecnico di Torino, Corso Duca degli Abruzzi 24, I-10129 Turin, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2020,12,2]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Chen, Y., and Chen, Y. (2011, January 11\u201316). Decomposing DAGs into Spanning Trees: A new way to Compress Transitive Closures. Proceedings of the 2011 IEEE 27th International Conference on Data Engineering, Hannover, Germany.","key":"ref_1","DOI":"10.1109\/ICDE.2011.5767832"},{"doi-asserted-by":"crossref","unstructured":"Zhang, Z., Yu, J.X., Qin, L., Zhu, Q., and Zhou, X. (2012). I\/O Cost Minimization: Reachability Queries Processing over Massive Graphs. Proceedings of the 15th International Conference on Extending Database Technology, Association for Computing Machinery. EDBT \u201912.","key":"ref_2","DOI":"10.1145\/2247596.2247651"},{"unstructured":"Ruoming, J., and Guan, W. (2013). Simple, Fast, and Scalable Reachability Oracle. arXiv.","key":"ref_3"},{"doi-asserted-by":"crossref","unstructured":"Zhu, A.D., Lin, W., Wang, S., and Xiao, X. (2014). Reachability Queries on Large Dynamic Graphs: A Total Order Approach. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery. SIGMOD \u201914.","key":"ref_4","DOI":"10.1145\/2588555.2612181"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"683","DOI":"10.1109\/TKDE.2016.2631160","article-title":"Reachability Querying: Can It Be Even Faster?","volume":"29","author":"Su","year":"2017","journal-title":"IEEE Trans. Knowl. Data Eng."},{"doi-asserted-by":"crossref","unstructured":"Strzheletska, E.V., and Tsotras, V.J. (2017). Efficient Processing of Reachability Queries with Meetings. Proceedings of the 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, Association for Computing Machinery. SIGSPATIAL \u201917.","key":"ref_6","DOI":"10.1145\/3139958.3139982"},{"doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Tomescu, A.I., Kuosmanen, A., Paavilainen, T., Gagie, T., and Chikhi, R. (2019). Sparse Dynamic Programming on DAGs with Small Width. ACM Trans. Algorithms, 15.","key":"ref_7","DOI":"10.1145\/3301312"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"812","DOI":"10.14778\/3380750.3380753","article-title":"Answering Billion-Scale Label-Constrained Reachability Queries within Microsecond","volume":"13","author":"Peng","year":"2020","journal-title":"Proc. VLDB Endow."},{"doi-asserted-by":"crossref","unstructured":"Pacaci, A., Bonifati, A., and \u00d6zsu, M.T. (2020). Regular Path Query Evaluation on Streaming Graphs. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery. SIGMOD \u201920.","key":"ref_9","DOI":"10.1145\/3318464.3389733"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"52027","DOI":"10.1109\/ACCESS.2018.2870283","article-title":"A Fast MPEG\u2019s CDVS Implementation for GPU Featured in Mobile","volume":"6","author":"Garbo","year":"2018","journal-title":"IEEE Access"},{"doi-asserted-by":"crossref","unstructured":"Cabodi, G., Camurati, P., Garbo, A., Giorelli, M., Quer, S., and Savarese, F. (2019). A Smart Many-Core Implementation of a Motion Planning Framework along a Reference Path for Autonomous Cars. Electronics, 8.","key":"ref_11","DOI":"10.3390\/electronics8020177"},{"doi-asserted-by":"crossref","unstructured":"Quer, S., Andrea, M., and Giovanni, S. (2020). The Maximum Common Subgraph Problem: A Parallel and Multi-Engine Approach. Computation, 8.","key":"ref_12","DOI":"10.3390\/computation8020048"},{"doi-asserted-by":"crossref","unstructured":"Wang, Y., Davidson, A., Pan, Y., Wu, Y., Riffel, A., and Owens, J.D. (2016). Gunrock: A High-Performance Graph Processing Library on the GPU. Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery. PPoPP \u201916.","key":"ref_13","DOI":"10.1145\/2851141.2851145"},{"unstructured":"Mattson, T., Sanders, B., and Massingill, B. (2004). Patterns for Parallel Programming, Addison-Wesley Professional. [1st ed.].","key":"ref_14"},{"doi-asserted-by":"crossref","unstructured":"McCool, M., Reinders, J., and Robison, A. (2012). Structured Parallel Programming: Patterns for Efficient Computation, Morgan Kaufmann Publishers Inc.. [1st ed.].","key":"ref_15","DOI":"10.1016\/B978-0-12-415993-8.00003-7"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"276","DOI":"10.14778\/1920841.1920879","article-title":"GRAIL: Scalable Reachability Index for Large Graphs","volume":"3","author":"Yildirim","year":"2010","journal-title":"Proc. VLDB Endow."},{"doi-asserted-by":"crossref","unstructured":"Naumov, M., Vrielink, A., and Garland, M. (2020, December 02). Parallel Depth-First Search for Directed Acyclic Graphs. Available online: https:\/\/research.nvidia.com\/sites\/default\/files\/publications\/nvr-2017-001.pdf.","key":"ref_17","DOI":"10.1145\/3149704.3149764"},{"doi-asserted-by":"crossref","unstructured":"Naumov, M., Vrielink, A., and Garland, M. (2017). Parallel Depth-First Search for Directed Acyclic Graphs. Proceedings of the Seventh Workshop on Irregular Applications: Architectures and Algorithms, Association for Computing Machinery. IA3\u201917.","key":"ref_18","DOI":"10.1145\/3149704.3149764"},{"doi-asserted-by":"crossref","unstructured":"Luo, L., Wong, M., and Hwu, W.M. (2010). An Effective GPU Implementation of Breadth-first Search. Proceedings of the 47th Design Automation Conference, ACM. DAC \u201910.","key":"ref_19","DOI":"10.1145\/1837274.1837289"},{"doi-asserted-by":"crossref","unstructured":"Liu, H., and Huang, H.H. (2015, January 15\u201320). Enterprise: Breadth-first graph traversal on GPUs. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Austin, TX, USA.","key":"ref_20","DOI":"10.1145\/2807591.2807594"},{"doi-asserted-by":"crossref","unstructured":"Shi, X., Zheng, Z., Zhou, Y., Jin, H., He, L., Liu, B., and Hua, Q.S. (2018). Graph Processing on GPUs: A Survey. ACM Comput. Surv., 50.","key":"ref_21","DOI":"10.1145\/3128571"},{"unstructured":"Karimi, K., Dickson, N.G., and Hamze, F. (2010). A Performance Comparison of CUDA and OpenCL. arXiv.","key":"ref_22"},{"doi-asserted-by":"crossref","unstructured":"Fang, J., Varbanescu, A.L., and Sips, H. (2011, January 13\u201316). A Comprehensive Performance Comparison of CUDA and OpenCL. Proceedings of the International Conference on Parallel Processing, Taipei, Taiwan.","key":"ref_23","DOI":"10.1109\/ICPP.2011.45"},{"key":"ref_24","first-page":"1","article-title":"Performance Comparison of Parallel Programming Frameworks in Digital Image Transformation","volume":"11","author":"Shin","year":"2019","journal-title":"Int. J. Internet Broadcast. Commun."},{"doi-asserted-by":"crossref","unstructured":"Quer, S. (2020, January 7\u20139). A Parallel Many-core CUDA-based Graph Labeling Computation. Proceedings of the 15th International Conference on Software Technologies (ICSOFT), Paris, France.","key":"ref_25","DOI":"10.5220\/0009780205970605"},{"doi-asserted-by":"crossref","unstructured":"Sanders, P., and Schultes, D. (2005). Highway Hierarchies Hasten Exact Shortest Path Queries. Algorithms, ESA 2005, Springer.","key":"ref_26","DOI":"10.1007\/11561071_51"},{"doi-asserted-by":"crossref","unstructured":"Tri\u00dfl, S., and Leser, U. (2007). Fast and Practical Indexing and Querying of Very Large Graphs. Proceedings of the ACM SIGMOD International Conference on Management of Data, ACM. SIGMOD \u201907.","key":"ref_27","DOI":"10.1145\/1247480.1247573"},{"doi-asserted-by":"crossref","unstructured":"Cohen, E., Halperin, E., Kaplan, H., and Zwick, U. (2002). Reachability and Distance Queries via 2-hop Labels. Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics. SODA \u201902.","key":"ref_28","DOI":"10.1137\/S0097539702403098"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1145\/99935.99944","article-title":"A Compression Technique to Materialize Transitive Closure","volume":"15","author":"Jagadish","year":"1990","journal-title":"ACM Trans. Database Syst."},{"unstructured":"Wang, H., He, H., Yang, J., Yu, P.S., and Yu, J.X. (2006). Dual Labeling: Answering Graph Reachability Queries in Constant Time. Proceedings of the 22nd International Conference on Data Engineering (ICDE\u201906), IEEE Computer Society.","key":"ref_30"},{"doi-asserted-by":"crossref","unstructured":"Jin, R., Xiang, Y., Ruan, N., and Wang, H. (2008). Efficiently Answering Reachability Queries on Very Large Directed Graphs. Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data, ACM. SIGMOD \u201908.","key":"ref_31","DOI":"10.1145\/1376616.1376677"},{"doi-asserted-by":"crossref","unstructured":"Chen, Y., and Chen, Y. (2008). An Efficient Algorithm for Answering Graph Reachability Queries. Proceedings of the IEEE 24th International Conference on Data Engineering, IEEE Computer Society. ICDE \u201908.","key":"ref_32","DOI":"10.1109\/ICDE.2008.4497498"},{"unstructured":"Van, S., Sebastiaan, J., and de Moor, O. (2011). A Memory Efficient Reachability Data Structure through Bit Vector Compression. Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data, Association for Computing Machinery. SIGMOD \u201911.","key":"ref_33"},{"doi-asserted-by":"crossref","unstructured":"Merrill, D., Garland, M., and Grimshaw, A. (2012). Scalable GPU Graph Traversal. Proceedings of the 17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, Association for Computing Machinery. PPoPP \u201912.","key":"ref_34","DOI":"10.1145\/2145816.2145832"},{"doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Anderson, R.J., and Kao, M.Y. (1989). Parallel Depth-First Search in General Directed Graphs. Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, Association for Computing Machinery. STOC \u201989.","key":"ref_35","DOI":"10.1145\/73007.73035"},{"doi-asserted-by":"crossref","unstructured":"Acar, U.A., Chargu\u00e9raud, A., and Rainey, M. (2015). A Work-Efficient Algorithm for Parallel Unordered Depth-First Search. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, Association for Computing Machinery. SC \u201915.","key":"ref_36","DOI":"10.1145\/2807591.2807651"}],"container-title":["Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2079-3197\/8\/4\/103\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T10:40:29Z","timestamp":1760179229000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2079-3197\/8\/4\/103"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,2]]},"references-count":36,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2020,12]]}},"alternative-id":["computation8040103"],"URL":"https:\/\/doi.org\/10.3390\/computation8040103","relation":{},"ISSN":["2079-3197"],"issn-type":[{"type":"electronic","value":"2079-3197"}],"subject":[],"published":{"date-parts":[[2020,12,2]]}}}