An efficient spectral graph sparsification approach to scalable reduction of large flip-chip power grids

Xueqian Zhao, Zhuo Feng, Cheng Zhuo

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

10 Scopus citations

Abstract

Existing state-of-The-Art realizable RC reduction methods may not be suitable for scalable power grid reductions due to the fast growing computational complexity and the large number of ports. In this work, we present a scalable power grid reduction method for reducing large-scale flip-chip power grids based on recent spectral graph sparsification techniques. The first step of the proposed approach aggressively reduces the large power grid blocks into much smaller power grid blocks by properly matching the effective resistances of the original power grid networks. Next, an efficient spectral graph sparsification scheme is introduced to dramatically sparsify the relatively dense power grid blocks that are generated during the previous step. In the last, an effective grid compensation scheme is proposed to further improve the model accuracy of the reduced and sparsified power grid. Since reduction of each power grid block can be performed independently, our method can be easily accelerated on parallel computers, and therefore expected to be capable of handling large power grid designs as well as incremental designs. Extensive experimental results show that our method can scale linearly with power grid sizes and efficiently reduce industrial power grids sizes by 20X without loss of much accuracy in both DC and transient analysis.

Original languageEnglish
Title of host publication2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers
Pages218-223
Number of pages6
EditionJanuary
ISBN (Electronic)9781479962785
DOIs
StatePublished - 5 Jan 2015
Event2014 33rd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - San Jose, United States
Duration: 2 Nov 20146 Nov 2014

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
NumberJanuary
Volume2015-January
ISSN (Print)1092-3152

Conference

Conference2014 33rd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014
Country/TerritoryUnited States
CitySan Jose
Period2/11/146/11/14

Fingerprint

Dive into the research topics of 'An efficient spectral graph sparsification approach to scalable reduction of large flip-chip power grids'. Together they form a unique fingerprint.

Cite this