Fast algorithms for IR drop analysis in large power grid
Fast algorithms for IR drop analysis in large power grid
复制标题
DOI：
10.1109/iccad.2005.1560093
复制
发表时间：
2005-05
期刊：
影响因子：
--
通讯作者：
Yu Zhong;Martin D. F. Wong
中科院分区：
文献类型：
--
作者：
Yu Zhong;Martin D. F. Wong
由于电网的规模非常大，IR下降分析在运行时和内存使用方面已经成为一个具有计算挑战性的问题。虽然红外雨滴分析可以很自然地表述为求解线性系统的问题，但该系统太大，现有的线性求解器无法解决。在本文中，我们分别提出了基于节点逐节点遍历和基于电网逐行遍历的两种迭代算法。我们的算法非常快，并保证收敛到精确的解。事实上，它们可以被认为是求解线性系统的经典逐次过松弛迭代方法的有效实现。我们的方法充分利用了电网的特殊结构。实验结果表明，我们的算法优于目前最著名的基于随机行走的算法。对于一个1600万个节点的问题，我们基于行的算法花了26.47分钟，而基于随机行走的算法花了19.6小时。我们的基于行的算法产生了一个精确的解，而随机漫步产生了一个最大误差为5.7 mV的解。
Due to the extremely large size of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. Although IR drop analysis can be naturally formulated as the problem of solving a linear system, the system is too large to be solved by existing linear solvers. In this paper, we present two iterative algorithms based on node-by-node traversals and row-by-row traversals of the power grid, respectively. Our algorithms are extremely fast and guarantee convergence to the exact solutions. In fact, they can be considered as efficient implementations of the classical successive over relaxation iterative method for solving linear systems. Our methods take full advantage of the special structure of the power grid. Experimental results show that our algorithms out-perform the random-walk-based algorithm which is the best known method today. For a 16-million node problem, our row-based algorithm took 26.47 minutes while the random-walk-based algorithm took 19.6 hours. Our row-based algorithm produced an exact solution while the random walk produced a solution with maximum error of 5.7 mV.