Fast multipole method on GPU: Tackling 3-D capacitance extraction on massively parallel SIMD platforms

Xueqian Zhao, Zhuo Feng

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

7 Scopus citations

Abstract

To facilitate full chip capacitance extraction, field solvers are typically deployed for characterizing capacitance libraries for various interconnect structures and configurations. In the past decades, various algorithms for accelerating boundary element methods (BEM) have been developed to improve the efficiency of field solvers for capacitance extraction. This paper presents the first massively parallel capacitance extraction algorithm FMMGpu that accelerates the well-known fast multipole methods (FMM) on modern Graphics Processing Units (GPUs). We propose GPU-friendly data structures and SIMD parallel algorithm flows to facilitate the FMM-based 3-D capacitance extraction on GPU. Effective GPU performance modeling methods are also proposed to properly balance the workload of each critical kernel in our FMMGpu implementation, by taking advantage of the latest Fermi GPU's concurrent kernel executions on streaming multiprocessors (SMs). Our experimental results show that FMMGpu brings 22X to 30X speedups in capacitance extractions for various test cases. We also show that even for small test cases that may not well utilize GPU's hardware resources, the proposed cube clustering and workload balancing techniques can bring 20% to 60% extra performance improvements.

Original languageEnglish
Title of host publication2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011
Pages558-563
Number of pages6
StatePublished - 2011
Event2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011 - San Diego, CA, United States
Duration: 5 Jun 20119 Jun 2011

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X

Conference

Conference2011 48th ACM/EDAC/IEEE Design Automation Conference, DAC 2011
Country/TerritoryUnited States
CitySan Diego, CA
Period5/06/119/06/11

Keywords

  • Capacitance extraction
  • GPU
  • parallel fast multipole method

Fingerprint

Dive into the research topics of 'Fast multipole method on GPU: Tackling 3-D capacitance extraction on massively parallel SIMD platforms'. Together they form a unique fingerprint.

Cite this