Back to search

Michigan Technological University

HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS

Abstract

dc:description.abstract

Recent research shows that by leveraging the key spectral properties of eigenvalues and eigenvectors of graph Laplacians, more efficient algorithms can be developed for tackling many graph-related computing tasks. In this dissertation, spectral methods are utilized for achieving faster algorithms in the applications of very-large-scale integration (VLSI) computer-aided design (CAD) First, a scalable algorithmic framework is proposed for effective-resistance preserving spectral reduction of large undirected graphs. The proposed method allows computing much smaller graphs while preserving the key spectral (structural) properties of the original graph. Our framework is built upon the following three key components: a spectrum-preserving node aggregation and reduction scheme, a spectral graph sparsification framework with iterative edge weight scaling, as well as effective-resistance preserving post-scaling and iterative solution refinement schemes. We show that the resultant spectrally-reduced graphs can robustly preserve the first few nontrivial eigenvalues and eigenvectors of the original graph Laplacian and thus allow for developing highly-scalable spectral graph partitioning and circuit simulation algorithms. Based on the framework of the spectral graph reduction, a Sparsified graph-theoretic Algebraic Multigrid (SAMG) is proposed for solving large Symmetric Diagonally Dominant (SDD) matrices. The proposed SAMG framework allows efficient construction of nearly-linear sized graph Laplacians for coarse-level problems while maintaining good spectral approximation during the AMG setup phase by leveraging a scalable spectral graph sparsification engine. Our experimental results show that the proposed method can offer more scalable performance than existing graph-theoretic AMG solvers for solving large SDD matrices in integrated circuit (IC) simulations, 3D-IC thermal analysis, image processing, finite element analysis as well as data mining and machine learning applications. Finally, the spectral methods are applied to power grid and thermal integrity verification applications. This dissertation introduces a vectorless power grid and thermal integrity verification framework that allows computing worst-case voltage drop or thermal profiles across the entire chip under a set of local and global workload (power density) constraints. To address the computational challenges introduced by the large 3D mesh-structured thermal grids, we apply the spectral graph reduction approach for highly-scalable vectorless thermal (or power grids) verification of large chip designs. The effectiveness and efficiency of our approach have been demonstrated through extensive experiments.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy in Computer Engineering (PhD)
Level thesis:degree_level
Open Access Dissertation
Discipline thesis:degree_discipline
Department of Electrical and Computer Engineering

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhao, Zhiqiang
Committee members dc:contributor.committeemember
  • Jiguang Sun
  • Chee-Wooi Ten
  • Benjamin W. Ong
  • Saeid Nooshabadi
Contributors dc:contributor
  • Zhuo Feng
  • Glen E. Archer

Subjects

dc:subject × 8

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Michigan Technological University
Base URL
digitalcommons.mtu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhao, Zhiqiang. HIGH-PERFORMANCE SPECTRAL METHODS FOR COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS. Open Access Dissertation thesis, https://doi.org/10.37099/mtu.dc.etdr/1138