TY - GEN
T1 - A Spectral Graph Sparsification Approach to Scalable Vectorless Power Grid Integrity Verification
AU - Zhao, Zhiqiang
AU - Feng, Zhuo
N1 - Publisher Copyright:
© 2017 ACM.
PY - 2017/6/18
Y1 - 2017/6/18
N2 - 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.
AB - 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.
KW - Vectorless verification
KW - algebraic multigrid
KW - graph sparsification
KW - spectral graph theory
UR - http://www.scopus.com/inward/record.url?scp=85023648300&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85023648300&partnerID=8YFLogxK
U2 - 10.1145/3061639.3062193
DO - 10.1145/3061639.3062193
M3 - Conference contribution
AN - SCOPUS:85023648300
T3 - Proceedings - Design Automation Conference
BT - Proceedings of the 54th Annual Design Automation Conference 2017, DAC 2017
T2 - 54th Annual Design Automation Conference, DAC 2017
Y2 - 18 June 2017 through 22 June 2017
ER -