{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/116103"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/116103","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Enhancements in high performance subgraph enumeration on graphics processors","abstract":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","abstract_html":"Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","abstract_has_math":false,"creators":["Kawtikwar, Samiran"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Industrial Engineering","degree_department":null,"school":null,"contributors":["Nagi, Rakesh","Hwu, Wen-Mei"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-22T22:24:55Z","subjects":["subgraph-enumeration","cuda","gpu","parallel algorithms","DFS","big graphs","graph analytics"],"languages":["en","eng"],"rights":["Copyright 2022 Samiran Kawtikwar"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/116103","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":["Kawtikwar, Samiran"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-08","2022-07-18"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering"]},{"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","cuda","gpu","parallel algorithms","DFS","big graphs","graph analytics"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Samiran Kawtikwar"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/116103"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","The student, Samiran Kawtikwar, accepted the attached license on 2022-07-14 at 11:27.","The student, Samiran Kawtikwar, submitted this Thesis for approval on 2022-07-14 at 11:44.","This Thesis was approved for publication on 2022-07-18 at 16:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18306 on 2022-11-15 at 21:40:11","Subgraph enumeration is an important problem in graph theory with a wide range of applications. With rapidly increasing graph sizes due to advent of internet and smartphones, subgraph enumeration needs high performing implementations. Being NP-complete, this problem poses significant scalability challenges and needs efficient implementations for practical solutions. Fortunately, this problem is highly amenable to parallelization. There are already many solutions in the multi-core and distributed computing community. GPU (Graphics Processing Unit)-based solutions are recently gaining recognition as they offer massive parallelism without network delays. Most GPU solutions use Breadth First Traversal to utilize underlying parallelism and impose expensive restrictions on hardware due to huge memory requirements. PARSEC (Parallel Subgraph Enumeration and Counter) is the first GPU-based solution that uses Depth First Search and performs in-memory subgraph enumeration. In this thesis, PARSEC is improved by leveraging insights from traditional sequential solutions and advanced parallel programming techniques. The performance of Subgraph Enumeration is limited by the computational cost of adjacency list intersection operations. To tackle this, a smart preprocessing technique was developed for detecting opportunities for intersection reuse, which, in turn, reduces the number of intersections by up to 3.87×. A two-phase pruning technique was developed which shrinks the search space to further reduce the number of intersections by up to 6.6×. An in-depth analysis of PARSEC was conducted to overcome its load imbalance and limited hardware utilization. A hybrid parallelization scheme was developed that improves the load balance by up to 14×. Altogether, these improvements provide a geometric mean time speedup up to 4.6× across data graphs and up to 3.7× across all queries with max speedups up to 14.6×."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Enhancements in high performance subgraph enumeration on graphics processors"]}]}],"canonical_facts":{"dc:contributor":["Nagi, Rakesh","Hwu, Wen-Mei"],"dc:creator":["Kawtikwar, Samiran"],"dc:date":["2022-08","2022-07-18"],"dc:description":["Submission published under a 24 month embargo labeled 'U of I Access', the embargo will last until 2024-08-01","The student, Samiran Kawtikwar, accepted the attached license on 2022-07-14 at 11:27.","The student, Samiran Kawtikwar, submitted this Thesis for approval on 2022-07-14 at 11:44.","This Thesis was approved for publication on 2022-07-18 at 16:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18306 on 2022-11-15 at 21:40:11","Subgraph enumeration is an important problem in graph theory with a wide range of applications. With rapidly increasing graph sizes due to advent of internet and smartphones, subgraph enumeration needs high performing implementations. Being NP-complete, this problem poses significant scalability challenges and needs efficient implementations for practical solutions. Fortunately, this problem is highly amenable to parallelization. There are already many solutions in the multi-core and distributed computing community. GPU (Graphics Processing Unit)-based solutions are recently gaining recognition as they offer massive parallelism without network delays. Most GPU solutions use Breadth First Traversal to utilize underlying parallelism and impose expensive restrictions on hardware due to huge memory requirements. PARSEC (Parallel Subgraph Enumeration and Counter) is the first GPU-based solution that uses Depth First Search and performs in-memory subgraph enumeration. In this thesis, PARSEC is improved by leveraging insights from traditional sequential solutions and advanced parallel programming techniques. The performance of Subgraph Enumeration is limited by the computational cost of adjacency list intersection operations. To tackle this, a smart preprocessing technique was developed for detecting opportunities for intersection reuse, which, in turn, reduces the number of intersections by up to 3.87×. A two-phase pruning technique was developed which shrinks the search space to further reduce the number of intersections by up to 6.6×. An in-depth analysis of PARSEC was conducted to overcome its load imbalance and limited hardware utilization. A hybrid parallelization scheme was developed that improves the load balance by up to 14×. Altogether, these improvements provide a geometric mean time speedup up to 4.6× across data graphs and up to 3.7× across all queries with max speedups up to 14.6×."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/116103"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Samiran Kawtikwar"],"dc:subject":["subgraph-enumeration","cuda","gpu","parallel algorithms","DFS","big graphs","graph analytics"],"dc:title":["Enhancements in high performance subgraph enumeration on graphics processors"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Industrial Engineering"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:55Z"}