Article

Statistical Timing Analysis for Intra-Die Process Variations with Spatial Correlations

Authors:

Vladimir ZolotovAuthors Info & Claims

ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design

Page 900

Published: 09 November 2003 Publication History

Abstract

Process variations have become a critical issue in performanceverification of high-performance designs. We present a new, statisticaltiming analysis method that accounts for inter- and intra-dieprocess variations and their spatial correlations. Since statisticaltiming analysis has an exponential run time complexity, we proposea method whereby a statistical bound on the probability distributionfunction of the exact circuit delay is computed with linear run time.First, we develop a model for representing inter- and intra-die variationsand their spatial correlations. Using this model, we thenshow how gate delays and arrival times can be represented as a sumof components, such that the correlation information betweenarrival times and gate delays is preserved. We then show howarrival times are propagated and merged in the circuit to obtain anarrival time distribution that is an upper bound on the distributionof the exact circuit delay. We prove the correctness of the bound andalso show how the bound can be improved by propagating multiplearrival times. The proposed algorithms were implemented andtested on a set of benchmark circuits under several process variationscenarios. The results were compared with Monte Carlo simulationand show an accuracy of 3.32% on average over all test cases.

References

[1]

{1} S. Nassif, "Delay Variability: Sources, Impacts and Trends," Proceedings of ISSCC, 2000.

[2]

{2} A. Kahng, Y. Pati, "Subwavelength optical lithography: challenges and impacts on physical design," Proceedings of ISPD, 1999.

Digital Library

[3]

{3} M. Orshansky, L. Milor, P. Chen, K. Keutzer, C. Hu, "Impact of systematic spatial intra-chip gate length variability on performance of high-speed digital circuits", ICCAD 2000, pp. 62- 67.

Digital Library

[4]

{4} V. Mehrotra, S.L. Sam, D. Boning, A. Chandrakasan, R. Vallishayee, S. Nassif "A methodology for modelling the effects of systematic within-die interconnect and device variation on circuit performance. DAC 2000.

Digital Library

[5]

{5} Y. Deguchi, N. Ishiura, S. Yajima, "Probabilistic CTSS: analysis of timing error probability in asynchronous logic circuits," Proceedings IEEE/ACM Design Automation Conference, 1991.

Digital Library

[6]

{6} S. Devadas, H. F. Jyu, K. Keutzer, S. Malik, "Statistical timing analysis of combinational circuits ", ICCD 1992 pp. 38-43.

Digital Library

[7]

{7} H. F. Jyu, S. Malik, "Statistical timing optimization of combinational logic circuits" ICCD 1993. pp. 77-80.

[8]

{8} R.B. Brawhear, N. Menezes, C. Oh, L. Pillage, R. Mercer, "Predicting circuit performance using circuit-level statistical timing analysis" European Design and Test Conference, 1994.

[9]

{9} E.T.A.F. Jacobs, M.R.C.M. Berkelaar, "Gate sizing using a statistical delay model," Proceedings IEEE/ACM Design Automation and Test Europe Conference, 2000, pp. 283-290.

Digital Library

[10]

{10} R.-B. Lin; M.-C. Wu, "A new statistical approach to timing analysis of VLSI circuits", Proc. Int. Conf. on VLSI Design, 1998.

Digital Library

[11]

{11} S. Tongsima, C. Chantrapornchai, E.H.-M. Sha, N.L. Passos, "Optimizing circuits with confidence probability using probabilistic retiming," Proceedings IEEE ISCAS, 1998, pp. 270- 273.

[12]

{12} L. Sheffer, "Explicit Computation of Performance as a Function of Process Variation", Int. Workshop on Timing Issues in the Specification and Synthesis of Digital Systems, TAU 2002.

Digital Library

[13]

{13} M. Berkelaar, "Statistical Delay Calculation, a Linear Time Method," Proceedings of TAU 97, Austin, TX, December 1997.

[14]

{14} J.J Liou, K.T. Cheng, S. Kundu, A. Krstic, "Fast Statistical Timing Analysis By Probabilistic Even Propagation", DAC 2001.

Digital Library

[15]

{15} M. Orshansky, K. Keutzer, "A general probabilistic framework for worst-case timing analysis", Proc. DAC 2002.

Digital Library

[16]

{16} A. Gattiker, S. Nassif, R. Dinakar, C. Long "Timing Yield Estimation from Static Timing Analysis," Proc., ISQED 2001.

Digital Library

[17]

{17} X. Bai, C. Visweswariah, P. Strenski, D. Hathaway, "Uncertainty-aware circuit optimization," Proceedings ACM/IEEE Design Automation Conference, 2002.

Digital Library

[18]

{18} A. Agarwal, D. Blaauw, V. Zolotov, S. Vrudhula, "Computation and Refinement of Statistical Bounds on Circuit Delay," DAC 2003, pp. 348-353.

Digital Library

[19]

{19} A. Agarwal, D. Blaauw, S. Sundareswaran, V. Zolotov, M. Zhou, K. Gala, R. Panda, "Statistical Delay Computation Considering Spatial Correlations," ASP-DAC 2003, pp. 271-276.

Digital Library

[20]

{20} F. Brglez, H. Fujiwara, "A Neutral Netlist of 10 Combinatorial Benchmark Circuits", Proc. ISCAS, 1985, pp. 695-698.

Cited By

Ewetz RKoh C(2019)Scalable Construction of Clock Trees With Useful Skew and High Timing QualityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.283443738:6(1161-1174)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TCAD.2018.2834437
Khodabandeloo BKhonsari AMajidi AHajiesmaili MShin Y(2018)Task assignment and scheduling in MPSoC under process variationProceedings of the 23rd Asia and South Pacific Design Automation Conference10.5555/3201607.3201765(690-695)Online publication date: 22-Jan-2018
https://dl.acm.org/doi/10.5555/3201607.3201765
Abolmaali SKamal MAfzali-Kusha APedram M(2018)An Efficient False Path-Aware Heuristic Critical Path Selection Method with High Coverage of the Process Variation SpaceACM Transactions on Design Automation of Electronic Systems10.1145/317786623:3(1-25)Online publication date: 23-Feb-2018
https://dl.acm.org/doi/10.1145/3177866
Show More Cited By

Index Terms

Statistical Timing Analysis for Intra-Die Process Variations with Spatial Correlations

Recommendations

Statistical timing analysis under spatial correlations

Process variations are of increasing concern in today's technologies, and they can significantly affect circuit performance. An efficient statistical timing analysis algorithm that predicts the probability distribution of the circuit delay considering ...
Mapping Statistical Process Variations Toward Circuit Performance Variability: An Analytical Modeling Approach

An analytical gate delay model is developed by integrating short-channel effects and the Alpha-power law-based timing model. As verified with an industrial 90-nm technology, this analytical approach accurately predicts both nominal delay and delay ...
Statistical Timing Analysis Using Bounds
DATE '03: Proceedings of the conference on Design, Automation and Test in Europe - Volume 1

The growing impact of within-die process variation has created the need for statistical timing analysis, where gate delays are modeled as random variables. Statistical timing analysis has traditionally suffered from exponential run time complexity with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design

November 2003

899 pages

ISBN:1581137621

Sponsors

SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society

United States

Publication History

Published: 09 November 2003

Check for updates

Qualifiers

Article

Conference

ICCAD03

Sponsor:

SIGDA

ICCAD03: The International Conference on Computer-Aided Design

November 9 - 13, 2003

Acceptance Rates

ICCAD '03 Paper Acceptance Rate 129 of 490 submissions, 26%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

131
Total Citations
View Citations
1,078
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

Ewetz RKoh C(2019)Scalable Construction of Clock Trees With Useful Skew and High Timing QualityIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2018.283443738:6(1161-1174)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TCAD.2018.2834437
Khodabandeloo BKhonsari AMajidi AHajiesmaili MShin Y(2018)Task assignment and scheduling in MPSoC under process variationProceedings of the 23rd Asia and South Pacific Design Automation Conference10.5555/3201607.3201765(690-695)Online publication date: 22-Jan-2018
https://dl.acm.org/doi/10.5555/3201607.3201765
Abolmaali SKamal MAfzali-Kusha APedram M(2018)An Efficient False Path-Aware Heuristic Critical Path Selection Method with High Coverage of the Process Variation SpaceACM Transactions on Design Automation of Electronic Systems10.1145/317786623:3(1-25)Online publication date: 23-Feb-2018
https://dl.acm.org/doi/10.1145/3177866
Bal ASaha SRoy SChakraborty K(2017)Revamping timing error resilience to tackle choke points at NTC systemsProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130623(1020-1025)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130623
Esirci FBayrakci A(2017)Hardware trojan detection based on correlated path delays in defiance of variations with spatial correlationsProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130416(163-168)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130416
Ewetz RKoh C(2017)Fast clock scheduling and an application to clock tree synthesisIntegration, the VLSI Journal10.1016/j.vlsi.2016.10.01256:C(115-127)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.vlsi.2016.10.012
Somashekar ATragoudas SJayabharathi RGangadhar S(2016)Non-enumerative Generation of Path Delay Distributions and Its Application to Critical Path SelectionACM Transactions on Design Automation of Electronic Systems10.1145/294032722:1(1-21)Online publication date: 13-Dec-2016
https://dl.acm.org/doi/10.1145/2940327
Mercati PPaterna FBartolini AImani MBenini LRosing TCoskun AMargala MBehjat LHan J(2016)VarDroidProceedings of the 26th edition on Great Lakes Symposium on VLSI10.1145/2902961.2902971(269-274)Online publication date: 18-May-2016
https://dl.acm.org/doi/10.1145/2902961.2902971
Ewetz RKoh C(2016)Construction of Reconfigurable Clock Trees for MCMM Designs Using Mode Separation and Scenario CompressionACM Transactions on Design Automation of Electronic Systems10.1145/288360921:4(1-27)Online publication date: 18-May-2016
https://dl.acm.org/doi/10.1145/2883609
Tang AGao XChen LJha N(2016)Delay/Power Modeling and Optimization of FinFET Circuit Modules under PVT VariationsACM Journal on Emerging Technologies in Computing Systems10.1145/279523112:4(1-21)Online publication date: 8-Mar-2016
https://dl.acm.org/doi/10.1145/2795231
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