TY - GEN
T1 - Efficient second-order iterative methods for IR drop analysis in power grid
AU - Zhong, Yu
AU - Wong, Martin D.F.
PY - 2007
Y1 - 2007
N2 - Due to the extremely large sizes of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. It has been shown in [5] that first-order iterative algorithms based on node-by-node and row-by-row traversals of the power grid have both accuracy and runtime advantages over the well-known Random-Walk method. In this paper, we propose second-order iterative algorithms that can significantly reduce the runtime. The new algorithms are extremely fast, and we prove that they guarantee converge to the exact solutions. Experimental results show that our algorithms outperform the Random-Walk algorithm in [2] and algorithms in [5]. For a 25-million node problem, while the Random-Walk algorithm takes 2 days with maximum error of 6.1 mV, the fastest algorithm in [5] takes 50 minutes, and our second-order row-based algorithm takes 32 minutes to get an exact solution. Moreover, we can get a solution with maximum error 2 mV in 10 minutes.
AB - Due to the extremely large sizes of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. It has been shown in [5] that first-order iterative algorithms based on node-by-node and row-by-row traversals of the power grid have both accuracy and runtime advantages over the well-known Random-Walk method. In this paper, we propose second-order iterative algorithms that can significantly reduce the runtime. The new algorithms are extremely fast, and we prove that they guarantee converge to the exact solutions. Experimental results show that our algorithms outperform the Random-Walk algorithm in [2] and algorithms in [5]. For a 25-million node problem, while the Random-Walk algorithm takes 2 days with maximum error of 6.1 mV, the fastest algorithm in [5] takes 50 minutes, and our second-order row-based algorithm takes 32 minutes to get an exact solution. Moreover, we can get a solution with maximum error 2 mV in 10 minutes.
UR - http://www.scopus.com/inward/record.url?scp=46649120326&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=46649120326&partnerID=8YFLogxK
U2 - 10.1109/ASPDAC.2007.358082
DO - 10.1109/ASPDAC.2007.358082
M3 - Conference contribution
AN - SCOPUS:46649120326
SN - 1424406293
SN - 9781424406296
T3 - Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
SP - 768
EP - 773
BT - Proceedings of the ASP-DAC 2007 - Asia and South Pacific Design Automation Conference 2007
T2 - ASP-DAC 2007 - Asia and South Pacific Design Automation Conference 2007
Y2 - 23 January 2007 through 27 January 2007
ER -