Timing analysis based on primitive path delay fault identification

ABSTRACT

We present a novel timing analysis mechanism which is based on identifying primitive path delay faults (primitive PDFs) in a circuit. We show that this approach gives the exact maximum delay of the circuit under the floating mode of operation assumption. Our timing analysis approach provides a framework where component delay correlations and signal correlations arising from fabrication process, signal propagation, and signal interaction effects can be handled very accurately. Under these effects, timing analysis using previously reported floating mode timing analyzers, e.g., viability, TrueD-F etc., is very pessimistic. Our timing analysis approach based on primitive PDF identification is also more efficient than conventional floating mode path sensitization analysis mechanisms in situations where critical paths need to be re-identified due to component delay speedup (e.g., post-layout delay optimization). We demonstrate the applicability of our timing analysis approach for a variety of benchmark circuits, and demonstrate the pessimism of conventional floating mode timing analysis approaches in accounting for signal propagation effects.

REFERENCES

• 1: T. Kirkpatrick and N. Clark, "PERT as an aid to logic design," IBM Tech. Rep., 1966.
• 2: J. Benkoski, E. Vanden Meersch, L. J. M. Claesen, H. De Man, "Timing verification using statically sensitizable paths," IEEE Trans. Computer-Aided Design, vol. 9, Oct. 1990, pp. 1073-1084.
• 3: P. C. McGeer , R. K. Brayton, Efficient algorithms for computing the longest viable path in a combinational network, Proceedings of the 26th ACM/IEEE conference on Design automation, p.561-567, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74476]
• 4: S. Devadas, K. Keutzer, and S. Malik, "Computation of floating mode delay in combinational logic circuits: Theory and algorithms," IEEE Trans. Computer-Aided Design, vol. 12, Dec. 1993, pp. 1913-1922.
• 5: S. Devadas, K. Keutzer, S. Malik, and A. Wang, "Computation of floating mode delay in combinational logic circuits: Practice and implementation," IEEE Trans. Computer-Aided Design, vol. 12, Dec. 1993, pp. 1923- 1936.
• 6: H. Chen and D. Du, "Path sensitization in critical path problem," Proc. TAU'90. ACM-SIGDA, 1990.
• 7: S. Devadas, K. Keutzer, S. Malik, and A. Wang, "Certified timing verification and the transition delay of a logic circuit," IEEE Trans. VLSI Systems, vol. 2, Sept. 1994, pp. 333-342.
• 8: G.L. Smith, "Model for delay faults based upon paths," Proc. Int'l Test Conference, Nov. 1985, pp. 324-349.
• 9: C. J. Lin and S. M. Reddy, "On delay fault testing in logic circuits," IEEE Trans. Computer-Aided Design, vol. 6-5, Sept. 1987, pp. 694-703.
• 10: E.S. Park and M. R. Mercer, "Robust and nonrobust tests for path delay faults in a combinational circuit," Proc. Int' l Test Conf., 1987, pp. 1027-1034.
• 11: S.M. Reddy, "Delay faults: Modeling, fault simulation, and test generation," Int'l Test Conf., 1995, Tutorial 8.
• 12: Wuudiann Ke , Premachandran R. Menon, Synthesis of Delay-Verifiable Combinational Circuits, IEEE Transactions on Computers, v.44 n.2, p.213-222, February 1995 [doi>10.1109/12.364533]
• 13: Mukund Sivaraman , Andrzej J. Strojwas, Primitive Path Delay Fault Identification, Proceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications, p.95, January 04-07, 1997
• 14: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Design, Measurement, Performance, Theory

Keywords:
timing analysis, false path, timing verification, path delay fault testing, primitive path delay faults, correlated delay, floating mode