AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.4 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

Efficient Static Compaction of Test Patterns Using Partial Maximum Satisfiability

Laboratory of Symbol Computation and Knowledge Engineering, College of Computer Science and Technology, Jilin University, Changchun 130012, China.
Show Author Information

Abstract

Static compaction methods aim at finding unnecessary test patterns to reduce the size of the test set as a post-process of test generation. Techniques based on partial maximum satisfiability are often used to track many hard problems in various domains, including artificial intelligence, computational biology, data mining, and machine learning. We observe that part of the test patterns generated by the commercial Automatic Test Pattern Generation (ATPG) tool is redundant, and the relationship between test patterns and faults, as a significant information, can effectively induce the test patterns reduction process. Considering a test pattern can detect one or more faults, we map the problem of static test compaction to a partial maximum satisfiability problem. Experiments on ISCAS89, ISCAS85, and ITC99 benchmarks show that this approach can reduce the initial test set size generated by TetraMAX18 while maintaining fault coverage.

Keywords

test compactionpartial maximum satisfiabilityAutomatic Test Pattern Generation (ATPG)

References

[1]
I. Hamzaoglu and J. H. Patel, New techniques for deterministic test pattern generation, J. Electron. Test, vol. 15, nos. 1&2, pp. 63-73, 1999.
Google Scholar
[2]
I. Pomeranz, Balancing the numbers of detected faults for improved test set quality, IEEE Trans. Comput. Aided. Des. Integrated. Circ. Syst., vol. 35, no. 2, pp. 337-341, 2016.
Crossref Google Scholar
[3]
J. P. Roth, Diagnosis of automata failures: A calculus and a method, IBM J. Res. Dev., vol. 10, no. 4, pp. 278-291, 1966.
Crossref Google Scholar
[4]
M. H. Schulz, E. Trischler, and T. M. Sarfert, Socrates: A highly efficient automatic test pattern generation system, IEEE Trans. Comput. Aided. Des. Integrated. Circ. Syst., vol. 7, no. 1, pp. 126-137, 1988.
Crossref Google Scholar
[5]
A. G. Boon, C. C. Kit, C. K. Keng, and O. C. Khian, TetraMax diagnosis and laker software on failure analysis for ATPG/scan failures, in Proc. of 13th International Symposium on the Physical and Failure Analysis of Integrated Circuits, Singapore, 2006, pp. 217-221.
Crossref
[6]
C. Bolchini, E. Quintarelli, F. Salice, and P. Garza, A data mining approach to incremental adaptive functional diagnosis, in Proc. of 2013 IEEE International Symposium on Defect and Fault Tolerance in VLSI and Nanotechnology Systems, New York, NY, USA, 2013, pp. 13-18.
Crossref
[7]
M. Dimopoulos and P. Linardis, Efficient static compaction of test sequence sets through the application of set covering techniques, in Proc. of Design, Automation and Test in Europe Conference and Exhibition, Paris, France, 2004, pp. 194-199.
[8]
I. Pomeranz, Fold: Extreme static test compaction by folding of functional test sequences, ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 20, no. 4, p. 57, 2015.
Crossref Google Scholar
[9]
I. Pomeranz, Modeling a set of functional test sequences as a single sequence for test compaction, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 23, no. 11, pp. 2629-2638, 2014.
Crossref Google Scholar
[10]
S. J. Li, W. M. Liu, and S. S. Wang, Qualitative constraint satisfaction problems: An extended framework with landmarks, Artificial Intelligence., vol. 201, no. 4, pp. 32-58, 2013.
Crossref Google Scholar
[11]
D. B. Cai and M. H. Yin, On the utility of landmarks in SAT-based planning, Knowledge-Based Systems, vol. 36, pp. 146-154, 2012.
Crossref Google Scholar
[12]
J. Gao, R. Z. Li, and M. H. Yin, A randomized diversification strategy for solving satisfiability problem with long clauses, Science China Information Sciences, vol. 60, no. 9, pp. 121-131, 2017.
Crossref Google Scholar
[13]
R. Drechsler, M. Diepenbeck, S. Eggersgl, and R. Wille, Passat 2.0: A multifunctional SAT-based testing framework, presented at the 14th Latin American Test Workshop-LATW, Cordoba, Argentina, 2013.
Crossref
[14]
S. Eggersgl, R. Krenz-Baath, A. Glowatz, F. Hapke, and R. Drechsler, A new SAT-based ATPG for generating highly compacted test sets, in Proc. of IEEE 15th International Symposium on Design and Diagnostics of Electronic Circuits & Systems, Tallinn, Estonia, 2012, pp. 230-235.
Crossref
[15]
S. Eggersgl, R. Wille, and R. Drechsler, Improved SAT-based ATPG: More constraints, better compaction, in Proc. of International Conference on Computer-Aided Design, Hong Kong, China, 2013, pp. 85-90.
Crossref
[16]
S. Eggersgl, M. Yilmaz, and K. Chakrabarty, Robust timing-aware test generation using pseudo-boolean optimization, in Proc. of 21st Asian Test Symposium, Guam, USA, 2012, pp. 290-295.
Crossref
[17]
J. H. Shi, G. Fey, R. Drechsler, A. Glowatz, H. Friedrich, and S. Jurgen, Passat: Efficient SAT-based test pattern generation for industrial circuits, in Proc. of IEEE Computer Society Annual Symposium on VLSI: New Frontiers in VLSI Design, Tampa, FL, USA, 2005, pp. 212-217.
[18]
P. Stephan, R. K. Brayton, and A. L. Sangiovanni-Vincentelli, Combinational test generation using satisfiability, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 9, pp. 1167-1176, 1996.
Crossref Google Scholar
[19]
Z. D. Lei and S. W. Cai, Solving (weighted) partial MAX-SAT by dynamic local search for SAT, in Proc. 27th International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2018, pp. 1346-1352.
Crossref
[20]
M. Liu, D. T. Ouyang, S. W. Cai, and L. M. Zhang, Efficient zonal diagnosis with maximum satisfiability, Science China Information Sciences, vol. 61, no. 11, p. 112101, 2018.
Crossref Google Scholar
[21]
H. S. Zhou, D. T. Ouyang, M. Liu, N. Y. Tian, and L. M. Zhang, A PMS method combined with structure characteristics for diagnositic problem, (in Chineses), Scientia Sinica Informationis, vol. 49, no. 6, p. 685, 2019.
Crossref Google Scholar
[22]
M. Bushnell and V. Agrawal, Essentials of Electronic Testing for Digital, Memory and Mixed-signal VLSI Circuits. Berlin, Germany: Springer Science & Business Media, 2004.
[23]
W. Zhao, L. Zhao, W. D. Wu, S, G. Chen, S. H. Sun, and Y. Cao, Loading-balance relay-selective strategy based on stochastic dynamic program, Tsinghua Science & Technology, vol. 23, no. 4, pp. 127-134, 2018.
Crossref Google Scholar
[24]
F. Brglez, A neutral netlist of 10 combinatorial benchmark circuits and a target translator in fortran, in Proc. of 1985 IEEE Int. Symp. on Circuits and Systems, Special Session on Recent Algorithms for Gate-Level ATPG with Fault Simulation and Their Performance Assessment, Kyoto, Japan, 1985, pp. 663-698.
[25]
F. Brglez, D. Bryan, and K. Kozminski, Combinational profiles of sequential benchmark circuits, IEEE Trans. on Circuits and Systems, vol. 3, pp. 1929-1934, 1989.
Google Scholar
[26]
F. Corno, M. S. Reorda, and G. Squillero, Rt-level itc?99 benchmarks and first ATPG results, IEEE Design & Test of Computers, vol. 17, no. 3, pp. 44-53, 2000.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 26 Issue 1,
February 2021
Pages 1-8
DOI: 10.26599/TST.2019.9010046
Cite this article:
Zhou H, Ouyang D, Zhang L. Efficient Static Compaction of Test Patterns Using Partial Maximum Satisfiability. Tsinghua Science and Technology, 2021, 26(1): 1-8. https://doi.org/10.26599/TST.2019.9010046

770

Views

58

Downloads

2

Crossref

N/A

Web of Science

2

Scopus

0

CSCD

Altmetrics
Received: 01 April 2019
Revised: 19 August 2019
Accepted: 28 August 2019
Published: 19 June 2020
© The author(s) 2021.

The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
Return