Efficient parallel power grid analysis via Additive Schwarz method

Ting Yu*, Zigang Xiao, Martin D.F. Wong

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

17 Citations (Scopus)


Due to the rapid advances of integrated circuit technology, the size of power distribution network (power grid) is becoming larger and larger. There are usually multi-million nodes on a power grid. Analyzing these huge power grids has become very expensive in terms of both time and memory. This paper presents an efficient parallel implementation of the Additive Schwarz Method (ASM) for IR-drop analysis of large-scale power grid. Based on distributed memory system, a new data storage method is proposed to overcome memory bottleneck of traditional methods. Techniques including overlapping in multiple layer and irregular power grid, via detection and grouping are utilized to accelerate the simulation. Moreover, a new communication strategy exhibiting minimum communication overhead is proposed. The proposed method is very accurate in the final solution, with the maximum error less than 0.1mv. Experimental results on industrial medium size benchmarks show that the proposed method achieves more than 110X speedup over a state-of-the-art direct LU solver. The proposed approach can easily solve very large-scale benchmarks, while LU solver fails to obtain the solution because of system memory limitation. It is the first time reported in literature that IR-drop analysis of power grid with over 190M nodes is successfully solved within 5 minutes.

Original languageEnglish
Title of host publicationICCAD '12: Proceedings of the International Conference on Computer-Aided Design
EditorsAlan J. Hu
PublisherAssociation for Computing Machinery (ACM)
Number of pages8
ISBN (Print)9781450315739
Publication statusPublished - 5 Nov 2012
Event2012 30th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2012 - San Jose, CA, United States
Duration: 5 Nov 20128 Nov 2012

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
PublisherAssociation for Computing Machinery
ISSN (Print)1092-3152


Conference2012 30th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2012
Country/TerritoryUnited States
CitySan Jose, CA

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Efficient parallel power grid analysis via Additive Schwarz method'. Together they form a unique fingerprint.

Cite this