{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/120514"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/120514","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Solutions for graph compression problems and applications","abstract":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2025-05-01","abstract_html":"Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2025-05-01","abstract_has_math":false,"creators":["Lai, Tin-Yin"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical & Computer Engr","degree_department":null,"school":null,"contributors":["Wong, Martin D F","Hwu, Wen-mei","Chen, Deming","Hu, Yih-Chun"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2023,"date_issued":"2023-05","date_published":"2023-05","updated_at":"2026-07-22T22:24:57Z","subjects":["Graph Algorithm","Runtime Optimization","Parallel Programming","Gpu Programming"],"languages":["en","eng"],"rights":["Copyright 2023 Tin-Yin Lai"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/120514","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Wong, Martin D F","Hwu, Wen-mei","Chen, Deming","Hu, Yih-Chun"]},{"key":"dc:creator","label":"Author","values":["Lai, Tin-Yin"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2023-05","2023-04-26"]},{"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":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"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":["Graph Algorithm","Runtime Optimization","Parallel Programming","Gpu Programming"]}]},{"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 2023 Tin-Yin Lai"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/120514"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2025-05-01","The student, Tin-Yin Lai, accepted the attached license on 2023-04-14 at 23:07.","The student, Tin-Yin Lai, submitted this Dissertation for approval on 2023-04-14 at 23:22.","This Dissertation was approved for publication on 2023-04-26 at 13:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18995 on 2023-09-01 at 17:20:28","Graph compression techniques are commonly used to solve large-scale graph problems. This thesis presents four chapters (Chapters 2-5) with new graph compression techniques and their optimized implementations for quality and speed. In Chapter 2, we address a long-standing problem in incremental timing analysis on hierarchical circuit design. During the design cycle, circuit designers modify the circuits hundreds of thousands of times. However, the flat timing analysis is time-consuming. We propose timing macro modeling methods to accelerate multi-run timing analysis by building a library by shrinking the circuit graph. With graph pruning and tree reduction, our graph can be shrunk to less than 20% of its original edge number. We also consider parallel computing by independently computing paths to speed up graph compression. In Chapter 3, we optimize the well-known Louvain graph clustering algorithm using graph compression and GPU parallel computation. Our novel graph-covering method enables the Louvain algorithm to speed up by more than ×10 compared to the sequential version. To further improve the algorithm, we use maximum clique algorithms to optimize the graph covering part of the graph clustering algorithms. In Chapter 4, we present a highly parallel algorithm for the maximum clique problem (MCP). This work can be used to improve the GPU graph clustering algorithm in Chapter 3. We made a key observation that a maximum clique must lie along a Depth-First-Search path. This observation together with many heuristic bounding methods shrinking the solution space is the foundation of our maximum-clique algorithm. We implemented our maximum-clique algorithm on GPU. In Chapter 5, we address a tedious GPU implementation issue for the graph clustering algorithm in Chapter 3. To solve the problem of repeatedly manually tuning in the GPU profiling process in the graph clustering work, we automatically optimize the device configuration in our previous work using Neural Architecture Search (NAS) under the Reinforcement Learning (RL) framework. We optimize the inference computation in parallel on multithread computing units and reduce the runtime to 78% in MobileNet V2 and 89% in MobileNet V3. Finally, we conclude the dissertation in Chapter 6."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Solutions for graph compression problems and applications"]}]}],"canonical_facts":{"dc:contributor":["Wong, Martin D F","Hwu, Wen-mei","Chen, Deming","Hu, Yih-Chun"],"dc:creator":["Lai, Tin-Yin"],"dc:date":["2023-05","2023-04-26"],"dc:description":["Submission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2025-05-01","The student, Tin-Yin Lai, accepted the attached license on 2023-04-14 at 23:07.","The student, Tin-Yin Lai, submitted this Dissertation for approval on 2023-04-14 at 23:22.","This Dissertation was approved for publication on 2023-04-26 at 13:37.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18995 on 2023-09-01 at 17:20:28","Graph compression techniques are commonly used to solve large-scale graph problems. This thesis presents four chapters (Chapters 2-5) with new graph compression techniques and their optimized implementations for quality and speed. In Chapter 2, we address a long-standing problem in incremental timing analysis on hierarchical circuit design. During the design cycle, circuit designers modify the circuits hundreds of thousands of times. However, the flat timing analysis is time-consuming. We propose timing macro modeling methods to accelerate multi-run timing analysis by building a library by shrinking the circuit graph. With graph pruning and tree reduction, our graph can be shrunk to less than 20% of its original edge number. We also consider parallel computing by independently computing paths to speed up graph compression. In Chapter 3, we optimize the well-known Louvain graph clustering algorithm using graph compression and GPU parallel computation. Our novel graph-covering method enables the Louvain algorithm to speed up by more than ×10 compared to the sequential version. To further improve the algorithm, we use maximum clique algorithms to optimize the graph covering part of the graph clustering algorithms. In Chapter 4, we present a highly parallel algorithm for the maximum clique problem (MCP). This work can be used to improve the GPU graph clustering algorithm in Chapter 3. We made a key observation that a maximum clique must lie along a Depth-First-Search path. This observation together with many heuristic bounding methods shrinking the solution space is the foundation of our maximum-clique algorithm. We implemented our maximum-clique algorithm on GPU. In Chapter 5, we address a tedious GPU implementation issue for the graph clustering algorithm in Chapter 3. To solve the problem of repeatedly manually tuning in the GPU profiling process in the graph clustering work, we automatically optimize the device configuration in our previous work using Neural Architecture Search (NAS) under the Reinforcement Learning (RL) framework. We optimize the inference computation in parallel on multithread computing units and reduce the runtime to 78% in MobileNet V2 and 89% in MobileNet V3. Finally, we conclude the dissertation in Chapter 6."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/120514"],"dc:language":["en","eng"],"dc:rights":["Copyright 2023 Tin-Yin Lai"],"dc:subject":["Graph Algorithm","Runtime Optimization","Parallel Programming","Gpu Programming"],"dc:title":["Solutions for graph compression problems and applications"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Electrical & Computer Engr"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:57Z"}