skip to main content
10.1145/2024724.2024853acmconferencesArticle/Chapter ViewAbstractPublication PagesdacConference Proceedingsconference-collections
research-article

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

Published: 05 June 2011 Publication History

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.

References

[1]
K. Nabors and J. White. FastCap: a multipole accelerated 3-D capacitance extraction program. IEEE Trans. on Computer-Aided Design, 10(11):1447--1459, Nov. 1991.
[2]
J. Phillips and J. White. A precorrected-FFT method for electrostatic analysis of complicated 3-D structures. IEEE Trans. on Computer-Aided Design, 16(10):1059--1072, Oct. 1997.
[3]
W. Shi, J. Liu, N. Kakani, and T. Yu. A fast hierarchical algorithm for 3-D capacitance extraction. In IEEE/ACM DAC, pages 212--217, June 1998.
[4]
F. Gong, H. Yu, and L. He. Picap: A parallel and incremental capacitance extraction considering stochastic process variation. In IEEE/ACM DAC, pages 764--769, Jul. 2009.
[5]
R. Iverson and Y. Le Coz. A Stochastic Algorithm for High Speed capacitance Extraction in Integrated Circuits. Solid-State Electronics, 35(7):1005--1012, 1992.
[6]
T. El-Moselhy, I. Elfadel, and L. Daniel. A hierarchical floating random walk algorithm for fabric-aware 3D capacitance extraction. In IEEE/ACM ICCAD, pages 752--758, 2009.
[7]
NVIDIA Corporation. Fermi compute architecture white paper. {Online}. Available: http://www.nvidia.com/object/fermi_architecture.html, 2010.
[8]
N. Gumerov and R. Duraiswami. Fast multipole methods on graphics processors. J. Comput. Phys., 227(18):8290--8313, 2008.
[9]
T. Hamada, T. Narumi, R. Yokota, K. Yasuoka, K. Nitadori, and M. Taiji. 42 TFlops hierarchical N-body simulations on GPUs with applications in both astrophysics and turbulence. In SC '09, pages 1--12, 2009.
[10]
K. Nabors, S. Kim, and J. White. Fast capacitance extraction of general three-dimensional structures. IEEE Trans. on Microwave Theory and Techniques, 40(7):1496--1506, Jul. 1992.
[11]
L. Greengard and V. Rokhlin. A fast algorithm for particle simulations. J. Comput. Phys., 73(2):325--348, 1987.
[12]
A. Appel. An efficient program for many-body simulation. SIAM Journal on Scientific and Statistical Computing, 6(1):85--103, 1985.
[13]
NVIDIA Corporation. NVIDIA CUDA C programming guide. {Online}. Available: http://developer.nvidia.com/object/gpucomputing.html, 2010.

Cited By

View all
  • (2022)GPU-Friendly FRW Algorithms for Electrostatic Computation ProblemsMonte Carlo Methods for Partial Differential Equations With Applications to Electronic Design Automation10.1007/978-981-19-3250-2_10(195-216)Online publication date: 3-Sep-2022
  • (2015)Accelerated molecular mechanical and solvation energetics on multicore CPUs and manycore GPUsProceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics10.1145/2808719.2808742(222-231)Online publication date: 9-Sep-2015
  • (2014)Statistical Capacitance Extraction Based on Continuous-Surface Geometric ModelAdvanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_9(153-178)Online publication date: 12-Mar-2014
  • Show More Cited By

Index Terms

  1. Fast multipole method on GPU: tackling 3-D capacitance extraction on massively parallel SIMD platforms

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    DAC '11: Proceedings of the 48th Design Automation Conference
    June 2011
    1055 pages
    ISBN:9781450306362
    DOI:10.1145/2024724
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 05 June 2011

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. GPU
    2. capacitance extraction
    3. parallel fast multipole method

    Qualifiers

    • Research-article

    Conference

    DAC '11
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

    Upcoming Conference

    DAC '25
    62nd ACM/IEEE Design Automation Conference
    June 22 - 26, 2025
    San Francisco , CA , USA

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)6
    • Downloads (Last 6 weeks)1
    Reflects downloads up to 13 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2022)GPU-Friendly FRW Algorithms for Electrostatic Computation ProblemsMonte Carlo Methods for Partial Differential Equations With Applications to Electronic Design Automation10.1007/978-981-19-3250-2_10(195-216)Online publication date: 3-Sep-2022
    • (2015)Accelerated molecular mechanical and solvation energetics on multicore CPUs and manycore GPUsProceedings of the 6th ACM Conference on Bioinformatics, Computational Biology and Health Informatics10.1145/2808719.2808742(222-231)Online publication date: 9-Sep-2015
    • (2014)Statistical Capacitance Extraction Based on Continuous-Surface Geometric ModelAdvanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_9(153-178)Online publication date: 12-Mar-2014
    • (2014)Process Variation-Aware Capacitance ExtractionAdvanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_8(121-152)Online publication date: 12-Mar-2014
    • (2014)Extracting Frequency-Dependent Substrate ParasiticsAdvanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_7(107-119)Online publication date: 12-Mar-2014
    • (2014)Substrate Resistance Extraction with Boundary Element MethodAdvanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_6(91-106)Online publication date: 12-Mar-2014
    • (2014)Resistance Extraction of Complex 3-D InterconnectsAdvanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_5(71-89)Online publication date: 12-Mar-2014
    • (2014)Fast Boundary Element Methods for Capacitance Extraction (II)Advanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_4(39-70)Online publication date: 12-Mar-2014
    • (2014)Fast Boundary Element Methods for Capacitance Extraction (I)Advanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_3(19-37)Online publication date: 12-Mar-2014
    • (2014)Basic Field-Solver Techniques for RC ExtractionAdvanced Field-Solver Techniques for RC Extraction of Integrated Circuits10.1007/978-3-642-54298-5_2(7-18)Online publication date: 12-Mar-2014
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media