TY - JOUR
T1 - Efficient algorithms for extracting the K most critical paths in timing analysis
AU - Yen, Steve H.C.
AU - Du, David H.C.
AU - Ghanta, S.
PY - 1989/1/1
Y1 - 1989/1/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0024889867&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0024889867&partnerID=8YFLogxK
U2 - 10.1145/74382.74497
DO - 10.1145/74382.74497
M3 - Conference article
AN - SCOPUS:0024889867
SN - 0738-100X
SP - 649
EP - 654
JO - Proceedings - Design Automation Conference
JF - Proceedings - Design Automation Conference
T2 - 26th ACM/IEEE Design Automation Conference
Y2 - 25 June 1989 through 29 June 1989
ER -