TY - GEN
T1 - An efficient spectral graph sparsification approach to scalable reduction of large flip-chip power grids
AU - Zhao, Xueqian
AU - Feng, Zhuo
AU - Zhuo, Cheng
N1 - Publisher Copyright:
© 2014 IEEE.
PY - 2015/1/5
Y1 - 2015/1/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84936880848&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84936880848&partnerID=8YFLogxK
U2 - 10.1109/ICCAD.2014.7001355
DO - 10.1109/ICCAD.2014.7001355
M3 - Conference contribution
AN - SCOPUS:84936880848
T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD
SP - 218
EP - 223
BT - 2014 IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014 - Digest of Technical Papers
T2 - 2014 33rd IEEE/ACM International Conference on Computer-Aided Design, ICCAD 2014
Y2 - 2 November 2014 through 6 November 2014
ER -