Hierarchical functional timing analysis

ABSTRACT

We propose a hierarchical timing analysis technique for combinational circuits under the tightest known sensitization criterion, the XBDO delay model. Given a hierarchical combinational circuit, a generalized delay model of each left module is characterized first. Since this timing characterization step takes into account false paths in each module, the delay model is more accurate than the one obtained by topological analysis. Then topological delay analysis is performed on the circuit composed of generalized gates replacing the leaf modules, where the “gate” delay model is the derived one. As far as the authors know, this is the first result that shows that hierarchical analysis is possible under state-of-the-art tight sensitization criteria. We demonstrate by experimental results that loss of accuracy in using the hierarchical approach is very minimal in practice. The theory developed in this paper also provides a foundation for incremental timing analysis under accurate sensitization criteria.

REFERENCES

• 1: Krishna P. Belkhale , Alexander J. Suess, Timing analysis with known false sub graphs, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.736-740, November 05-09, 1995, San Jose, California, United States
• 2: H.-C. Chen and D. H.-C. Du. Path sensitization in critical path problem. IEEE Transactions on Computer-Aided Design, 12(2): 196-207, February 1993.
• 3: S. Devadas, K. Keutzer, and S. Malik. Computation of floating mode delay in combinational circuits: Theory and algorithms. 1EEE Transactions on Computer-Aided Design, 12( 12): 1913- 1923, December 1993.
• 4: Yuji Kukimoto , Robert K. Brayton, Exact required time analysis via false path detection, Proceedings of the 34th annual conference on Design automation, p.220-225, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266070]
• 5: 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
• 6: P. C. McGeer, A. Saldanha, R. K.Brayton, and A. Sangiovanni- Vincentelli. Delay models and exact timing analysis. In T. Sasao, editor, Logic Synthesis and Optimization, pages 167- 189. Kluwer Academic Publishers, 1993.
• 7: A. Saldanha. Performance and testability interactions in logic synthesis. Technical ReportUCB/ERLM91/100, University of California, Berkeley, October 199 1.
• 8: S. V. Venkatesh, R. Palermo, M. Mortazavi, and K. A. Sakallah. Timing abstraction of intellectual property blocks. InProceedings of Custom Integrated Circuit Conference,pages 99-102, May 1997.
• 9: 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.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability

  C. Computer Systems Organization

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

  J. Computer Applications

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