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

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.