More Web Proxy on the site http://driver.im/

research-article

SAT-based ATPG using multilevel compatible don't-cares

Authors:

Kanupriya Gulati,

Sunil P KhatriAuthors Info & Claims

ACM Transactions on Design Automation of Electronic Systems (TODAES), Volume 13, Issue 2

Article No.: 24, Pages 1 - 18

https://doi.org/10.1145/1344418.1344420

Published: 23 April 2008 Publication History

Abstract

In a typical IC design flow, circuits are optimized using multilevel don't cares. The computed don't cares are discarded before Technology Mapping or Automatic Test Pattern Generation (ATPG). In this paper, we present two combinational ATPG algorithms for combinational designs. These algorithms utilize the multilevel don't cares that are computed for the design during technology independent logic optimization. They are based on Boolean Satisfiability (SAT), and utilize the single stuck-at fault model. Both algorithms make use of the Compatible Observability Don't Cares (CODCs) associated with nodes of the circuit, to speed up the ATPG process. For large circuits, both algorithms make use of approximate CODCs (ACODCs), which we can compute efficiently. Our first technique speeds up fault propagation by modifying the active clauses in the transitive fanout (TFO) of the fault site. In our second technique, we define new j-active variables for specific nodes in the transitive fanin (TFI) of the fault site. Using these j-active variables we write additional clauses to speed up fault justification. Experimental results demonstrate that the combination of these techniques (when using CODCs) results in an average reduction of 45% in ATPG runtimes. When ACODCs are used, a speed-up of about 30% is obtained in the ATPG run-times for large designs. We compare our method against a commercial structural ATPG tool as well. Our method is slower for small designs, but for large designs, we obtain a 31% average speedup over the commercial tool.

References

[1]

Bhattacharya, D., Agrawal, P., and Agrawal, V. 1995. Test generation for path delay faults using binary decision diagrams. IEEE Trans. Comput. 44, 3, 434--447.

Digital Library

[2]

Brayton, R. K., Hachtel, G. D., McMullen, C. T., and Sangiovanni-Vincentelli, A. L. 1984. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers.

Digital Library

[3]

Bryant, R. E. 1986. Graph based algorithms for Boolean function representation. IEEE Trans. Comput. C-35, 677--690.

Digital Library

[4]

Chang, C. J. and Marek-Sadowska, M. 2002. ATPG-based logic synthesis: An overview. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 786--789.

Digital Library

[5]

Chang, S. C. and Marek-Sadowska, M. 1994. Perturb and simplify: multi-level boolean network optimizer. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 2--5.

Digital Library

[6]

Chang, S. C., van Ginneken, L. P. P. P., and Marek-Sadowska, M. 1996. Fast boolean optimization by rewiring. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 262--269.

Digital Library

[7]

Fujiwara, H. and Shimono, T. 1983. On the acceleration of test generation algorithms. IEEE Trans. Comput. C-31, 1137--1144.

Digital Library

[8]

Garey, M. R. and Johnson, D. S. 1979. Computers and Interactability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company.

Digital Library

[9]

Gizdarski, E. and Fujiwara, H. 2000. Spirit: satisfiability problem implementation for redundancy identification and test generation. In Proceedings of the 9th Asian Test Symposium (ATS). 171--178.

Digital Library

[10]

Gizdarski, E. and Fujiwara, H. 2002. SPIRIT: a highly robust combinational test generation algorithm. In IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst. 1446--1458.

Digital Library

[11]

Goel, P. 1981. An implicit enumeration alogorithm to generate tests for combinational logic circuits. IEEE Trans. Comput. C-31, 215--222.

Digital Library

[12]

Gupta, Yang, Z., and Ashar, P. 2001. Dynamic detection and removal of inactive clauses in SAT with application in image computation. In Proceedings of the Design Automation Conference. 536--541.

Digital Library

[13]

Huang, C. Y., Yang, B., Tsai, H. C., and Cheng, K. T. 2000. Static property checking using ATPG v.s. BDD techniques. In Proceedings of the 2000 IEEE International Test Conference. 309.

Digital Library

[14]

Huang, S. Y., Cheng, K. T., and Chen, K. C. 2001. Verifying sequential equivalence using ATPG techniques. In ACM Trans. Des. Autom. Electron. Syst. 244--275.

Digital Library

[15]

Kirkland, T. and Mercer, M. 1988. Algorithms for automatic test-pattern generation. IEEE Design & Test of Computers. Vol. 5. 43--55.

Digital Library

[16]

Kunz, W. 1994. Multi-level logic optimization by implication analysis. In IEEE/ACM International Conference on Computer-Aided Design. 6--13.

Digital Library

[17]

Kunz, W. and Pradhan, D. 1994. Recursive learning: a new implication technique for efficient solutions to CAD problems-test, verification, and optimization. IEEE Trans. Comput.-Aid. Des. Integ. Circ. Syst. 13, 9, 1143--1158.

Digital Library

[18]

Larrabee, T. 1992. Test pattern generation using boolean satisfiability. IEEE Trans. Comput.-Aid. Des. 11, 4--15.

Digital Library

[19]

McCluskey, E. 1986. Logic Design Principles: With Emphasis on Testable Semicustom Circuits. Prentice-Hall.

Digital Library

[20]

Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., and Malik, S. 2001. Chaff: Engineering an efficient SAT solver. In Proceedings of the Design Automation Conference.

Digital Library

[21]

Radecka, K. and Zilic, Z. 2001. Identifying redundant gate replacements in verification by error modeling. In Proceedings of the International Test Conference. 803--812.

Digital Library

[22]

Radecka, K. and Zilic, Z. 2002. Identifying redundant wire replacements for synthesis and verification. In Proceedings of the Asia and South Pacific Design Automation Conference and the International Conference on VLSI Design. 517--523.

Digital Library

[23]

Roth, J. 1966. Diagnosis of automata failures: A calculus and a method. IBM J. Res. Develop. 10, 278--291.

Digital Library

[24]

Safarpour, S., Veneris, A., Drechsler, R., and Lee, J. 2004. Managing don't cares in Boolean satisfiability. In Proceedings of the Design, Automation and Test in Europe Conference (DATE). Vol. 1. 260--265.

Digital Library

[25]

Saluja, N. and Khatri, S. 2004. A robust algorithm for approximate compatible observability don't care (CODC) computation. In Proceedings of the 41st Design Automation Conference. San Diego, CA, 422--427.

Digital Library

[26]

Savoj, H. and Brayton, R. 1990. The use of observability and external don't cares for the simplification of multi-level networks. In Proceedings of the 27th ACM/IEEE Design Automation Conference. Orlando.

Digital Library

[27]

Schulz, M. H., Trischler, E., and Sarfert, T. M. 1988. Socrates: A highly efficient automatic test pattern generation system. IEEE Trans. Comput.-Aid. Des. 7, 126--137.

Digital Library

[28]

Sellers, F. F., Hsiao, M. Y., and Bearnson, L. W. 1968. Analysing errors with Boolean difference. IEEE Trans. Comput. C-24, 676--683.

Digital Library

[29]

Sentovich, E. M., Singh, K. J., Lavagno, L., Moon, C., Murgai, R., Saldanha, A., Savoj, H., Stephan, P. R., Brayton, R. K., and Sangiovanni-Vincentelli, A. L. 1992. SIS: A system for sequential circuit synthesis. Tech. rep. UCB/ERL M92/41, Electronics Research Lab, University of California, Berkeley.

[30]

Shi, J., Fey, G., Drechsler, R., Glowatz, A., Hapke, F., and Schloffel, J. 2005. PASSAT: Efficient sat-based test pattern generation for industrial circuits. In Proceedings of the IEEE Computer Society Annual Symposium on VLSI. 212--217.

Digital Library

[31]

Silva, M. and Sakallah, J. 1996. GRASP-a new search algorithm for satisfiability. In Proceedings of the International Conference on Computer-Aided Design (ICCAD). 220--7.

Digital Library

[32]

Stephan, P., Brayton, R., and Sangiovanni-Vincentelli, A. 1996. Combinational test generation using satisfiability. IEEE Trans. Comput.-Aid. Des. Integ. Circ. Systems 15, 9, 1167--1176.

Digital Library

[33]

Tafertshofer, P., Ganz, A., and Henftling, M. 1997. A SAT-based implication engine for efficient ATPG, equivalence checking, and optimization of netlists. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design. 648--655.

Digital Library

[34]

Tarjan, R. 1974. Finding dominators in directed graphs. SIAM J. Comput. 3, 62--89.

Digital Library

[35]

Velev, M. 2004. Encoding global unobservability for efficient translation to SAT. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 197--204.

[36]

Zhaohui, F., Yinlei, Y., and Malik, S. 2005. Considering circuit observability don't cares in CNF satisfiability. In Proceedings of the Design, Automation and Test in Europe Conference (DATE). Vol. 2. 1108--1113.

Digital Library

Cited By

Lin PKhatri SLin PKhatri S(2013)ATPG for Cancer TherapyLogic Synthesis for Genetic Diseases10.1007/978-1-4614-9429-4_5(77-92)Online publication date: 1-Nov-2013
https://doi.org/10.1007/978-1-4614-9429-4_5
Lin PKhatri SGroeneveld PSciuto DHassoun S(2012)Application of logic synthesis to the understanding and cure of genetic diseasesProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228493(734-740)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228493

Index Terms

SAT-based ATPG using multilevel compatible don't-cares
1. Hardware
  1. Hardware test
  2. Robustness

Recommendations

Incremental solving techniques for SAT-based ATPG

Automatic test pattern generation (ATPG) based on the Boolean satisfiability (SAT) problem has recently been proven to be a beneficial complement to traditional methods. Efficient SAT techniques yield a robust fault classification. In this paper, we ...
On Acceleration of SAT-Based ATPG for Industrial Designs

Due to the rapidly growing size of integrated circuits, there is a need for new algorithms for automatic test pattern generation (ATPG). While classical algorithms reach their limit, there have been recent advances in algorithms to solve Boolean ...
Power and Delay Efficient Hardware Implementation with ATPG for Vedic Multiplier Using Urdhva Tiryagbhyam Sutra
IAIT '23: Proceedings of the 13th International Conference on Advances in Information Technology

In most implementations of digital circuitry, multiplication requires the highest latency and computational complexity. Vedic calculations are an ancient system of mathematics that involves mathematical computations to ascertain the multiplication in ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Design Automation of Electronic Systems

ACM Transactions on Design Automation of Electronic Systems Volume 13, Issue 2

April 2008

272 pages

ISSN:1084-4309

EISSN:1557-7309

DOI:10.1145/1344418

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 23 April 2008

Accepted: 01 July 2007

Revised: 01 March 2007

Received: 01 June 2003

Published in TODAES Volume 13, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
307
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lin PKhatri SLin PKhatri S(2013)ATPG for Cancer TherapyLogic Synthesis for Genetic Diseases10.1007/978-1-4614-9429-4_5(77-92)Online publication date: 1-Nov-2013
https://doi.org/10.1007/978-1-4614-9429-4_5
Lin PKhatri SGroeneveld PSciuto DHassoun S(2012)Application of logic synthesis to the understanding and cure of genetic diseasesProceedings of the 49th Annual Design Automation Conference10.1145/2228360.2228493(734-740)Online publication date: 3-Jun-2012
https://dl.acm.org/doi/10.1145/2228360.2228493

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents