Solutions for graph compression problems and applications

Lai, Tin-Yin

Permalink

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

Description

Title

Solutions for graph compression problems and applications

Author(s)

Lai, Tin-Yin

Issue Date

2023-04-26

Director of Research (if dissertation) or Advisor (if thesis)

Wong, Martin D F

Doctoral Committee Chair(s)

Wong, Martin D F

Committee Member(s)

• Hwu, Wen-mei
• Chen, Deming
• Hu, Yih-Chun

Department of Study

Electrical & Computer Eng

Discipline

Electrical & Computer Engr

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Graph Algorithm
• Runtime Optimization
• Parallel Programming
• GPU Programming

Abstract

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.

Graduation Semester

2023-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2023 Tin-Yin Lai

Owning Collections