On the general false path problem in timing analysis

ABSTRACT

The false path problem is often referred to as the problem of detecting the longest sensitizable path (A path which is not a false path is a sensitizable path). The term “false path” is not clearly defined. In this paper, we first give a clear and precise definition of a false path. Then the general false path problem is formulated. The general false path problem is to detect whether a given path (not necessarily the longest one) is a false path. We present an efficient algorithm for solving the general false path problem. We also propose another algorithm which generates all the possible sensitizable paths with the delays greater than a given threshold T. The efficiency and effectiveness of the proposed algorithm are demonstrated by the experimental results. Index Terms: Timing Verification, Logic Simulation, VLSI circuit, Timing Analysis, False path, Graph Theory.

REFERENCES

• BELL88: Design files provided by ATg~T Bell Labortory.
• BENK87: Benkowski, J., Vanden Meersch, E., Claesen, L., and De Man, H. "Efficient Algorithms for Solving the False Path Problem in Timing Verification," Proceeding8 of ICCAD-SZ 44-47, 1987.
• BRAN86: Brand, D. and Iyengar, V. S. "Timing Analysis Using Functional Relal~ionships," Proceeding8 of CCAD-86, 126-129, 1986; (See also "Timing Analysis using Functional Analysis" IBM Research Report, RC 11768(#52821) March 12th ~986.)
• 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
• McWI80: Thomas M. McWilliams, Verification of timing constraints on large digital systems, Proceedings of the 17th conference on Design automation, p.139-147, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804523]
• OUST85: Ousterhout, J. K. "A Switch-Level Timing Verifier for Digital MOS VLSI," 1EF~E Transaction~ 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]
• ROTH66: J.P. Roth, "Diagnosis of automata failures: A calculus and a new method," IBM J. Res. Develop.,, OCT. 1966, pp. 278-281.
• 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
• SZYM86: Szymanski, T. G. "LEADOUT: A Static Timing Analyzer for MOS Circuits," Proceeding8 of ICCAD-88, 130-133, 1986.
• YEN87: Yen, H.C., Ghaaata, S., and Du, H C., "Timing Analysis Algorithms for Large Designs," Technical Report No. 87-57, Department of Computer Science, University of Minnesota.
• YEN88a: 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
• YEN88b: Yen, H.C. and Du, H.C., "On the General False Path Problem in Timing Analysis," Technical Report No. 88-87, Department of Computer Science, University of Minnesota.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

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: Verification

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Performance, Theory