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

ABSTRACT

Path extracting algorithms are a very important part of timing analysis approach. In this paper we designed and developed several algorithms which can generate the K most critical paths in a non-increasing order of their delays. The effectiveness of these algorithms is shown by some experimental results.

REFERENCES

• BENI82: Lionel C. Bening , Thomas A. Lane , Curtis R. Alexander , James E. Smith, Developments in logic network path delay analysis, Proceedings of the 19th conference on Design automation, p.605-615, January 1982
• BELL88: Design files provided by AT&T Bell Labortory.
• BRAN86: :Brand, D. and Iyengar, V. S. "Timing Analysis Using Functional Relationships," Proceedings of ICCAD-86, 126-129, 1986.
• CHAN85: Edward Chan, Development of a timing analysis program for multiple clocked network, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.816-819, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.318005]
• GLES85: M. Glesner , J. Schuck , R. B. Steck, SCAT—a new statistical timing verifier in a silicon compiler system, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.220-226, July 1986, Las Vegas, Nevada, United States
• HITC82a: Hitchcock, R. B., Smith, G. L., and Cheng, D. D. "Timing Analysis of Computer Hardware," IBM Journal of Research and Development, Vol. 26, 1, January 1982, 100-105.
• HITC82b: Robert B. Hitchcock, Sr., Timing Verification and the Timing Analysis program, Proceedings of the 19th conference on Design automation, p.594-604, January 1982
• HWAN86: Seung H. Hwang , Young H. Kim , A. R. Newton, An accuration delay modeling technique for switch-level timing verification, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.227-233, July 1986, Las Vegas, Nevada, United States
• KATO82: Kat~h, N., Ibaraki, T., and Mine, H. "An Efficient Algorithm for K Shortest Simple Paths," Networks, Vol. 12, 1982, 411-427.
• KIRK66: T.t. Kirkpatrick and N.R. Clark, "PERT as an aid to logic design," IBM J. Res. Develop., vol. 10, no. 2, pp. 135-141, March 1966.
• LARS87: Larson, B. "DAMSEL Users Manual," Honeywell SSED Design Technology, Honeywell Corporation, Minneapolis, Minnesot, a, April 1987.
• MURP85: Murphy, B. J., Kleckner, J. E., and Tam, K. K. "STA: A Mixed-LeveL Timing Analyzer," Proceedings of ICCAD-85, 176-178, 1985.
• MURA85: Michiaki Muraoka , Hirokazu Iida , Hideyuki Kikuchihara , Michio Murakami , Kazuyuki Hirakawa, ACTAS: an accurate timing analysis system for VLSI, Proceedings of the 22nd ACM/IEEE conference on Design automation, p.152-158, June 1985, Las Vegas, Nevada, United States [doi>10.1145/317825.317849]
• OUST85: Ousterhout, J. K., "A Switch-Level Timing Verifier for Digital MOS VLSI," IEEE Tran- 8action~ on Computer Aided Design, Vol. CAD-4, 3, July 1985, 336-349.
• REDD86: R Reddi , C Chen, Hierarchical timing verification system, Computer-Aided Design, v.18 n.9, p.467-471, Nov. 1986 [doi>10.1016/0010-4485(86)90002-3]
• SASA81: Tohru Sasaki , Akihiko Yamada , Toshinori Aoyama , Katsutoshi Hasegawa , Shunichi Kato , Shinichi Sato, Hierarchical design verification for large digital systems, Proceedings of the 18th conference on Design automation, p.105-112, June 29-July 01, 1981, Nashville, Tennessee, United States
• SYZM86: Syzmanski, T. G. "LEADOUT: A Static Timing Analyzer for MOS Circuits," Proceedings of ICCAD-86, 130-133, 1986.
• TOYO86: Reiji Toyoshima , Yoshimitsu Takiguchi , Kazumi Matsumoto , Hidetomo Hongou , Mashiro Hashimoto , Ryotaro Kamikawai , Katsuhiko Takizawa, An effective delay analysis system for a large scale computer design, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.398-403, July 1986, Las Vegas, Nevada, United States
• WALL86: David E. Wallace , Carlo H. Séquin, Plug-in timing models for an abstract timing verifier, Proceedings of the 23rd ACM/IEEE conference on Design automation, p.683-689, July 1986, Las Vegas, Nevada, United States
• YEN87: Yen, H.C., Ghunt% S., ~nd Du, H.C., "Timing Analysis Algorithms for Large Designs," Technical Report No. 87-57, Department of Computer Science, Universit~y of Minnesota, also submitted to IEEE Trans. on Computers.
• YEN88: H. C. Yen , S. Ghanta , H. C. Du, A path selection algorithm for timing analysis, Proceedings of the 25th ACM/IEEE conference on Design automation, p.720-723, June 12-15, 1988, Atlantic City, New Jersey, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Simulation; Verification

General Terms:
Algorithms, Design, Theory, Verification