Multigrid on GPU: Tackling power grid analysis on parallel SIMT platforms

Zhuo Feng, Peng Li

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

94 Scopus citations

Abstract

The challenging task of analyzing on-chip power (ground) distribution networks with multi-million 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 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 algorithm, GpuHMD, and its implementation. In particular, a proper interplay between algorithm design and SIMT architecture consideration is shown to be essential to achieve good runtime performance. Different from the standard CPU based CAD development, care must be taken to balance between computing and memory access, reduce random memory access patterns and simplify flow control to achieve efficiency on the GPU platform. Extensive experiments on industrial and synthetic benchmarks have shown that the proposed GpuHMD engine can achieve 100X runtime speedup over a stateof-the-art direct solver and be more than 15X faster than the CPU based multigrid implementation. The DC analysis of a 1.6 million-node industrial power grid benchmark can be accurately solved in three seconds with less than 50MB memory on a commodity GPU. It is observed that the proposed approach scales favorably with the circuit complexity, at a rate about one second per million nodes.

Original languageEnglish
Title of host publication2008 IEEE/ACM International Conference on Computer-Aided Design Digest of Technical Papers, ICCAD 2008
Pages647-654
Number of pages8
DOIs
StatePublished - 2008
Event2008 International Conference on Computer-Aided Design, ICCAD - San Jose, CA, United States
Duration: 10 Nov 200813 Nov 2008

Publication series

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

Conference

Conference2008 International Conference on Computer-Aided Design, ICCAD
Country/TerritoryUnited States
CitySan Jose, CA
Period10/11/0813/11/08

Fingerprint

Dive into the research topics of 'Multigrid on GPU: Tackling power grid analysis on parallel SIMT platforms'. Together they form a unique fingerprint.

Cite this