[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/602902.602979acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
Article
Free access

Slope propagation in static timing analysis

Published: 05 November 2000 Publication History

Abstract

Static timing analysis has traditionally used the PERT method for identifying the critical path of a digital circuit. Due to the influence of the slope of a signal at a particular node on the subsequent path delay, an earlier signal with a signal slope greater than the slope of the later signal may result in a greater delay. Therefore, the traditional method for timing analysis may identify the incorrect critical path and report an optimistic delay for the circuit. We show that the circuit delay calculated using the traditional method is a discontinuous function with respect to transistor and gate sizes, posing a severe problem for circuit optimization methods. We propose a new timing analysis algorithm which resolves both these issues. The proposed algorithm selectively propagates multiple signals through each timing edge in cases where there exists ambiguity regarding which arriving signal represents the critical path. The algorithm for propagating the corresponding required times is also presented. We prove that the proposed algorithm identifies a circuit's true critical path, where the traditional timing analysis method may not. We also show that under this method circuit delay and node slack are continuous functions with respect to a circuit's transistor and gate sizes. In addition, we present a heuristic method which reduces the number of signals to be propagated at the expense of a slight loss in accuracy. Finally, we show how the proposed algorithm was efficiently implemented in an industrial static timing analysis and optimization tool, and present results for a number of industrial circuits. Our results show that the traditional timing analysis method underestimates the circuit delay by as much as 38%, while that the proposed method efficiently finds the correct circuit delay with only a slight increase in run time.

References

[1]
Ayman I. Kayssi, Karem A. Sakallah, Trevor N. Mudge The Impact of Signal Transition Time on Path Delay Computation, IEEE Transactions on circuits and systems-II: Analog and digital signal processing, Vol. 40, No. 5, May 1993
[2]
Chandu Visweswariah, Andrew R.Conn, Formulation of Static Circuit Optimization with Reduced Size, Degeneracy and Redundancy by Timing Graph Manipulation, Proc. IEEE/ACM ICCAD, 1999, pp.244-251.
[3]
Gill, P.E., Murray, W. and Wright, M.H., Practical Optimization, Academic Press, New York, 1983.
[4]
Hitchcock, R.B. Timing verification and the Timing Analysis program, Proc., IEEE/ACM DAC, 1982, pp.594-604
[5]
Jouppi, N.P. Timing analysis for nMOS VLSI, IEEE/ACM Design Automation Conf., 1983, pp. 411-418
[6]
J.P.Fishburn, A.Dunlop, "TILOS: A posynomial programming approach to transistor sizing", ICCAD, Nov 1985
[7]
S.Devadas, K.Keutzer, S.Malik, "Computation of Floating Mode Delay in Combinational Circuit: Theory and Algorithms", IEEE Trans. on Computer Aided Design, Dec 1993.
[8]
Y.Kukimoto, W.Gosti, A.Saldanha, R.Brayton, "Approximate Timing Analysis of Combinatorial Circuits under XBD0 Model", ICCAD, 1997, pp. 176-181
[9]
H.Yalcin, J.P.Hayes, "Event propagation conditions in circuit delay computation", ACM Transactions on Design Automation of Electronic Systems, July 1997

Cited By

View all
  • (2013)NBTI-aware circuit node criticality computationACM Journal on Emerging Technologies in Computing Systems10.1145/24916819:3(1-19)Online publication date: 8-Oct-2013
  • (2007)Accurate timing analysis using SAT and pattern-dependent delay modelsProceedings of the conference on Design, automation and test in Europe10.5555/1266366.1266586(1018-1023)Online publication date: 16-Apr-2007
  • (2005)Efficient static timing analysis and applications using edge masksProceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays10.1145/1046192.1046215(174-183)Online publication date: 20-Feb-2005
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
ICCAD '00: Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design
November 2000
558 pages
ISBN:0780364481

Sponsors

Publisher

IEEE Press

Publication History

Published: 05 November 2000

Check for updates

Qualifiers

  • Article

Conference

ICCAD '00
Sponsor:
ICCAD '00: International Conference on Computer Aided Design
November 5 - 9, 2000
California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)17
  • Downloads (Last 6 weeks)4
Reflects downloads up to 07 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2013)NBTI-aware circuit node criticality computationACM Journal on Emerging Technologies in Computing Systems10.1145/24916819:3(1-19)Online publication date: 8-Oct-2013
  • (2007)Accurate timing analysis using SAT and pattern-dependent delay modelsProceedings of the conference on Design, automation and test in Europe10.5555/1266366.1266586(1018-1023)Online publication date: 16-Apr-2007
  • (2005)Efficient static timing analysis and applications using edge masksProceedings of the 2005 ACM/SIGDA 13th international symposium on Field-programmable gate arrays10.1145/1046192.1046215(174-183)Online publication date: 20-Feb-2005
  • (2004)RESTAProceedings of the 14th ACM Great Lakes symposium on VLSI10.1145/988952.989050(407-412)Online publication date: 26-Apr-2004
  • (2003)Clock Scheduling and Clocktree Construction for High Performance ASICSProceedings of the 2003 IEEE/ACM international conference on Computer-aided design10.5555/996070.1009896Online publication date: 9-Nov-2003
  • (2003)Death, taxes and failing chipsProceedings of the 40th annual Design Automation Conference10.1145/775832.775921(343-347)Online publication date: 2-Jun-2003
  • (2003)Closed-Form Crosstalk Noise Delay MetricsAnalog Integrated Circuits and Signal Processing10.1023/A:102412653187235:2-3(143-156)Online publication date: 1-May-2003
  • (2002)WTAProceedings of the 2002 IEEE/ACM international conference on Computer-aided design10.1145/774572.774665(625-631)Online publication date: 10-Nov-2002
  • (2001)On the signal bounding problem in timing analysisProceedings of the 2001 IEEE/ACM international conference on Computer-aided design10.5555/603095.603200(507-514)Online publication date: 4-Nov-2001

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media