Visible to the public A Spectral Graph Sparsification Approach to Scalable Vectorless Power Grid Integrity Verification

TitleA Spectral Graph Sparsification Approach to Scalable Vectorless Power Grid Integrity Verification
Publication TypeConference Paper
Year of Publication2017
AuthorsZhao, Zhiqiang, Feng, Z.
Conference Name2017 54th ACM/EDAC/IEEE Design Automation Conference (DAC)
Keywordsalgebraic 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.

URLhttps://dl.acm.org/citation.cfm?doid=3061639.3062193
DOI10.1145/3061639.3062193
Citation Keyzhao_spectral_2017