Provably correct high-level timing analysis without path sensitization

ABSTRACT

This paper addresses the problem of true delay estimation during high level design. The existing delay estimation techniques either estimate the topological delay of the circuit which may be pessimistic, or use gate-level timing analysis for calculating the true delay, which may be prohibitively expensive.We show that the paths in the implementation of a behavioral specification can be partitioned into two sets, SP and UP. While the paths in SP can affect the delay of the circuit, the paths in UP cannot. Consequently, the true delay of the resulting circuit can be computed by just measuring the topological delay of the paths in SP, eliminating the need for the computationally intensive process of path sensitization. Experimental results show that high-level true delay estimation can be done very fast, even when gate-level true delay estimation becomes computationally infeasible. The high-level delay estimates are verified by comparing with delay estimates obtained by gate-level timing analysis on the actual implementation.

REFERENCES

• 1: H-C. Chen and D. H. C. Du. Path Sensitization in Critical Path Problem. In ICCAD, 1991.
• 2: S. Devadas, K. Keutzer, and S. Malik. Delay Computation in Combinational Logic Circuits: Theory and Algorithms. In lCCAD, 1991.
• 3: EC. McGeer, A. Saldanha, ER. Stephan, and R.K. Brayton. Timing Analysis and Delay-Fault Test Generation using Path-Recursive Functions. In ICCAD, Nov 1991.
• 4: E Ashar, S. Malik, and S. Rothweiler. Functional Timing Analysis using ATPG. In EDAC, 1993.
• 5: 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]
• 6: C. Ramachandran , F. J. Kurdahi , D. D. Gajski , A. C.-H. Wu , V. Chaiyakul, Accurate layout area and delay modeling for system level design, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.355-361, November 1992, Santa Clara, California, United States
• 7: Andreas Kuehlmann , Reinaldo A. Bergamaschi, Timing analysis in high-level synthesis, Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, p.349-354, November 1992, Santa Clara, California, United States
• 8: EK. Jha and N.D. Dutt. Rapid Estimation for Parameterized Components in High-Level Synthesis. IEEE Transactions on VLSI Systems, 1 (3):296- 303, Sept 1993.
• 9: C. Safinia, R. Leveugle, and G. Saucier. Taking Advantage of High Level Functional Information to Refine Timing Analysis and Timing Modeling. In ED&T, 1994.
• 10: Champaka Ramachandran , Fadi J. Kurdahi, Combined topological and functionality based delay estimation using a layout-driven approach for high level applications, Proceedings of the conference on European design automation, p.72-78, November 1992, Congress Centrum Hamburg, Hamburg, Germany
• 11: R.A. Bergamaschi. The Effects of False Paths in High-Level Synthesis. In ICCAD, 1991.
• 12: B. Gregory , D. MacMillen , D. Fogg, ISIS: a system for performance driven resource sharing, Proceedings of the 29th ACM/IEEE conference on Design automation, p.285-290, June 08-12, 1992, Anaheim, California, United States
• 13: Subhrajit Bhattacharya , Sujit Dey , Franc Brglez, Clock period optimization during resource sharing and assignment, Proceedings of the 31st annual conference on Design automation, p.195-200, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196346]
• 14: S. Bhattacharya, S. Dey, and F. Brglez. Provably Correct High-Level Timing Analysis without Path Sensitization. Technical report, C&C Research Labs, NEC USA, June 1994.
• 15: Kenneth Hintz , Daniel Tabak, Microcontrollers: architecture, implementation, and programming, McGraw-Hill, Inc., New York, NY, 1992
• 16: K. Kozminski (ed.). OASIS Users Guide. MCNC, Research Triangle Park, N.C. 27709, 1992.
• 17: Ellen Sentovich , Kanwar Jit Singh , Cho W. Moon , Hamid Savoj , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Sequential Circuit Design Using Synthesis and Optimization, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.328-333, October 11-14, 1992

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION

General Terms:
Algorithms, Measurement, Theory