TY - JOUR
T1 - Parallel on-chip power distribution network analysis on multi-core-multi-GPU platforms
AU - Feng, Zhuo
AU - Zeng, Zhiyu
AU - Li, Peng
PY - 2011/10
Y1 - 2011/10
N2 - The challenging task of analyzing on-chip power (ground) distribution networks with multimillion node complexity and beyond is key to today's large chip designs. For the first time, we show how to exploit recent massively parallel single-instruction multiple-thread (SIMT)-based graphics processing unit (GPU) platforms to tackle large-scale power grid analysis with promising performance. Several key enablers including GPU-specific algorithm design, circuit topology transformation, workload partitioning, performance tuning are embodied in our GPU-accelerated hybrid multigrid (HMD) algorithm (GpuHMD) and its implementation. We also demonstrate that using the HMD solver as a preconditioner, the conjugate gradient solver can converge much faster to the true solution with good robustness. Extensive experiments on industrial and synthetic benchmarks have shown that for DC power grid analysis using one GPU, the proposed simulation engine achieves up to 100 × runtime speedup over a state-of-the-art direct solver and more than 50 × speedup over the CPU based multigrid implementation, while utilizing a four-core-four-GPU system, a grid with eight million nodes can be solved within about 1 s. It is observed that the proposed approach scales favorably with the circuit complexity, at a rate about 1 s per two million nodes on a single GPU card.
AB - The challenging task of analyzing on-chip power (ground) distribution networks with multimillion node complexity and beyond is key to today's large chip designs. For the first time, we show how to exploit recent massively parallel single-instruction multiple-thread (SIMT)-based graphics processing unit (GPU) platforms to tackle large-scale power grid analysis with promising performance. Several key enablers including GPU-specific algorithm design, circuit topology transformation, workload partitioning, performance tuning are embodied in our GPU-accelerated hybrid multigrid (HMD) algorithm (GpuHMD) and its implementation. We also demonstrate that using the HMD solver as a preconditioner, the conjugate gradient solver can converge much faster to the true solution with good robustness. Extensive experiments on industrial and synthetic benchmarks have shown that for DC power grid analysis using one GPU, the proposed simulation engine achieves up to 100 × runtime speedup over a state-of-the-art direct solver and more than 50 × speedup over the CPU based multigrid implementation, while utilizing a four-core-four-GPU system, a grid with eight million nodes can be solved within about 1 s. It is observed that the proposed approach scales favorably with the circuit complexity, at a rate about 1 s per two million nodes on a single GPU card.
KW - Circuit simulation
KW - graphics processing units (GPUs)
KW - interconnect modeling
KW - multigrid method
KW - parallel computing
KW - power grid simulation
KW - preconditioner
UR - http://www.scopus.com/inward/record.url?scp=80051793208&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=80051793208&partnerID=8YFLogxK
U2 - 10.1109/TVLSI.2010.2059718
DO - 10.1109/TVLSI.2010.2059718
M3 - Article
AN - SCOPUS:80051793208
SN - 1063-8210
VL - 19
SP - 1823
EP - 1836
JO - IEEE Transactions on Very Large Scale Integration (VLSI) Systems
JF - IEEE Transactions on Very Large Scale Integration (VLSI) Systems
IS - 10
M1 - 5551267
ER -