Article

Convergence-provable statistical timing analysis with level-sensitive latches and feedback loops

Authors:

Jengliang Tsai,

Charlie Chung-Ping ChenAuthors Info & Claims

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

Pages 941 - 946

https://doi.org/10.1145/1118299.1118511

Published: 24 January 2006 Publication History

Abstract

Statistical timing analysis has been widely applied to predict the timing yield of VLSI circuits when process variations become significant. Existing statistical latch timing methods are either having exponential complexity or unable to treat the random variable's self-dependence caused by the coexistence of level-sensitive latches and feedback loops.In this paper, an efficient iterative statistical timing algorithm with provable convergence is proposed for latch-based circuits with feedback loops. Based on a new notion of iteration mean, we prove that the algorithm converges unconditionally. Moreover, we show that the converged value of iteration mean can be used to predict the circuit yield during design time. Tested by ISCAS'89 benchmark circuits, the proposed algorithm shows an error of 1.1% and speedup of 303 x on average when compared with the Monte Carlo simulation.

References

[1]

S. Nassif, "Within-chip variability analysis," Electron Devices Meeting, 1998, IEDM '98 Technical Digest., International, pp. 283--286, Dec 1998.

[2]

C. S. Amin, N. Menezes, K. Killpack, F. Dartu, Y. Ismail, U. Choudhury, and N. Hakim, "Statistical static timing analysis: How simple can we get?" 42th Design Automation Conference, DAC'05, 2005.

Digital Library

[3]

J. Le, X. Li, and L. Pileggi, "Stac: statistical timing analysis with correlation," Design Automation Conference, 2004. Proceedings. 41st, pp. 343 -- 348, June 2004.

Digital Library

[4]

H. Chang and S. S. Sapatnekar, "Statistical timing analysis considering spatial correlations using a single pert-like traversal," ICCAD'03, pp. 621--625, Nov 2003.

Digital Library

[5]

C. Visweswariah, K. Ravindran, and K. Kalafala, "First-order parameterized block-based statistical timing analysis," TAU'04, Feb 2004.

[6]

L. Zhang, W. Chen, Y. Hu, and C. C. Chen, "Statistical timing analysis with extended pseudo-canonical timing model," DATE'05, March 2005.

Digital Library

[7]

M. Orshansky, C. Spanos, and C. Hu, "Circuit performance variability decomposition," 4th International Workshop on Statistical Metrology, 1999. IWSM. 1999, June 1999.

[8]

S. Tsukiyama, M. Tanaka, and M. Fukui, "A statistical static timing analysis considering correlations between delays," Proceedings of the 2001 conference on Asia South Pacific design automation, January 2001.

Digital Library

[9]

F. N. Najm and N. Menezes, "Yield estimation and optimization: Statistical timing analysis based on a timing yield model," Proceedings of the 41st annual conference on Design automation, 2004.

Digital Library

[10]

M. C.-T, Chao, L.-C. Wang, K.-T. Cheng, and S. Kundu, "Static statistical timing analysis for latch-based pipeline designs," IEEE/ACM International Conference on Computer Aided Design, 2004. ICCAD-2004, pp. 468--472, 2004.

Digital Library

[11]

R. Chen and H. Zhou, "Clock schedule verification under process variations," IEEE/ACM International Conference on Computer Aided Design, 2004. ICCAD-2004, pp. 619--625, Nov 2004.

Digital Library

[12]

K. A. Sakallah, T. Mudge, and O. Olukotun, "checktc and mintc: timing verification and optimal clocking of synchronous digital circuits," IEEE International Conference on Computer-Aided Design, 1990. ICCAD-90, pp. 552--555, 1990.

[13]

T. Szymanski and N. Shenoy, "Verifying clock schedules," IEEE/ACM International Conference on Computer-Aided Design, 1992. ICCAD-92, pp. 124 -- 131, 1992.

Digital Library

[14]

J.-F. Lee, D. Tang, and C. Wong, "A timing analysis algorithm for circuits with level-sensitive latches," IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, pp. 535 -- 543, May 1996.

Digital Library

[15]

R. M. Karp, "A characterization of the minimum cycle mean in a digraph," Discrete Mathematics, vol. 23, pp. 309--311, 1978.

[16]

S. M. Burns, "Performance analysis and optimization of asynchronous circuits," PhD Thesis, California Institute of Technology, 1991.

Digital Library

Cited By

Maji SKoh C(2022)A Scalable, Memory-Efficient Algorithm for Minimum Cycle Mean Calculation in Directed GraphsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.309730041:6(1943-1956)Online publication date: Jun-2022
https://doi.org/10.1109/TCAD.2021.3097300
Kwon HKim JKang SKim Y(2018)SoftCorner: Relaxation of Corner Values for De-terministic Static Timing Analysis of VLSI Sys-temsIEEE Access10.1109/ACCESS.2018.2875474(1-1)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2875474
Gong MZhou HLi LTao JZeng X(2011)Binning Optimization for Transparently-Latched CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.208187030:2(270-283)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1109/TCAD.2010.2081870
Show More Cited By

Index Terms

Convergence-provable statistical timing analysis with level-sensitive latches and feedback loops
1. Hardware

Recommendations

Timing verification and optimization of circuits with level-sensitive latches
Linearization of the timing analysis and optimization of level-sensitive digital synchronous circuits

This paper describes a linear programming (LP) problem formulation applicable to the static-timing analysis of large scale synchronous circuits with level-sensitive latches. Specifically, an LP formulation for the clock period minimization problem is ...
Clock independent timing verification of level-sensitive latches
EURO-DAC '91: Proceedings of the conference on European design automation

This paper presents a method to automatically handle level-sensitive latches in timing analysis/verification. Timing specifications, including delays and timing constraints, are automatically generated for the cells in the design. The generated timing ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

ASP-DAC '06: Proceedings of the 2006 Asia and South Pacific Design Automation Conference

January 2006

998 pages

ISBN:0780394518

General Chair:
Fumiyasu Hirose
Cadence Design Systems, Japan

Sponsors

IEEE Circuits and Systems Society
SIGDA: ACM Special Interest Group on Design Automation
IEICE ESS: Institute of Electronics, Information and Communication Engineers, Engineering Sciences Society
IPSJ SIG-SLDM: Information Processing Society of Japan, SIG System LSI Design Methodology

Publisher

IEEE Press

Publication History

Published: 24 January 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 466 of 1,454 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
147
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Maji SKoh C(2022)A Scalable, Memory-Efficient Algorithm for Minimum Cycle Mean Calculation in Directed GraphsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2021.309730041:6(1943-1956)Online publication date: Jun-2022
https://doi.org/10.1109/TCAD.2021.3097300
Kwon HKim JKang SKim Y(2018)SoftCorner: Relaxation of Corner Values for De-terministic Static Timing Analysis of VLSI Sys-temsIEEE Access10.1109/ACCESS.2018.2875474(1-1)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2875474
Gong MZhou HLi LTao JZeng X(2011)Binning Optimization for Transparently-Latched CircuitsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.208187030:2(270-283)Online publication date: 1-Feb-2011
https://dl.acm.org/doi/10.1109/TCAD.2010.2081870
Knoth CSchlichtmann ULi BZhang MOlbrich MAcar EEichler UHaase JLange APronath M(2011)Methods of Parameter VariationsProcess Variations and Probabilistic Integrated Circuit Design10.1007/978-1-4419-6621-6_4(91-179)Online publication date: 8-Oct-2011
https://doi.org/10.1007/978-1-4419-6621-6_4
Li BChen NSchlichtmann UScheffer LPhillips JHu A(2010)Fast statistical timing analysis of latch-controlled circuits for arbitrary clock periodsProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133540(524-531)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133540
Yuan XWang JLin Y(2010)Statistical timing verification for transparently latched circuits through structural graph traversalProceedings of the 2010 Asia and South Pacific Design Automation Conference10.5555/1899721.1899877(663-668)Online publication date: 18-Jan-2010
https://dl.acm.org/doi/10.5555/1899721.1899877
Li BChen NSchlichtmann U(2010)Fast statistical timing analysis of latch-controlled circuits for arbitrary clock periods2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2010.5653800(524-531)Online publication date: Nov-2010
https://doi.org/10.1109/ICCAD.2010.5653800
Li BChen NSchlichtmann URoychowdhury J(2009)Timing model extraction for sequential circuits considering process variationsProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687463(336-343)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687463
Gong MZhou HTao JZeng XRoychowdhury J(2009)Binning optimization based on SSTA for transparently-latched circuitsProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687462(328-335)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687462
Blaauw DChopra KSrivastava AScheffer L(2008)Statistical Timing AnalysisIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2007.90704727:4(589-607)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1109/TCAD.2007.907047

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten