{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T13:18:11Z","timestamp":1792156691936,"version":"4.4.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2014,6,1]],"date-time":"2014-06-01T00:00:00Z","timestamp":1401580800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>Power grid design and analysis is a critical part of modern VLSI chip design and demands tools for accurate modeling and efficient analysis. The process of power grid design is inherently iterative, during which numerous small changes are made to an initial design, either to enhance the design or to fix design constraint violations. Due to the large sizes of power grids in modern chips, updating the solution for these perturbations can be a computationally intensive task. In this work, we first introduce an accurate modeling methodology for power grids that, contrary to conventional models, can result in asymmetrical equations. Next, we propose an efficient and accurate incremental solver that utilizes the backward random walks to identify the region of influence of the perturbation. The solution of the network is then updated for this significantly smaller region only. The proposed algorithm is capable of handling both symmetrical and asymmetrical power grid equations. Moreover, it can handle consecutive perturbations without any degradation in the quality of the solution. Experimental results show speedups of up to 13\u00d7 for our incremental solver, as compared to a full resolve of the power grid.<\/jats:p>","DOI":"10.1145\/2611763","type":"journal-article","created":{"date-parts":[[2014,6,17]],"date-time":"2014-06-17T12:38:13Z","timestamp":1403008693000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Incremental Analysis of Power Grids Using Backward Random Walks"],"prefix":"10.1145","volume":"19","author":[{"given":"Baktash","family":"Boghrati","sequence":"first","affiliation":[{"name":"University of Minnesota, Minneapolis, MN"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sachin S.","family":"Sapatnekar","sequence":"additional","affiliation":[{"name":"University of Minnesota, Minneapolis, MN"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,6,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"E. Anderson Z. Bai C. Bischof S. Blackford J. Demmel J. Dongarra J. Du Croz A. Greenbaum S. Hammarling A. McKenney and D. Sorensen. 1999. LAPACK Users' Guide 3rd Ed. SIAM Philadelphia PA.   E. Anderson Z. Bai C. Bischof S. Blackford J. Demmel J. Dongarra J. Du Croz A. Greenbaum S. Hammarling A. McKenney and D. Sorensen. 1999. LAPACK Users' Guide 3 rd Ed. SIAM Philadelphia PA.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC'10)","author":"Boghrati B.","unstructured":"B. Boghrati and S. Sapatnekar . 2010. Incremental solution of power grids using random walks . In Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC'10) . 757--762. B. Boghrati and S. Sapatnekar. 2010. Incremental solution of power grids using random walks. In Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC'10). 757--762."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC'12)","author":"Boghrati B.","unstructured":"B. Boghrati and S. Sapatnekar . 2012. Incremental power network analysis using backward random walks . In Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC'12) . 41--46. B. Boghrati and S. Sapatnekar. 2012. Incremental power network analysis using backward random walks. In Proceedings of the Asia and South Pacific Design Automation Conference (ASPDAC'12). 41--46."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2007.09.003"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2004.1382626"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'07)","author":"Fu Y.","unstructured":"Y. Fu , R. Panda , B. Reschke , S. Sundareswaran , and M. Zhao . 2007. A novel technique for incremental analysis of on-chip power distribution networks . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'07) . 817--823. Y. Fu, R. Panda, B. Reschke, S. Sundareswaran, and M. Zhao. 2007. A novel technique for incremental analysis of on-chip power distribution networks. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'07). 817--823."},{"key":"e_1_2_1_7_1","volume-title":"Matrix Computations","author":"Golub G. H.","unstructured":"G. H. Golub and C. F. Van Loan . 1996. Matrix Computations 3 rd Ed. Johns Hopkins University Press , Baltimore, MD . G. H. Golub and C. F. Van Loan. 1996. Matrix Computations 3rd Ed. Johns Hopkins University Press, Baltimore, MD.","edition":"3"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 4th International Symposium on Circuits and Systems (ISCAS'04)","volume":"5","author":"Guo W.","unstructured":"W. Guo , S. Tan , Z. Luo , and X. Hong . 2004. Partial randomwalk for large linear network analysis . In Proceedings of the 4th International Symposium on Circuits and Systems (ISCAS'04) . Vol. 5 . 173--177. W. Guo, S. Tan, Z. Luo, and X. Hong. 2004. Partial randomwalk for large linear network analysis. In Proceedings of the 4th International Symposium on Circuits and Systems (ISCAS'04). Vol. 5. 173--177."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"J. M. Hammersley and D. C. Handscomb. 1964. Monte Carlo Methods. Taylor and Francis.  J. M. Hammersley and D. C. Handscomb. 1964. Monte Carlo Methods. Taylor and Francis.","DOI":"10.1007\/978-94-009-5819-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1973009.1973051"},{"key":"e_1_2_1_11_1","unstructured":"I. Nangate. 2014. NANGate. http:\/\/www.si2.org\/openeda.si2.org\/projects\/nangatelib.  I. Nangate. 2014. NANGate. http:\/\/www.si2.org\/openeda.si2.org\/projects\/nangatelib."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1356802.1356895"},{"key":"e_1_2_1_13_1","unstructured":"L. T. Pillage R. A. Rohrer and C. Visweswariah. 1994. Electronic Circuit and System Simulation Methods. McGraw-Hill New York.   L. T. Pillage R. A. Rohrer and C. Visweswariah. 1994. Electronic Circuit and System Simulation Methods. McGraw-Hill New York."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775860"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2005.850863"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'05)","author":"Qian H.","unstructured":"H. Qian and S. S. Sapatnekar . 2005. A hybrid linear equation solver and its application in quadratic placement . In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'05) . 905--909. H. Qian and S. S. Sapatnekar. 2005. A hybrid linear equation solver and its application in quadratic placement. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD'05). 905--909."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/07068713X"},{"key":"e_1_2_1_18_1","volume-title":"Iterative Methods for Sparse Linear Systems","author":"Saad Y.","unstructured":"Y. Saad . 2003. Iterative Methods for Sparse Linear Systems 2 nd Ed. SIAM , Philadelphia, PA . Y. Saad. 2003. Iterative Methods for Sparse Linear Systems 2nd Ed. SIAM, Philadelphia, PA.","edition":"2"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/981066.981093"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2429384.2429467"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391469.1391646"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/337292.337355"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2611763","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2611763","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:34Z","timestamp":1750230094000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2611763"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.1145\/2611763"],"URL":"https:\/\/doi.org\/10.1145\/2611763","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6]]},"assertion":[{"value":"2013-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}