Event propagation conditions in circuit delay computation

ABSTRACT

Accurate and efficient computation of delays is a central problem in computer-aided design of complex VLSI circuits. Delays are determined by events (signal transitions) propagated from the inputs of a circuit to its outputs, so precise characterization of event propagation is required for accurate delay computation. Although many different propagation conditions (PCs) have been proposed for delay computation, their properties and relationships have been far from clear. We present a systematic analysis of delay computation based on a series of waveform models that capture signal behavior rigorously at different levels of details. The most general model, called the exact of W0 model, specifies each event occurring in a circuit signal. A novel method is presented that generates approximate waveforms by progressively eliminating signal values from the exact model. For each waveform model, we drive the PCs that correctly capture the requirements under which an event propagates along a path. The waveform models and their PCs are shown to form a well-defined hierarchy, which provides a means to trade accuracy for computational effort. The relationships among the derived PCs and existing ones are analyzed in depth. It is proven that though many PCs, such as the popular floating mode condition, produce a correct upper bound on the circuit delay, they can fail to recognize event propagation in some instances. This analysis further enables us to derive new and useful PCs. We describe such a PC, called safe static. Experimental results demonstrate that safe static provides an excellent accuracy/efficiency tradeoff.

REFERENCES

• 1: BRAND, D. AND IYENGAR, V.S. 1986. Timing Analysis Using Functional Relationships. In Computer-Aided Design.
• 2: BROWN, F. 1090. Boolean reasoning. Kluwer Academic Publishers, Hingham, MA.
• 3: Jindrich Zejda , Eduard Cerny, Gate-level timing verification using waveform narrowing, Proceedings of the conference on European design automation, p.374-379, September 19-23, 1994, Grenoble, France
• 4: Hoon Chang , Jacob A. Abraham, VIPER: an efficient vigorously sensitizable path extractor, Proceedings of the 30th international conference on Design automation, p.112-117, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.158845]
• 5: CHEN, H.-C AND DU, D.-C. 1993. Path Sensitization in Critical Path Problem. IEEE Trans. CAD 12 (Feb.), 196-207.
• 6: S. Devadas , K. Keutzer , S. Malik , A. Wang, Certified timing verification and the transition delay of a logic circuit, Proceedings of the 29th ACM/IEEE conference on Design automation, p.549-555, June 08-12, 1992, Anaheim, California, United States
• 7: DEVADAS, S. 1993. Computation of Floating Mode Delay in Combinational Circuits: Theory and Algorithms. IEEE Trans. CAD 12 (Dec.), 1913-1923.
• 8: DEVADAS, S. 1994. Event Suppression: Improving the Efficiency of Timing Simulation for Synchronous Digital Circuits. IEEE Trans. CAD 13 (June), 814-822.
• 9: D. H. Du , S. H. Yen , S. Ghanta, On the general false path problem in timing analysis, Proceedings of the 26th ACM/IEEE conference on Design automation, p.555-560, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74475]
• 10: HRAPCENKO,, V. 1978. Depth and Delay in a Network. Soviet Math. Dokl. 19, 1006-1009.
• 11: Yun-Cheng Ju , Resve A. Saleh, Incremental techniques for the identification of statically sensitizable critical paths, Proceedings of the 28th conference on ACM/IEEE design automation, p.541-546, June 17-22, 1991, San Francisco, California, United States [doi>10.1145/127601.127729]
• 12: William K. C. Lam , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Circuit delay models and their exact computation using Timed Boolean Functions, Proceedings of the 30th international conference on Design automation, p.128-134, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164625]
• 13: 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]
• 14: Patrick C. McGeer , Robert K. Brayton, Integrating Functional and Temporal Domains in Logic Design: The False Path Problem and Its Implications, Kluwer Academic Publishers, Norwell, MA, 1991
• 15: S. Perremans , L. Claesen , H. De Man, Static timing analysis of dynamically sensitizable paths, Proceedings of the 26th ACM/IEEE conference on Design automation, p.568-573, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74477]
• 16: SAKALLAH, K. 1995. Dynamic Modeling of Logic Gate Circuits. University of Michigan, Ann Arbor, MI.
• 17: Emily J. Shriver , Karem A. Sakallah, Ravel: assigned-delay compiled-code logic simulation, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.364-368, November 1992, Santa Clara, California, United States
• 18: SILVA, J. AND SAKALLAH, K. 1993. An Analysis of Path Sensitization Criteria. In Computer Design, 68-72.
• 19: SILVA, J. AND SAKALLAH, K. 1994. Efficient and Robust Test Generation-Based Timing Analysis. In Circuits and Systems, 303-306.
• 20: Shanf-Zhi Sun , David Hung-Chang Du , Hsi-Chuan Chen, Efficient Timing Analysis for CMOS Circuits Considering Data Dependent Delays, Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, p.156-159, October 10-12, 1994
• 21: Hakan Yalcin , John P. Hayes, Hierarchical timing analysis using conditional delays, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.371-377, November 05-09, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Verification

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Verification

General Terms:
Performance, Theory, Verification

Keywords:
delay computation, event propagation, false path, path sensitization, propagation condition, timing analysis, waveform modeling