A Spectral Graph Sparsification Approach to Scalable Vectorless Power Grid Integrity Verification
Title | A Spectral Graph Sparsification Approach to Scalable Vectorless Power Grid Integrity Verification |
Publication Type | Conference Paper |
Year of Publication | 2017 |
Authors | Zhao, Zhiqiang, Feng, Z. |
Conference Name | 2017 54th ACM/EDAC/IEEE Design Automation Conference (DAC) |
Keywords | algebraic multigrid, compositionality, graph sparsification, graph theory, graph-theoretic algebraic multigrid algorithmic framework, integrated circuit design, Integrated circuit modeling, Laplace equations, Metrics, Nanoscale devices, nanoscale power delivery networks, Optimization methods, power grid designs, power grids, power supply circuits, pubcrawl, resilience, Resiliency, Scalability, scalable multilevel integrity verification framework, scalable vectorless power grid integrity verification, scalable verification, Sensitivity, spectral graph sparsification, spectral graph theory, spectral power grid sparsifiers, Vectorless verification, vectorless verification framework |
Abstract | Vectorless integrity verification is becoming increasingly critical to robust design of nanoscale power delivery networks (PDNs). To dramatically improve efficiency and capability of vectorless integrity verifications, this paper introduces a scalable multilevel integrity verification framework by leveraging a hierarchy of almost linear-sized spectral power grid sparsifiers that can well retain effective resistances between nodes, as well as a recent graph-theoretic algebraic multigrid (AMG) algorithmic framework. As a result, vectorless integrity verification solution obtained on coarse level problems can effectively help find the solution of the original problem. Extensive experimental results show that the proposed vectorless verification framework can always efficiently and accurately obtain worst-case scenarios in even very large power grid designs. |
URL | https://dl.acm.org/citation.cfm?doid=3061639.3062193 |
DOI | 10.1145/3061639.3062193 |
Citation Key | zhao_spectral_2017 |
- power supply circuits
- vectorless verification framework
- Vectorless verification
- spectral power grid sparsifiers
- spectral graph theory
- spectral graph sparsification
- Sensitivity
- scalable verification
- scalable vectorless power grid integrity verification
- scalable multilevel integrity verification framework
- Scalability
- Resiliency
- resilience
- pubcrawl
- algebraic multigrid
- power grids
- power grid designs
- Optimization methods
- nanoscale power delivery networks
- Nanoscale devices
- Metrics
- Laplace equations
- Integrated circuit modeling
- integrated circuit design
- graph-theoretic algebraic multigrid algorithmic framework
- graph theory
- graph sparsification
- Compositionality