research-article

Incremental criticality and yield gradients

Authors:

Vladimir Zolotov,

Chandu VisweswariahAuthors Info & Claims

DATE '08: Proceedings of the conference on Design, automation and test in Europe

Pages 1130 - 1135

https://doi.org/10.1145/1403375.1403652

Published: 10 March 2008 Publication History

Abstract

Criticality and yield gradients are two crucial diagnostic metrics obtained from Statistical Static Timing Analysis (SSTA). They provide valuable information to guide timing optimization and timing-driven physical synthesis. Existing work in the literature, however, computes both metrics in a non-incremental manner, i.e., after one or more changes are made in a previously-timed circuit, both metrics need to be recomputed from scratch, which is obviously undesirable for optimizing large circuits. The major contribution of this paper is to propose two novel techniques to compute both criticality and yield gradients efficiently and incrementally. In addition, while node and edge criticalities are addressed in the literature, this paper for the first time describes a technique to compute path criticalities. To further improve algorithmic efficiency, this paper also proposes a novel technique to update "chip slack" incrementally. Numerical results show our methods to be over two orders of magnitude faster than previous work.

References

[1]

H. Chang and S. S. Sapatnekar. Statistical timing analysis considering spatial correlations using a single PERT-like traversal. Proc. ICCAD, pages 621--625, November 2003.

Digital Library

[2]

C. Visweswariah, K. Ravindran, K. Kalafala, S. G. Walker, and S. Narayan. First-order incremental block-based statistical timing analysis. Proc. DAC, pages 331--336, June 2004.

Digital Library

[3]

A. Agarwal, D. Blaauw, and V. Zolotov. Statistical timing analysis for intra-die process variations with spatial correlations. Proc. ICCAD, pages 900--907, November 2003.

Digital Library

[4]

L. Zhang, Y. Hu, and C. C. Chen. Block based statistical timing analysis with extended canonical timing model. Proc. ASPDAC, pages 250--253, January 2005.

Digital Library

[5]

M. R. Guthaus, N. Venkateswaran, C. Visweswariah, and V. Zolotov. Gate sizing using incremental parameterized statistical timing analysis. Proc. ICCAD, pages 1029--1036, November 2005.

Digital Library

[6]

J. Xiong, V. Zolotov, C. Visweswariah, and N. Venkateswaran. Criticality computation in parameterized statistical timing. Proc. DAC, pages 63--68, July 2006.

Digital Library

[7]

R. P. Abato, A. D. Drumm, D. J. Hathaway, and L. P. P. P. van Ginneken. Incremental timing analysis. U. S. Patent 5,508,937, April 1996.

[8]

A. Agarwal, K. Chopra, D. Blaauw, and V. Zolotov. Circuit optimization using statistical timing analysis. Proc. DAC, pages 321--324, June 2005.

Digital Library

[9]

X. Li, J. Le, M. Celik, and L. T. Pileggi. Defining statistical sensitivity for timing optimization of logic circuits with large-scale process and environmental variations. Proc. ICCAD, pages 844--851, November 2005.

Digital Library

[10]

K. Chopra, S. Shah, A. Srivastava, D. Blaauw, and D. Sylvester. Parametric yield maximization using gate sizing based on efficient statistical power and delay gradient computation. Proc. ICCAD, pages 1023--1028, November 2005.

Digital Library

[11]

V. Zolotov, J. Xiong, and C. Visweswariah. Computation of yield gradients from statistical timing analysis. Proc. 2006 TAU, pages 125--130, February 2006.

[12]

J. Singh and S. Sapatnekar. Statistical timing analysis with correlated non-Gaussian parameters using independent component analysis. In Proc. DAC, pages 155--160, July 2006.

Digital Library

[13]

L. Cheng, J. Xiong, and L. He. Non-linear statistical static timing analysis for non-Gaussian variation sources. In Proc. DAC, pages 250--255, June 2007.

Digital Library

[14]

H. Chang, V. Zolotov, C. Visweswariah, and S. Narayan. Parameterized block-based statistical timing analysis with non-Gaussian and nonlinear parameters. Proc. DAC, pages 71--76, June 2005.

Digital Library

[15]

L. Zhang, W. Chen, Y. Hu, J. A. Gubner, and C. C. Chen. Correlation-preserved non-Gaussian statistical timing analysis with quadratic timing model. In Proc. DAC, pages 83--88, June 2005.

Digital Library

[16]

Y. Zhan, A. J. Strojwas, X. Li, and L. T. Pileggi. Correlation-aware statistical timing analysis with non-Gaussian delay distribution. In Proc. DAC, pages 77--82, June 2005.

Digital Library

[17]

C. E. Clark. The greatest of a finite set of random variables. Operations Research, pages 145--162, March-April 1961.

[18]

D. Sinha, H. Zhou, and N. V. Shenoy. Advances in computation of the maximum of a set of random variables. Proc. ISQED, pages 306--311, March 2006.

Digital Library

Cited By

Raji MGhavami BRaji MGhavami B(2022)Joint Timing Yield and Lifetime Reliability Optimization of Integrated CircuitsLifetime Reliability-aware Design of Integrated Circuits10.1007/978-3-031-15345-7_5(65-83)Online publication date: 17-Nov-2022
https://doi.org/10.1007/978-3-031-15345-7_5
Ebrahimipour SGhavami BRaji M(2021)A Statistical Gate Sizing Method for Timing Yield and Lifetime Reliability Optimization of Integrated CircuitsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2020.29879469:2(759-773)Online publication date: 1-Apr-2021
https://doi.org/10.1109/TETC.2020.2987946
Ebrahimipour SGhavami BRaji M(2019)Adjacency criticality: a simple yet effective metric for statistical timing yield optimisation of digital integrated circuitsIET Circuits, Devices & Systems10.1049/iet-cds.2018.561613:7(979-987)Online publication date: 22-Oct-2019
https://doi.org/10.1049/iet-cds.2018.5616
Show More Cited By

Index Terms

Incremental criticality and yield gradients
1. Hardware

Recommendations

Quantifying Instruction Criticality
PACT '02: Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques

Information about instruction criticality can be used to control the application of micro-architectural resources efficiently. To this end, several groups have proposed methods to predict critical instructions. This paper presents a framework that ...
Multiple incremental decremental learning of support vector machines

We propose a multiple incremental decremental algorithm of support vector machines (SVM). In online learning, we need to update the trained model when some new observations arrive and/or some observations become obsolete. If we want to add or remove ...
Criticality analyzer and tester: an effective approach for critical component identification & verification using ABC

Now a days, software industries satisfy users' needs through developing software. To satisfy their customers, the software developers need to identify the critical components that make serious impacts on users' requirements. Tracking critical components ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DATE '08: Proceedings of the conference on Design, automation and test in Europe

March 2008

1575 pages

ISBN:9783981080131

DOI:10.1145/1403375

General Chair:
Donatella Sciuto
Politecnico di Milano, Italy

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

The EDA Consortium
EDAA: European Design Automation Association
ECSI
SIGDA: ACM Special Interest Group on Design Automation
The IEEE Computer Society TTTC
IEEE Council on Electronic Design Automation (CEDA)
The Russian Academy of Sciences: The Russian Academy of Sciences

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 10 March 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

DATE '08

Sponsor:

EDAA
SIGDA
The Russian Academy of Sciences

DATE '08: Design, Automation and Test in Europe

March 10 - 14, 2008

Munich, Germany

Acceptance Rates

Overall Acceptance Rate 518 of 1,794 submissions, 29%

Upcoming Conference

DATE '25

Sponsor:
sigda

Design, Automation and Test in Europe

March 31 - April 2, 2025

Lyon , France

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
115
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Raji MGhavami BRaji MGhavami B(2022)Joint Timing Yield and Lifetime Reliability Optimization of Integrated CircuitsLifetime Reliability-aware Design of Integrated Circuits10.1007/978-3-031-15345-7_5(65-83)Online publication date: 17-Nov-2022
https://doi.org/10.1007/978-3-031-15345-7_5
Ebrahimipour SGhavami BRaji M(2021)A Statistical Gate Sizing Method for Timing Yield and Lifetime Reliability Optimization of Integrated CircuitsIEEE Transactions on Emerging Topics in Computing10.1109/TETC.2020.29879469:2(759-773)Online publication date: 1-Apr-2021
https://doi.org/10.1109/TETC.2020.2987946
Ebrahimipour SGhavami BRaji M(2019)Adjacency criticality: a simple yet effective metric for statistical timing yield optimisation of digital integrated circuitsIET Circuits, Devices & Systems10.1049/iet-cds.2018.561613:7(979-987)Online publication date: 22-Oct-2019
https://doi.org/10.1049/iet-cds.2018.5616
S RVasudevan V(2016)Efficient Algorithms for Discrete Gate Sizing and Threshold Voltage Assignment Based on an Accurate Analytical Statistical Yield GradientACM Transactions on Design Automation of Electronic Systems10.1145/289681921:4(1-27)Online publication date: 18-May-2016
https://dl.acm.org/doi/10.1145/2896819
Ramprasath SVasudevan V(2015)An efficient algorithm for statistical timing yield optimizationProceedings of the 52nd Annual Design Automation Conference10.1145/2744769.2744796(1-6)Online publication date: 7-Jun-2015
https://dl.acm.org/doi/10.1145/2744769.2744796
Ramprasath SVasudevan VHu A(2012)On the computation of criticality in statistical timing analysisProceedings of the International Conference on Computer-Aided Design10.1145/2429384.2429418(172-179)Online publication date: 5-Nov-2012
https://dl.acm.org/doi/10.1145/2429384.2429418
Sinha DVisweswariah CVenkateswaran NXiong JZolotov VGroeneveld PSciuto DHassoun S(2012)Reversible statistical max/min operationProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228554(1067-1073)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228554
Li BChen NSchlichtmann UPhillips JHu AGraeb H(2011)Fast statistical timing analysis for circuits with post-silicon tunable clock buffersProceedings of the International Conference on Computer-Aided Design10.5555/2132325.2132354(111-117)Online publication date: 7-Nov-2011
https://dl.acm.org/doi/10.5555/2132325.2132354
Chung JXiong JZolotov VAbraham J(2011)Path criticality computation in parameterized statistical timing analysisProceedings of the 16th Asia and South Pacific Design Automation Conference10.5555/1950815.1950873(249-254)Online publication date: 25-Jan-2011
https://dl.acm.org/doi/10.5555/1950815.1950873
Chung JXiong JZolotov VAbraham JStok LDutt NHassoun S(2011)Testability driven statistical path selectionProceedings of the 48th Design Automation Conference10.1145/2024724.2024822(417-422)Online publication date: 5-Jun-2011
https://dl.acm.org/doi/10.1145/2024724.2024822
Show More Cited By

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.

Media

Figures

Other

Tables

View Table of Contents