Prior methods for simulating SPICE-accurate post-layout circuits do not scale well due to the superlinear complexity of existing sparse matrix solution algorithms, such as LU decomposition methods. To address the challenging computational bottlenecks, this research project aims to leverage emerging graph sparsification techniques and heterogeneous parallel computers for scalable SPICE-accurate post-layout integrated circuit simulations in both time and frequency domains. Recent graph sparsification research allows computing ultra-sparse graph proxies for approximating the original undirected graphs, which can immediately accelerate many numerical and graph-related algorithms.

However, integrated circuit networks usually involve not only undirected edges but also directed edges. To effectively accelerate sparse matrix solvers in circuit simulation tasks, three different types of circuits have been investigated during the four-year research study by leveraging recent graph sparsification techniques: 1) time-domain SPICE simulation of interconnect-dominant circuits, 2) time-domain SPICE simulation of transistor-dominant circuits, 3) frequency-domain harmonic balance (HB) analysis of radio-frequency (RF) circuits. We have proposed brand new circuit simulation algorithms that are highly scalable for handling extremely large circuit systems, allowing large-scale post-layout circuit designs to be analyzed in nearly-linear time and space. Our main technical contributions have been summarized as follows:

1. During the first two years of this project, we have developed a series graph sparsification techniques for sparsifying large time-domain and frequency domain post-layout integrated circuits (modified nodal analysis matrices) that can be subsequently leveraged for achieving nearly-linear complexity runtime/memory cost performance. Additionally, we successfully developed performance-guided graph sparsification frameworks for time-domain and frequency-domain SPICE-accurate circuit simulations that allow automatically identifying the optimal graph sparsification configuration that can lead to optimal runtime performance.
2. We have also developed a highly-parallel graph-theoretic preconditioning method for Harmonic Balance analysis of microwave and RF circuits, which achieved up to 20X speedups compared to the state-of-the-art HB simulation algorithm published in DAC’09 by Berkeley Design Automation. The new method is built upon our recent graph sparsification research as well as a sparse block matrix solver optimized for modern CPU-GPU heterogeneous computing platforms. 
3. We developed a nearly-linear time yet practically-efficient spectral graph sparsification algorithm that can immediately lead to the development of nearly-linear time sparse symmetric diagonally-dominant (SDD) matrix solvers and spectral graph (data) partitioning (clustering) algorithms. This work can potentially allow constructing circuit proxies with guaranteed high quality and sparsity, which will be critical for future nanoscale IC designs that involve increasingly stronger couplings due to complex parasitics components.
4. We have released a preliminary software "GRASS: GRAph Spectral Sparsifier" (https://sites.google.com/mtu.edu/zhuofeng-graphspar/home). GRASS is the first highly efficient graph spectral sparsification engine that scales almost linearly with the size of the input graph Laplacian. The spectrally sparsified graphs computed by GRASS can approximately preserve the distances or effective resistances between vertices so that much faster numerical and graph-related algorithms can be developed based on these sparsified graphs. For example, spectrally sparsified social (data) networks may allow for more efficiently modeling, mining and analysis of large social (data) networks, spectrally sparsified circuit networks may lead to more efficient simulation, optimization and verification of large integrated circuit systems, etc.
5. We have been trying hard to disseminate the research outcome of this research in the industrial and academic sectors by publishing in top IEEE/ACM conferences and journals. We also have delivered many research presentations to industrial partners, such as Cadence Design Systems and Intel Corporation, as well as many universities, such as University of California San Diego, Duke University, Carnegie Mellon University, The University of Pittsburgh, University at Buffalo, Lehigh University, University of Houston, Tsinghua University, Peking University, The University of Electronic Science and Technology of China, Shenzhen University, Fudan University, ShanghaiTech University, Sun Yat-Sen University, etc, to disseminate our latest research results.

The research investigation of graph sparsification techniques for IC simulations will immediately benefit the solver developments for large-scale sparse matrix problems involved in other engineering fields that require solving large linear/nonlinear partial differential equations, such as computational fluid dynamics, and computational electromagnetics. It is expected that graph sparsification related research outcome will immediately benefit other research communities that heavily rely on scientific computing, such as machine learning, data mining, computer vision, image processing, network analysis, and computational biology. 

 By leveraging the research results from this project, people may run much larger simulation/computation tasks on relatively small (personal) computers in the near future without introducing additional cost. Even on small, low-power mobile computing devices, traditionally very costly functions, such as circuit simulations, data clustering, matrix solvers, etc. can be potentially be executed locally using multi-core CPUs and many-core GPUs without leveraging power-consuming cloud computing facilities.

Last Modified: 11/22/2017
Modified by: Zhuo Feng