GPU-accelerated Path-based Timing Analysis

Guannan Guo, Tsung-Wei Huang, Yibo Lin, Martin Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

21 Citations (Scopus)

Abstract

Path-based Analysis (PBA) is an important step in the design closure flow for reducing slack pessimism. However, PBA is extremely time-consuming. Recent years have seen many parallel PBA algorithms, but most of them are architecturally constrained by the CPU parallelism and do not scale beyond a few threads. To overcome this challenge, we propose in this paper a new fast and accurate PBA algorithm by harnessing the power of graphics processing unit (GPU). We introduce GPU-efficient data structures, high-performance kernels, and efficient CPU-GPU task decomposition strateiges, to accelerate PBA to a new performance milestone. Experimental results show that our method can speed up the state-of-the-art algorithm by 543× on a design of 1.6 million gates with exact accuracy. At the extreme, our method of 1 CPU and 1 GPU outperforms the state-of-the-art algorithm of 40 CPUs by 25-45×.

Original languageEnglish
Title of host publication58th ACM/IEEE Design Automation Conference - Proceedings 2021
PublisherIEEE
Pages721-726
Number of pages6
ISBN (Electronic)9781665432740
ISBN (Print)9781665432757
DOIs
Publication statusPublished - 13 Dec 2021
Event58th ACM/IEEE Design Automation Conference, DAC 2021 - Online and , San Francisco, United States
Duration: 5 Dec 202131 Dec 2021
https://www.dac.com/About/Conference-Archive/58th-DAC-2021 (Conference website)
https://www.dac.com/Portals/0/Documents/Conference/DAC58%20Onsite%20Guide_v3.pdf?ver=PzAzrEcD9k-zkYioncfDUw%3d%3d (Conference programme )
https://ieeexplore.ieee.org/xpl/conhome/9585997/proceeding (Conference proceedings)

Publication series

NameACM/IEEE Design Automation Conference - Proceedings
Volume2021-December
ISSN (Print)0738-100X

Conference

Conference58th ACM/IEEE Design Automation Conference, DAC 2021
Country/TerritoryUnited States
CitySan Francisco
Period5/12/2131/12/21
Internet address

Scopus Subject Areas

  • Computer Science Applications
  • Control and Systems Engineering
  • Electrical and Electronic Engineering
  • Modelling and Simulation

Fingerprint

Dive into the research topics of 'GPU-accelerated Path-based Timing Analysis'. Together they form a unique fingerprint.

Cite this