UI-Timer 1.0: An Ultrafast Path-Based Timing Analysis Algorithm for CPPR

Tsung-Wei Huang, Martin D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

34 Citations (Scopus)

Abstract

The recent TAU computer-aided design (CAD) contest has aimed to seek novel ideas for accurate and fast common path pessimism removal (CPPR). Unnecessary pessimism forces the static timing analysis tool to report worse violation than the true timing properties owned by physical circuits, thereby misleading signoff timing into a lower clock frequency at which circuits can operate than actual silicon implementations. Therefore, we introduce in this paper UI-Timer 1.0, a powerful CPPR algorithm which achieves high accuracy and ultrafast runtime. Unlike existing approaches which are dominated by explicit path search, UI-Timer 1.0 proves that by implicit path representation the amount of search effort can be significantly reduced. Our timer is superior in both space and time saving, from which memory storage and important timing quantities are available in constant space and constant time per path during the search. Experimental results on industrial benchmarks released from TAU 2014 CAD contest have justified that UI-Timer 1.0 achieved the best result in terms of accuracy and runtime over existing CPPR algorithms.
Original languageEnglish
Article number7400988
Pages (from-to)1862-1875
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume35
Issue number11
DOIs
Publication statusPublished - Nov 2016

User-Defined Keywords

  • Common path pessimism removal (CPPR)
  • static timing analysis (STA)

Cite this