TY - JOUR
T1 - Locality-driven parallel static analysis for power delivery networks
AU - Zeng, Zhiyu
AU - Feng, Zhuo
AU - Li, Peng
AU - Sarin, Vivek
PY - 2011/6
Y1 - 2011/6
N2 - Large VLSI on-chip Power Delivery Networks (PDNs) are challenging to analyze due to the sheer network complexity. In this article, a novel parallel partitioning-based PDN analysis approach is presented. We use the boundary circuit responses of each partition to divide the full grid simulation problem into a set of independent subgrid simulation problems. Instead of solving exact boundary circuit responses, a more efficient scheme is proposed to provide near-exact approximation to the boundary circuit responses by exploiting the spatial locality of the flip-chip-type power grids. This scheme is also used in a block-based iterative error reduction process to achieve fast convergence. Detailed computational cost analysis and performance modeling is carried out to determine the optimal (or near-optimal) number of partitions for parallel implementation. Through the analysis of several large power grids, the proposed approach is shown to have excellent parallel efficiency, fast convergence, and favorable scalability. Our approach can solve a 16-million-node power grid in 18 seconds on an IBM p5-575 processing node with 16 Power5+ processors, which is 18.8X faster than a state-of-the-art direct solver.
AB - Large VLSI on-chip Power Delivery Networks (PDNs) are challenging to analyze due to the sheer network complexity. In this article, a novel parallel partitioning-based PDN analysis approach is presented. We use the boundary circuit responses of each partition to divide the full grid simulation problem into a set of independent subgrid simulation problems. Instead of solving exact boundary circuit responses, a more efficient scheme is proposed to provide near-exact approximation to the boundary circuit responses by exploiting the spatial locality of the flip-chip-type power grids. This scheme is also used in a block-based iterative error reduction process to achieve fast convergence. Detailed computational cost analysis and performance modeling is carried out to determine the optimal (or near-optimal) number of partitions for parallel implementation. Through the analysis of several large power grids, the proposed approach is shown to have excellent parallel efficiency, fast convergence, and favorable scalability. Our approach can solve a 16-million-node power grid in 18 seconds on an IBM p5-575 processing node with 16 Power5+ processors, which is 18.8X faster than a state-of-the-art direct solver.
KW - Locality
KW - Parallel
KW - Partitioning based
KW - Power delivery network
KW - Static analysis
UR - http://www.scopus.com/inward/record.url?scp=79960696185&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=79960696185&partnerID=8YFLogxK
U2 - 10.1145/1970353.1970361
DO - 10.1145/1970353.1970361
M3 - Article
AN - SCOPUS:79960696185
SN - 1084-4309
VL - 16
JO - ACM Transactions on Design Automation of Electronic Systems
JF - ACM Transactions on Design Automation of Electronic Systems
IS - 3
M1 - 28
ER -