Efficient parallel power grid analysis via Additive Schwarz method

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

Research output: Contribution to journalConference articlepeer-review


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 (US)
Article number6386643
Pages (from-to)399-406
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
StatePublished - 2012
Event2012 30th IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2012 - San Jose, CA, United States
Duration: Nov 5 2012Nov 8 2012

ASJC 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