A Selected Inversion Approach for Locality Driven Vectorless Power Grid Verification

Vectorless power grid verification is a practical approach for early stage safety check without input current patterns. The power grid is usually formulated as a linear system and requires intensive matrix inversion and numerous linear programming (LP), which is extremely time-consuming for large-sc...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on very large scale integration (VLSI) systems 2015-11, Vol.23 (11), p.2617-2628
Main Authors: Yang, Jianlei, Cai, Yici, Zhou, Qiang, Zhao, Wei
Format: Article
Language:English
Subjects:
Accuracy
Computation
Cost engineering
Electric utilities
Inversions
IR drop
Linear systems
locality
Mathematical model
Mathematical models
Noise
Partitioning
Power grids
RLC circuits
selected inversion
signal integrity
Sparse matrices
Upper bound
vectorless power grid verification
Vectors
Very large scale integration
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Vectorless power grid verification is a practical approach for early stage safety check without input current patterns. The power grid is usually formulated as a linear system and requires intensive matrix inversion and numerous linear programming (LP), which is extremely time-consuming for large-scale power grid verification. In this paper, the power grid is represented in the manner of domain-decomposition approach, and we propose a selected inversion technique to reduce the computation cost of matrix inversion for vectorless verification. The locality existence among power grids is exploited to decide which blocks of matrix inversion should be computed while remaining blocks are not necessary. The vectorless verification could be purposefully performed by this manner of selected inversion, while previous direct approaches are required to perform full matrix inversion and then discard small entries to reduce the complexity of LP. Meanwhile, constraint locality is proposed to improve the verification accuracy. In addition, a concept of quasi-Poisson block is introduced to exploit grid locality among realistic power grids and a scheme of pad-aware partitioning is proposed to enable the selected inversion approach available for practical use. Experimental results show that the proposed approach could achieve significant speedups compared with previous approaches while still guaranteeing the quality of solution accuracy.
ISSN:1063-8210
1557-9999
DOI:10.1109/TVLSI.2014.2365520