D. H. Du
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.
- BELL88.Design files provided by ATg~T Bell Labortory.Google Scholar
- 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.Google Scholar
- 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.)Google Scholar
- 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.Google ScholarDigital Library
- HITC82b.Hitchcock, R. B. "Timing Verification and the Timing Analysis Program," Proceedings of the 19th Design Automation Conference, 594-604, 1982. Google ScholarDigital Library
- McWI80.McWilliams, T. M. "Verification of Timing Constraints on Large Digital Systems," Proceedings of 17th Design Automation Conference, 139-147, 1980. Google ScholarDigital Library
- 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.Google Scholar
- REDD86.Reddi, R. and Ghen, C. "Hierarchical Timing Verification System," Computer Aided Design, Vol. 18, 9, November 1986, 467-471. Google ScholarDigital Library
- ROTH66.J.P. Roth, "Diagnosis of automata failures: A calculus and a new method," IBM J. Res. Develop.,, OCT. 1966, pp. 278-281.Google Scholar
- SASA81.Sasaki, T., Yamada, A., Aoyama, T., Hasegawa, K., Kato, S. ~nd Sato, S. "HierarchicM Design Verification for Large Digital Systems," Proceeding~ of 18th Design Automation Conference, 105- 112, 1981. Google ScholarDigital Library
- SZYM86.Szymanski, T. G. "LEADOUT: A Static Timing Analyzer for MOS Circuits," Proceeding8 of ICCAD-88, 130-133, 1986.Google Scholar
- 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.Google Scholar
- YEN88a.Yen, H.C., Ghanta, S., and Du, H.C., "A Path Selection Algorithm for Timing Analysis" Proceeding of the 25th Design .Automation Conference, 5une, 1988. Google ScholarDigital Library
- 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.Google Scholar
Index Terms
- On the general false path problem in timing analysis
Recommendations
On timing-independent false path identification
ICCAD '10: Proceedings of the International Conference on Computer-Aided DesignThis paper is concerned with finding timing-independent false paths that cannot be sensitized under any signal arrival time condition in integrated circuits. Existing techniques regard a path as a true path as long as a vector pair can be found to ...
Shortest path problem with uncertain arc lengths
Uncertainty theory provides a new tool to deal with the shortest path problem with nondeterministic arc lengths. With help from the operational law of uncertainty theory, this paper gives the uncertainty distribution of the shortest path length. Also, ...
Comments