research-article

Testability driven statistical path selection

Authors:

Vladimir Zolotov,

Jacob AbrahamAuthors Info & Claims

DAC '11: Proceedings of the 48th Design Automation Conference

Pages 417 - 422

https://doi.org/10.1145/2024724.2024822

Published: 05 June 2011 Publication History

Abstract

In the face of large-scale process variations, statistical timing methodology has advanced significantly over the last few years, and statistical path selection takes advantage of it in at-speed testing. In deterministic path selection, the separation of path selection and test generation is known to require time consuming iteration between the two processes. This paper shows that in statistical path selection, this is not only the case, but also the quality of results can be severely degraded even after the iteration. To deal with this issue, we consider testability in the first place by integrating a SAT solver, and this necessitates a new statistical path selection method. Our proposed method is based on a generalized path criticality metric which properties allow efficient pruning. Our experimental results show that the proposed method achieves 47% better quality of results on average, and up to 361x speedup compared to statistical path selection followed by test generation.

References

[1]

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

Digital Library

[2]

K. Cheng and H. Chen. Delay testing for non-robust untestable circuits. In Proc. ITC, pages 954--961, 2002.

Digital Library

[3]

J. Chung and J. A. Abraham. Recursive Path Selection for Delay Fault Testing. In Proc. VTS, pages 65--70, 2009.

Digital Library

[4]

C. E. Clark. The greatest of a finite set of random variables. In Operations Research, pages 85--91, 1961.

[5]

N. Ećn and N. Sorensson. An extensible SAT-solver. In Theory and Applications of Satisfiability Testing, pages 333--336, 2004.

[6]

K. Fuchs, F. Fink, and M. Schulz. Dynamite: an efficient automatic test pattern generation system forpath delay faults. IEEE TCAD, 10(10):1323--1335, 1991.

Digital Library

[7]

K. Fuchs, M. Pabst, and T. Rossel. Resist: a recursive test pattern generation algorithm for path delay faults considering various test classes. IEEE TCAD, 13(12):1550--1562, 1994.

Digital Library

[8]

J. Kim, J. Whittemore, J. Marques-Silva, and K. Sakallah. On applying incremental satisfiability to delay fault testing. In Proc. DATE, pages 380--384, 2000.

Digital Library

[9]

X. Li, J. Le, M. Celik, and L. Pileggi. Defining statistical timing sensitivity for logic circuits with large-scale process and environmental variations. IEEE TCAD, 27(6):1041--1054, 2008.

Digital Library

[10]

Q. Liu and S. Sapatnekar. Synthesizing a representative critical path for post-silicon delay prediction. In Proc. ISPD, pages 183--190, 2009.

Digital Library

[11]

G. Luong and D. Walker. Test generation for global delay faults. In Proc. ITC, 1996.

Digital Library

[12]

P. McGeer and R. Brayton. Efficient algorithms for computing the longest viable path in a combinational network. In Proc. DAC, pages 561--567, 2006.

Digital Library

[13]

L. Scheffer. Explicit computation of performance as a function of process variation. In IEEE/ACM TAU, pages 1--8, 2002.

Digital Library

[14]

M. Sharma and J. Patel. Finding a small set of longest testable paths that cover every gate. In Proc. ITC, pages 974--982, 2002.

Digital Library

[15]

C. Visweswariah, K. Ravindran, K. Kalafala, S. Walker, S. Narayan, D. Beece, J. Piaget, N. Venkateswaran, and J. Hemmett. First-order incremental block-based statistical timing analysis. IEEE TCAD, (10):2170--2180, 2006.

Digital Library

[16]

J. Xiong, Y. Shi, V. Zolotov, and C. Visweswariah. Pre-ATPG path selection for near optimal post-ATPG process space coverage. In Proc. ICCAD, pages 89--96, 2009.

Digital Library

[17]

J. Xiong, Y. Shi, V. Zolotov, and C. Visweswariah. Statistical multilayer process space coverage for at-speed test. In Proc. DAC, pages 340--345, 2009.

Digital Library

[18]

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

Digital Library

[19]

J. Xiong, V. Zolotov, and C. Visweswariah. Incremental criticality and yield gradients. In Proc. DATE, pages 1130--1135, 2008.

Digital Library

[20]

V. Zolotov, J. Xiong, H. Fatemi, and C. Visweswariah. Statistical path selection for at-speed test. In Proc. ICCAD, pages 624--631, 2008.

Digital Library

Cited By

Alladi PTragoudas S(2017)Aging-aware critical paths for process related validation in the presence of NBTI2017 18th International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2017.7918356(445-448)Online publication date: Mar-2017
https://doi.org/10.1109/ISQED.2017.7918356
Javvaji PTragoudas S(2017)Efficient computation of the sensitization probability of a critical path considering process variations and path correlation2017 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2017.8050439(1-4)Online publication date: May-2017
https://doi.org/10.1109/ISCAS.2017.8050439
Andres BSauer MGebser MSchubert TBecker BSchaub T(2013)Accurate Computation of Sensitizable Paths Using Answer Set ProgrammingProceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning - Volume 814810.1007/978-3-642-40564-8_10(92-101)Online publication date: 15-Sep-2013
https://dl.acm.org/doi/10.1007/978-3-642-40564-8_10
Show More Cited By

Recommendations

Statistical path selection for at-speed test

Process variations make at-speed testing significantly more difficult. They cause subtle delay changes that are distributed in contrast to the localized nature of a traditional fault model. Due to parametric variations, different paths can be critical ...
Testability-Driven Statistical Path Selection

In the face of large-scale process variations, statistical timing methodology has advanced significantly over the last few years, and statistical path selection takes advantage of it in at-speed testing. In deterministic path selection, the separation ...
A Hierarchical Technique for Statistical Path Selection and Criticality Computation

Due to process variations, every path in the circuit is associated with a probability of being critical and a measure of this probability is the criticality of the path. Identification of critical paths usually proceeds in two steps, namely, generation ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

DAC '11: Proceedings of the 48th Design Automation Conference

June 2011

1055 pages

ISBN:9781450306362

DOI:10.1145/2024724

General Chair:
Leon Stok
IBM Corp., Hopewell Jct., NY
,
Program Chairs:
Nikil Dutt
Univ. of California, Irvine, CA
,
Soha Hassoun
Tufts Univ., Medford, MA

Copyright © 2011 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

EDAC: Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation
IEEE Council on Electronic Design Automation (CEDA)

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

DAC '11

Sponsor:

EDAC
SIGDA

DAC '11: The 48th Annual Design Automation Conference 2011

June 5 - 10, 2011

California, San Diego

Acceptance Rates

Overall Acceptance Rate 1,264 of 4,035 submissions, 31%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
103
Total Downloads

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

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alladi PTragoudas S(2017)Aging-aware critical paths for process related validation in the presence of NBTI2017 18th International Symposium on Quality Electronic Design (ISQED)10.1109/ISQED.2017.7918356(445-448)Online publication date: Mar-2017
https://doi.org/10.1109/ISQED.2017.7918356
Javvaji PTragoudas S(2017)Efficient computation of the sensitization probability of a critical path considering process variations and path correlation2017 IEEE International Symposium on Circuits and Systems (ISCAS)10.1109/ISCAS.2017.8050439(1-4)Online publication date: May-2017
https://doi.org/10.1109/ISCAS.2017.8050439
Andres BSauer MGebser MSchubert TBecker BSchaub T(2013)Accurate Computation of Sensitizable Paths Using Answer Set ProgrammingProceedings of the 12th International Conference on Logic Programming and Nonmonotonic Reasoning - Volume 814810.1007/978-3-642-40564-8_10(92-101)Online publication date: 15-Sep-2013
https://dl.acm.org/doi/10.1007/978-3-642-40564-8_10
Jiang JSauer MCzutro ABecker BPolian IRosenstiel WMacii E(2012)On the optimality of K longest path generation algorithm under memory constraintsProceedings of the Conference on Design, Automation and Test in Europe10.5555/2492708.2492813(418-423)Online publication date: 12-Mar-2012
https://dl.acm.org/doi/10.5555/2492708.2492813
Jie Jiang Sauer MCzutro ABecker BPolian I(2012)On the optimality of K longest path generation algorithm under memory constraints2012 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.1109/DATE.2012.6176507(418-423)Online publication date: Mar-2012
https://doi.org/10.1109/DATE.2012.6176507
Sauer MJiang JCzutro APolian IBecker B(2011)Efficient SAT-Based Search for Longest Sensitisable PathsProceedings of the 2011 Asian Test Symposium10.1109/ATS.2011.43(108-113)Online publication date: 20-Nov-2011
https://dl.acm.org/doi/10.1109/ATS.2011.43

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