Critical path analysis using a dynamically bounded delay model

ABSTRACT

This paper focuses on static timing analysis in the presence of capacitive coupling. We propose a novel gate delay model, the dynamically bounded delay model. In contrast to the min-max or bounded delay model which assumes a fixed delay range, [dmin, dmax], for each circuit component, our new model allows for the specification of delay variations and the conditions upon which the variations will hold. Novel static timing analysis algorithms can thus dynamically bound the delays. To demonstrate the effectiveness of this model and approach, we use our model to perform critical path analysis in the presence of capacitive coupling. Our experiments show that our approach avoids pessimism when compared to PERT analysis assuming worst case capacitive coupling.

REFERENCES

• 1: Pu Arunachalam. "CMOS Gate Delay Models for Coupled RC(L) Interconnect Loads". Master's thesis, Carnegie Mellon University, May 1998.
• 2: D. Brand and V. Iyengar. "Timing Analysis Using Fucntional Relationships". In Proc. of the IEEE International Conference on Computer-Aided Design (IC- CAD), pages 126-9, 1986.
• 3: Florentin Dartu , Noel Menezes , Jessica Qian , Lawrence T. Pillage, A gate-delay model for high-speed CMOS circuits, Proceedings of the 31st annual conference on Design automation, p.576-580, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196562]
• 4: Florentin Dartu , Lawrence T. Pileggi, Calculating worst-case gate delays due to dominant capacitance coupling, Proceedings of the 34th annual conference on Design automation, p.46-51, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266033]
• 5: S. Devadas, K. Keutzer, and S. Malik. "Computation of Floating Mode Delay in Combinational Circuits: Theory and Algorithms". IEEE Transactions on Computer- Aided Design, 12(12):1913-23, December 1993.
• 6: 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]
• 7: P. Feldmann and R. Freund. "Efficient Linear Circuit Analysis by Pad~ Approximation via the Lanczos Process". IEEE Transactions on Computer-Aided Design, 9(4):352-366, April 1990.
• 8: Robert B. Hitchcock, Sr., Timing Verification and the Timing Analysis program, Proceedings of the 19th conference on Design automation, p.594-604, January 1982
• 9: S-T. Huang, T-M. Parng, and J-M. Shyu. "A New Approach to Solving False Path Problem in Timing Analysis". In Proc. of the IEEE International Conference on Computer-Aided Design (ICCAD), pages 216-219, 1991.
• 10: T. Kirkpatrick and N. Clark. "PERT as an Aid to Logic Design". "IBM Journal of Research and Developement", 10(2):135-141, March 1966.
• 11: 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
• 12: P. McGeer, A. Saldanha, R. Brayton, and A. Sangiovanni-Vincentelli. "Delay Models and Exact Timing Analysis". In T. Sasao, editor, "Logic Synthesis and Optimization", pages 167-89, 1993.
• 13: Altan Odabasioglu , Mustafa Celik , Lawrence T. Pileggi, PRIMA: passive reduced-order interconnect macromodeling algorithm, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.58-65, November 09-13, 1997, San Jose, California, United States
• 14: L. Pillage and Pu Rohrer. "Asympototic Waveform Evaluation for Timing Analysis". IEEE Transactions on Computer-Aided Design, 9(4):352-366, April 1990.
• 15: J. Qian, S. Pullela, and L. Pillage. "Modeling the Effective Capacitance for the RC Interconnect of CMOS Gates". IEEE Transactions on Computer-Aided Design, 13(12):1526-1535, December 1994.
• 16: Karem A. Sakallah , Trevor N. Mudge , Oyekunle A. Olukotun, Analysis and design of latch-controlled synchronous digital circuits, Proceedings of the 27th ACM/IEEE conference on Design automation, p.111-117, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123237]
• 17: C-J Seger. "A Bounded Delay Race Model". In Proc. of the IEEE International Conference on Computer-Aided Design (ICCAD), pages 130-3, 1989.
• 18: K. L. Shepard , V. Narayanan , P. C. Elmendorf , Gutuan Zheng, Global harmony: coupled noise analysis for full-chip RC interconnect networks, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.139-146, November 09-13, 1997, San Jose, California, United States
• 19: L. Miguel Silveira , Mattan Kamon , Jacob White, Efficient reduced-order modeling of frequency-dependent coupling inductances associated with 3-D interconnect structures, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.376-380, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217558]
• 20: Thomas G. Szymanski , Narendra Shenoy, Verifying clock schedules, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.124-131, November 1992, Santa Clara, California, United States
• 21: S. Tasiran, S. Khatri, S. Yovine, R. Brayton, and A. Sangiovanni-Vincentelli. "A Timed Automaton- Based Method for Accurate Computation of Circuit Delay in the Presence of Cross Talk". In Formal Methods in Computer-Aided Design, 1998.
• 22: Neil H. E. Weste , Kamran Eshraghian, Principles of CMOS VLSI design: a systems perspective, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 23: H. Williams. "Model Building in Mathematical Programming". John Wiley & Sons, 1978.

INDEX TERMS

Primary Classification:
  J. Computer Applications

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.1 Project and People Management
          Subjects: Management techniques (e.g., PERT/CPM)

General Terms:
Design, Experimentation, Management, Measurement, Performance, Theory