A Selected Inversion Approach for Locality Driven Vectorless Power Grid Verification
A Selected Inversion Approach for Locality Driven Vectorless Power Grid Verification
复制标题
用于局部驱动无矢量电网验证的选择性反演方法
DOI：
10.1109/tvlsi.2014.2365520
复制
发表时间：
2015
影响因子：
2.8
通讯作者：
Wei Zhao
中科院分区：
文献类型：
--
作者：
Jianlei Yang;Yici Cai;Qiang Zhou;Wei Zhao
无矢量电网校验是一种不需要输入电流模式的早期安全校验方法。电网通常是一个线性系统，需要密集的矩阵求逆和大量的线性规划（LP），这是非常耗时的大规模电网验证。在本文中，电网表示的方式域分解的方法，我们提出了一个选择性的逆技术，以减少计算成本的矩阵求逆无向量验证。该算法利用电网间的局部性来决定哪些块需要求逆，而其余块则不需要。无向量验证可以通过这种选择求逆的方式有目的地执行，而之前的直接方法需要执行完全矩阵求逆，然后丢弃小条目以降低LP的复杂性。同时，为了提高验证精度，提出了约束局部性的概念.此外，准泊松块的概念被引入到现实的电网中，利用网格的局部性和焊盘感知分区的计划，提出了使所选择的反演方法可用于实际使用。实验结果表明，该方法可以实现显着的加速比与以前的方法相比，同时仍然保证解决方案的精度质量。
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.