A GPU-Accelerated Framework for Path-Based Timing Analysis

Guannan Guo, Tsung Wei Huang, Yibo Lin, Zizheng Guo, Sushma Yellapragada, Martin D.F. Wong

Research output: Contribution to journalArticlepeer-review


As a key routine in static timing analysis (STA), path-based analysis (PBA) plays a very important role in refining the critical path report by reducing excessive slack pessimism. PBA is also well known for its long execution time, which makes it a hot topic for parallel computing in the STA community. However, nearly all of the parallel PBA algorithms are restricted to CPU architectures, which greatly limits their scalability. To achieve a new performance milestone on PBA, we must leverage the high throughput computing in the graphics processing unit (GPU). Therefore, in this work, we propose a new GPU-accelerated PBA framework which contains compact data structures and highly efficient kernels. By integrating with GPU-accelerated preprocessing steps, our framework can also effectively handle extensive critical path constraints. Besides, we highlight many optimization techniques that can overcome the execution bottleneck and further boost the performance. In experiments, we demonstrate 543× speed-up compared to the state-of-the-art PBA algorithm on the design with 1.6 million gates, which outperforms 25× - 45× over the state-of-the-art parallel PBA algorithm on 40 CPU cores. A fully optimized framework can achieve 3× - 5× speed-up on top of that.

Original languageEnglish (US)
Pages (from-to)4219-4232
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number11
StatePublished - Nov 1 2023
Externally publishedYes


  • Graphics processing unit (GPU) acceleration
  • static timing analysis (STA)

ASJC Scopus subject areas

  • Software
  • Electrical and Electronic Engineering
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'A GPU-Accelerated Framework for Path-Based Timing Analysis'. Together they form a unique fingerprint.

Cite this