Article

Efficient Boolean characteristic function for fast timed ATPG

Authors:

Yue-Lung Chang,

Shih-Chieh ChangAuthors Info & Claims

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

Pages 96 - 99

https://doi.org/10.1145/1233501.1233522

Published: 05 November 2006 Publication History

Abstract

Circuit timing analysis is important in various aspects of circuit optimization. The problem of finding input vectors achieving functional and temporal requirements is known as timed Automatic Test Pattern Generation (timed ATPG). A timed ATPG algorithm will return an input vector that satisfies functional and temporal requirements simultaneously when evaluated. Several previous works use timed ATPG as a core engine for solving problems related to timing analysis, such as crosstalk and maximum instantaneous current analysis. Despite the usefulness of timed ATPG, traditional timed ATPG is slow and unscalable for large circuits. In this paper, we present a very efficient way for timed ATPG. On average, our results are 8 times faster than the most recent work, and in some cases, up to 32 times faster.

References

[1]

P. Ashar, and S. Malik, "Functional Timing Analysis Using ATPG," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 14, no. 8, pp. 1025--1030, Aug. 1995.

Digital Library

[2]

R. I. Bahar, H. Cho, G. D. Hachtel, E. Macii, and F. Somenzi, "Timing Analysis of Combinational Circuits using ADD's," in Proc. of IEEE European Design Test Conference, pp. 625--629, 1994.

[3]

H.-C. Chen, and D. Du, "Path Sensitization in Critical Path Problem," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 2, pp. 196--207, Feb. 1993.

Digital Library

[4]

S. Devadas, K. Keutzer, and S. Malik, "Computation of Floating Mode Delay in Combinational Circuits: Theory and Algorithms," IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, vol. 12, no. 12, pp. 1913--1923, Dec. 1993.

Digital Library

[5]

J. L. Güntzel, A. C. M. Pinto, and R. Reis "A Timed Calculus for ATG-Based Timing Analysis of Circuits with Complex Gates," in Proc. IEEE Latin American Test Workshop, pp. 234--239, 2001.

[6]

H. Kriplani, F. Najm, and I. N. Hajj, "Pattern Independent Maximum Current Estimation in Power and Ground Buses of CMOS VLSI Circuits: Algorithms, Signal Correlations, and Their Resolution," IEEE Trans. on Computer-Aided Design, vol. 14, no. 8, pp. 998--1012, Aug. 1995.

Digital Library

[7]

Y.-M. Jiang, A. Krstic, and K.-T. Cheng, "Estimation for Maximum Instantaneous Current Through Supply Lines for CMOS Circuits," IEEE Trans. on Very Large Scale Integration Systems, vol. 8, no. 1, pp. 61--73, Feb. 2000.

Digital Library

[8]

Y.-M. Jiang, K.-T. Cheng, and A. Krstic, "Estimation of Maximum Power and Instantaneous Current Using a Genetic Algorithm," in Proc. of IEEE Custom Integrated Circuits Conference, pp. 135--138, 1997.

[9]

R. Kundu, and R. D. Blanton, "Timed Test Generation for Crosstalk Switch Failure in Domino CMOS Circuits," in Proc. of the IEEE VLSI Test Symposium, pp. 379--385, 2002.

Digital Library

[10]

R. Kundu, and R. D. Blanton, "ATPG for Noise-Induced Switch Failures in Domino Logic," in Proc. of the ICCAD, pp. 765--768, 2003.

Digital Library

[11]

P. C. McGeer, A. Saldanha, P. R. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vicentelli, "Timing Analysis and Delay-Fault Test Generation using Path-Recursive Functions," in Proc. of the ICCAD, pp. 180--183, 1991.

[12]

M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, and S. Malik, "Chaff: Engineering an efficient SAT solver," in Proc. of the DAC, pp. 530--535, 2001.

Digital Library

[13]

A. Nadel, "Backtrack Search Algorithms for Propositional Satisfiability: Review and Innovations," Master's Thesis, the Hebrew University of Jerusalem, 2002.

[14]

J. P. M. Silva, and K. A. Sakallah, "Efficient and Robust Test Generation-Based Timing Analysis," in Proc. of the International Symposium on Circuits and Systems, pp. 303--306, 1994.

[15]

J. P. M. Silva, and K. A. Sakallah, "GRASP: A Search Algorithm for Propositional Satisfiability," IEEE Trans. on Computers, vol. 48, no. 5, pp. 506--521, May 1999.

Digital Library

[16]

L. G. Silva, J. P. M. Silva, L. M. Silveira, and K. A. Sakallah, "Satisfiability Models and Algorithms for Circuit Delay Computation," ACM Trans. on Design Automation of Electronic Systems, vol. 7, no. 1, pp. 137--158, Jan. 2002.

Digital Library

[17]

H. Yalcin, and J. P. Hayes, "Hierarchical Timing Analysis Using Conditional Delays," in Proc. of the ICCAD, pp. 371--377, 1995.

Digital Library

[18]

H. Zhang, "SATO: An Efficient Propositional Prover," in Proc. of International Conference on Automated Deduction, pp. 272--275, 1997.

Digital Library

Cited By

Wan LChen DShanbhag NPoncino MChou PAmerasekera A(2012)CCPProceedings of the 2012 ACM/IEEE international symposium on Low power electronics and design10.1145/2333660.2333695(135-140)Online publication date: 30-Jul-2012
https://dl.acm.org/doi/10.1145/2333660.2333695
Wan LChen D(2012)Analysis of Digital Circuit Dynamic Behavior With Timed Ternary Decision Diagrams for Better-Than-Worst-Case DesignIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2011.218151231:5(662-675)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1109/TCAD.2011.2181512
Wan LChen DScheffer LPhillips JHu A(2010)Analysis of circuit dynamic behavior with timed ternary decision diagramProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133539(516-523)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133539
Show More Cited By

Index Terms

Efficient Boolean characteristic function for fast timed ATPG
1. Hardware

Recommendations

BIST-Guided ATPG
ISQED '05: Proceedings of the 6th International Symposium on Quality of Electronic Design

This paper presents a new reseeding technique that considerably reduces the storage required for the seeds as well as the test application time by alternating between ATPG and reseeding to optimize the seed selection. The technique avoids loading a new ...
STAR-ATPG: A High Speed Test Pattern Generator for Large Scan Designs
ITC '99: Proceedings of the 1999 IEEE International Test Conference

Star test is a novel test pattern generation technique inwhich a few test vectors serve as centers of clusters for othertest vectors which are derived by complementing at randomtheir coordinates. By properly selecting the deterministicpatterns as ...
Fast and waveform-accurate hazard-aware SAT-based TSOF ATPG
DATE '17: Proceedings of the Conference on Design, Automation & Test in Europe

Opens are known to be one of the predominant defects in nanoscale technologies. Especially with an increasing number of complex cells in today's VLSI designs intra-gate opens are becoming a major problem. The generation of tests for these faults is hard,...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

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

November 2006

147 pages

ISBN:1595933891

DOI:10.1145/1233501

General Chair:
Soha Hassoun
Tufts Univ., Medford, MA

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

SIGDA: ACM Special Interest Group on Design Automation
IEEE-CAS: Circuits & Systems
IEEE-CS: Computer Society

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ICCAD06

Sponsor:

SIGDA
IEEE-CAS
IEEE-CS

ICCAD06: The International Conference on Computer-Aided Design 2006

November 5 - 9, 2006

California, San Jose

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
142
Total Downloads

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

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wan LChen DShanbhag NPoncino MChou PAmerasekera A(2012)CCPProceedings of the 2012 ACM/IEEE international symposium on Low power electronics and design10.1145/2333660.2333695(135-140)Online publication date: 30-Jul-2012
https://dl.acm.org/doi/10.1145/2333660.2333695
Wan LChen D(2012)Analysis of Digital Circuit Dynamic Behavior With Timed Ternary Decision Diagrams for Better-Than-Worst-Case DesignIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2011.218151231:5(662-675)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1109/TCAD.2011.2181512
Wan LChen DScheffer LPhillips JHu A(2010)Analysis of circuit dynamic behavior with timed ternary decision diagramProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133539(516-523)Online publication date: 7-Nov-2010
https://dl.acm.org/doi/10.5555/2133429.2133539
Wan LChen D(2010)Analysis of circuit dynamic behavior with timed ternary decision diagram2010 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1109/ICCAD.2010.5653852(516-523)Online publication date: Nov-2010
https://doi.org/10.1109/ICCAD.2010.5653852
Wan LChen DRoychowdhury J(2009)DynaTuneProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687430(172-179)Online publication date: 2-Nov-2009
https://dl.acm.org/doi/10.1145/1687399.1687430
Su YWang DChang SMarek-Sadowska MLevitan S(2007)An efficient mechanism for performance optimization of variable-latency designsProceedings of the 44th annual Design Automation Conference10.1145/1278480.1278721(976-981)Online publication date: 4-Jun-2007
https://dl.acm.org/doi/10.1145/1278480.1278721
Hsieh CLin JChang S(2007)Efficient Transition-Mode Boolean Characteristic Function with Its Application to Maximum Instantaneous Current AnalysisProceedings of the 8th International Symposium on Quality Electronic Design10.1109/ISQED.2007.70(602-606)Online publication date: 26-Mar-2007
https://dl.acm.org/doi/10.1109/ISQED.2007.70

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