{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/110559"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/110559","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"High performance DFS-based subgraph enumeration on GPUs","abstract":"Subgraph enumeration is an important problem in the field of Graph Analytics with numerous applications. The problem is provably NP-complete and requires sophisticated heuristics and highly efficient implementations to be feasible on problem sizes of realistic scales. Parallel solutions have shown a lot of promise on CPUs and distributed environments. GPU-based solutions are gaining traction in recent times. Subgraph enumeration involves traversing a search tree formulated to find matches of a query in a graph. Most GPU-based solutions traverse the tree in a breadth-first manner which exploits parallelism at the cost of high memory requirement, which presents a formidable challenge for processing large graphs since the memory capacity of GPUs is significantly lower than that of CPUs. In this thesis, we propose a fast GPU-based solution based on depth-first traversal of the search tree. The depth-first approach requires less memory but presents more challenges for parallel execution. We apply various optimizations to optimally utilize memory and compute resources of the GPUs. We evaluate our performance in comparison with state-of-the-art CPU and GPU implementations. We outperform them with a geometric mean speedup of 10,678x and 8.56x from CPU and GPU implementations respectively. We also show that the proposed approach can efficiently process the graphs that previously cannot be processed by these state-of-the-art implementations due to their excessive memory requirement.","abstract_html":"Subgraph enumeration is an important problem in the field of Graph Analytics with numerous applications. The problem is provably NP-complete and requires sophisticated heuristics and highly efficient implementations to be feasible on problem sizes of realistic scales. Parallel solutions have shown a lot of promise on CPUs and distributed environments. GPU-based solutions are gaining traction in recent times. Subgraph enumeration involves traversing a search tree formulated to find matches of a query in a graph. Most GPU-based solutions traverse the tree in a breadth-first manner which exploits parallelism at the cost of high memory requirement, which presents a formidable challenge for processing large graphs since the memory capacity of GPUs is significantly lower than that of CPUs. In this thesis, we propose a fast GPU-based solution based on depth-first traversal of the search tree. The depth-first approach requires less memory but presents more challenges for parallel execution. We apply various optimizations to optimally utilize memory and compute resources of the GPUs. We evaluate our performance in comparison with state-of-the-art CPU and GPU implementations. We outperform them with a geometric mean speedup of 10,678x and 8.56x from CPU and GPU implementations respectively. We also show that the proposed approach can efficiently process the graphs that previously cannot be processed by these state-of-the-art implementations due to their excessive memory requirement.","abstract_has_math":false,"creators":["Dodeja, Vibhor"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Nagi, Rakesh","Hwu, Wen-mei"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2021,"date_issued":"2021-09-17T01:11:16Z","date_published":"2021-09-17T01:11:16Z","updated_at":"2026-07-22T22:24:52Z","subjects":["Subgraph enumeration, Pattern matching, Graphics processing units, acceleration, data mining"],"languages":["en"],"rights":["Copyright 2021 Vibhor Dodeja"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/110559","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Nagi, Rakesh","Hwu, Wen-mei"]},{"key":"dc:creator","label":"Author","values":["Dodeja, Vibhor"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2021-09-17T01:11:16Z","2021-04-26","2021-05"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engr"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Subgraph enumeration, Pattern matching, Graphics processing units, acceleration, data mining"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2021 Vibhor Dodeja"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/110559"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Subgraph enumeration is an important problem in the field of Graph Analytics with numerous applications. The problem is provably NP-complete and requires sophisticated heuristics and highly efficient implementations to be feasible on problem sizes of realistic scales. Parallel solutions have shown a lot of promise on CPUs and distributed environments. GPU-based solutions are gaining traction in recent times. Subgraph enumeration involves traversing a search tree formulated to find matches of a query in a graph. Most GPU-based solutions traverse the tree in a breadth-first manner which exploits parallelism at the cost of high memory requirement, which presents a formidable challenge for processing large graphs since the memory capacity of GPUs is significantly lower than that of CPUs. In this thesis, we propose a fast GPU-based solution based on depth-first traversal of the search tree. The depth-first approach requires less memory but presents more challenges for parallel execution. We apply various optimizations to optimally utilize memory and compute resources of the GPUs. We evaluate our performance in comparison with state-of-the-art CPU and GPU implementations. We outperform them with a geometric mean speedup of 10,678x and 8.56x from CPU and GPU implementations respectively. We also show that the proposed approach can efficiently process the graphs that previously cannot be processed by these state-of-the-art implementations due to their excessive memory requirement.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms","The student, Vibhor Dodeja, accepted the attached license on 2021-04-23 at 08:59.","The student, Vibhor Dodeja, submitted this Thesis for approval on 2021-04-23 at 09:06.","This Thesis was approved for publication on 2021-04-26 at 14:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16523 on 2021-09-16 at 16:47:22","Made available in DSpace on 2021-09-17T01:11:16Z (GMT). No. of bitstreams: 2 DODEJA-THESIS-2021.pdf: 1708041 bytes, checksum: 7af640b203dc91a1257d1cedbbdb7774 (MD5) LICENSE.txt: 4210 bytes, checksum: 58a4f2af7fe7f5cf573f96f4d5324369 (MD5) Previous issue date: 2021-04-26"]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["High performance DFS-based subgraph enumeration on GPUs"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh","Hwu, Wen-mei"],"dc:creator":["Dodeja, Vibhor"],"dc:date":["2021-09-17T01:11:16Z","2021-04-26","2021-05"],"dc:description":["Subgraph enumeration is an important problem in the field of Graph Analytics with numerous applications. The problem is provably NP-complete and requires sophisticated heuristics and highly efficient implementations to be feasible on problem sizes of realistic scales. Parallel solutions have shown a lot of promise on CPUs and distributed environments. GPU-based solutions are gaining traction in recent times. Subgraph enumeration involves traversing a search tree formulated to find matches of a query in a graph. Most GPU-based solutions traverse the tree in a breadth-first manner which exploits parallelism at the cost of high memory requirement, which presents a formidable challenge for processing large graphs since the memory capacity of GPUs is significantly lower than that of CPUs. In this thesis, we propose a fast GPU-based solution based on depth-first traversal of the search tree. The depth-first approach requires less memory but presents more challenges for parallel execution. We apply various optimizations to optimally utilize memory and compute resources of the GPUs. We evaluate our performance in comparison with state-of-the-art CPU and GPU implementations. We outperform them with a geometric mean speedup of 10,678x and 8.56x from CPU and GPU implementations respectively. We also show that the proposed approach can efficiently process the graphs that previously cannot be processed by these state-of-the-art implementations due to their excessive memory requirement.","Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2021-09-16 without embargo terms","The student, Vibhor Dodeja, accepted the attached license on 2021-04-23 at 08:59.","The student, Vibhor Dodeja, submitted this Thesis for approval on 2021-04-23 at 09:06.","This Thesis was approved for publication on 2021-04-26 at 14:48.","DSpace SAF Submission Ingestion Package generated from Vireo submission #16523 on 2021-09-16 at 16:47:22","Made available in DSpace on 2021-09-17T01:11:16Z (GMT). No. of bitstreams: 2 DODEJA-THESIS-2021.pdf: 1708041 bytes, checksum: 7af640b203dc91a1257d1cedbbdb7774 (MD5) LICENSE.txt: 4210 bytes, checksum: 58a4f2af7fe7f5cf573f96f4d5324369 (MD5) Previous issue date: 2021-04-26"],"dc:format":["application/pdf"],"dc:identifier":["http://hdl.handle.net/2142/110559"],"dc:language":["en"],"dc:rights":["Copyright 2021 Vibhor Dodeja"],"dc:subject":["Subgraph enumeration, Pattern matching, Graphics processing units, acceleration, data mining"],"dc:title":["High performance DFS-based subgraph enumeration on GPUs"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:52Z"}