An efficient critical path generation algorithm considering extensive path constraints

Guannan Guo*, Tsung-Wei Huang, Chun-Xun Lin, Martin Wong

*Corresponding author for this work

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

9 Citations (Scopus)

Abstract

In this paper, we introduce a fast and efficient critical path generation algorithm considering extensive path constraints on a Static Timing Analysis (STA) graph. Critical path generation is a key routine in the inner loop of path-based analysis and timing-driven synthesis flows. Our algorithm can report arbitrary numbers of critical paths on a logic cone constrained by a sequence of from/through/to pins under different min/max modes and rise/fall transitions. Our algorithm is general, efficient, and provably good. Experimental results have showed that our algorithm produces reports that matches a golden reference generated by an industrial signoff timer. Our results also correlate to a commercial timer yet achieving more than an order of magnitude speed-up.

Original languageEnglish
Title of host publication57th ACM/IEEE Design Automation Conference - Proceedings 2020
PublisherIEEE
Number of pages6
ISBN (Electronic)9781450367257, 9781728110851
ISBN (Print)9781728158020
DOIs
Publication statusPublished - 20 Jul 2020
Event57th ACM/IEEE Design Automation Conference, DAC 2020 - Virtual
Duration: 20 Jul 202024 Jul 2020
https://www.dac.com/About/Conference-Archive/57th-DAC-2020 (Conference website )
https://ieeexplore.ieee.org/xpl/conhome/9211868/proceeding (Conference proceedings )
https://dl.acm.org/doi/proceedings/10.5555/3437539 (Conference proceedings)

Publication series

NameACM/IEEE Design Automation Conference - Proceedings 2020
Volume2020-July
ISSN (Print)0738-100X

Conference

Conference57th ACM/IEEE Design Automation Conference, DAC 2020
CityVirtual
Period20/07/2024/07/20
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 'An efficient critical path generation algorithm considering extensive path constraints'. Together they form a unique fingerprint.

Cite this