Efficient algorithms for extracting the K most critical paths in timing analysis

Steve H.C. Yen, David H.C. Du, S. Ghanta

Research output: Contribution to journalConference articlepeer-review

45 Scopus citations

Abstract

Several algorithms which can generate the K most critical paths in a nonincreasing order of their delays were designed and developed. The effectiveness of these algorithms was shown experimentally. For instance, for a design of 2000 components, 6000 connections, and 2.7 million paths, one of the algorithms takes 3.6, 5.2, and 25.9 s on a Sun 50/3 workstation to generate 1, 10, and 100 most critical paths, respectively. When only the most critical path is reported, the proposed algorithms require roughly the same amount of execution time as block-oriented algorithms.

Original languageEnglish (US)
Pages (from-to)649-654
Number of pages6
JournalProceedings - Design Automation Conference
DOIs
StatePublished - Jan 1 1989
Event26th ACM/IEEE Design Automation Conference - Las Vegas, NV, USA
Duration: Jun 25 1989Jun 29 1989

Fingerprint

Dive into the research topics of 'Efficient algorithms for extracting the K most critical paths in timing analysis'. Together they form a unique fingerprint.

Cite this