Solutions for graph compression problems and applications

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2023

Author dc:creator

• Lai, Tin-Yin

Contributors dc:contributor

• Wong, Martin D F
• Hwu, Wen-mei
• Chen, Deming
• Hu, Yih-Chun

• Graph Algorithm
• Runtime Optimization
• Parallel Programming
• Gpu Programming

Statement dc:rights

• Copyright 2023 Tin-Yin Lai

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/120514

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F120514