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

Zhiqiang Zhao, Zhuo Feng

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

11 Scopus citations

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.

Original languageEnglish
Title of host publicationProceedings of the 54th Annual Design Automation Conference 2017, DAC 2017
ISBN (Electronic)9781450349277
DOIs
StatePublished - 18 Jun 2017
Event54th Annual Design Automation Conference, DAC 2017 - Austin, United States
Duration: 18 Jun 201722 Jun 2017

Publication series

NameProceedings - Design Automation Conference
VolumePart 128280
ISSN (Print)0738-100X

Conference

Conference54th Annual Design Automation Conference, DAC 2017
Country/TerritoryUnited States
CityAustin
Period18/06/1722/06/17

Keywords

  • Vectorless verification
  • algebraic multigrid
  • graph sparsification
  • spectral graph theory

Fingerprint

Dive into the research topics of 'A Spectral Graph Sparsification Approach to Scalable Vectorless Power Grid Integrity Verification'. Together they form a unique fingerprint.

Cite this