Please wait a minute...
Tsinghua Science and Technology  2021, Vol. 26 Issue (1): 1-8    doi: 10.26599/TST.2019.9010046
Special Issue on Reliability and Security     
Efficient Static Compaction of Test Patterns Using Partial Maximum Satisfiability
Huisi Zhou, Dantong Ouyang, Liming Zhang*
∙ Huisi Zhou, Dantong Ouyang, and Liming Zhang are with the Laboratory of Symbol Computation and Knowledge Engineering, College of Computer Science and Technology, Jilin University, Changchun 130012, China. E-mail: 1285162366@qq.com; ouyangdantong@163.com;
Download: PDF (2480 KB)      HTML
Export: BibTeX | EndNote (RIS)      

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.



Key wordstest compaction      partial maximum satisfiability      Automatic Test Pattern Generation (ATPG)     
Received: 01 April 2019      Published: 01 July 2020
Corresponding Authors: Liming Zhang   
Cite this article:

Huisi Zhou, Dantong Ouyang, Liming Zhang. Efficient Static Compaction of Test Patterns Using Partial Maximum Satisfiability. Tsinghua Science and Technology, 2021, 26(1): 1-8.

URL:

http://tst.tsinghuajournals.com/10.26599/TST.2019.9010046     OR     http://tst.tsinghuajournals.com/Y2021/V26/I1/1

TestFault
f1𝒇2𝒇3𝒇4𝒇5𝒇6𝒇7𝒇8𝒇9𝒇10𝒇11𝒇12𝒇13𝒇14
𝒕110100110000101
𝒕201010000000001
𝒕310100010100001
𝒕400101001000010
𝒕500010101001010
𝒕600010101001010
𝒕700100000010010
Table 1 ISCAS-85 benchmark c17.
Fig. 1 Translation of faults.
Hard clauseSoft clause
WeightClauseWeightClause
81 3 01-1 0
82 01-2 0
81 3 4 7 01-3 0
82 5 6 01-4 0
84 01-5 0
81 5 6 01-6 0
81 3 01-7 0
84 5 6 0
83 0
87 0
85 6 0
81 0
84 5 6 7 0
81 2 3 0
Table 2 Clauses of faults and tests in c17.
CircuitNumber of faultsCircuitNumber of faults
c1714s2764
c43286s208221
c499146s298396
c880165s344464
c1355146s349448
c1908116s382538
c2670589s386352
c3540144s400535
c5315596s420502
c6288128s444517
c7552613s510604
b01177s526587
b02129s526n581
b03778s641565
b042346s713573
b051848s820723
b06275s832742
b071617s838994
b08628s11961327
b09664s12381374
b10672s14232081
b111991s14881423
b124324s14941429
b131299s53784283
b1416947s92343650
b1525834s132075930
s3593234600s158502643
Table 3 Circuit name and faults number.
CircuitVERSE-H+FOLDTetraMAX+SATComp
Initial length of test patternLength of compacted test patternReduction (%)Initial length of test patternLength of compacted test patternReduction (%)
b01---211433.33
b02---161225.00
b0365599.23463132.61
b041238630.08997722.22
b05---1209223.33
b06---201715.00
b07---937024.73
b08---675025.37
b0926522515.09443227.27
b101168725.00634626.98
b1133223628.9218114320.99
b12---21817022.02
b13---674434.33
Table 4 Results of SATComp for ITC99 benchmarks.
CircuitTetraMAX+SATCompTetraMAX-Comp+SATComp
Initial length of test patternLength of compacted test patternReduction (%)Initial length of test patternLength of compacted test patternReduction (%)
c177614.295420.00
c432261542.3115146.67
c499201050.00880.00
c880241441.6710910.00
c1355151033.338712.50
c190818950.008712.50
c2670463230.43191710.53
c3540301453.33171229.41
c5315391756.41990.00
c62887528.577528.57
c7552583244.8314140.00
Table 5 Results of SATComp for ISCAS85 benchmarks.
CircuitCHRON+FOLDVERSE-H+FOLDTetraMAX+SATCompTetraMAX-Comp+SATComp
Initial length of test patternLength of compacted test patternReduction (%)Initial length of test patternLength of compacted test patternReduction (%)Initial length of test patternLength of compacted test patternReduction (%)Initial length of test patternLength of compacted test patternReduction (%)
s27------11736.3610730.00
s208------322715.6326253.85
s29873721.3775698.00423028.5726253.85
s34439382.56453913.33372532.4321199.52
s349------332524.24191710.53
s382489--483--473329.7932299.38
s386------645218.75494312.24
s400------443422.7330286.67
s420------866919.7768671.47
s444------393120.5130286.67
s510------837213.2567661.49
s5267497342.008698037.59534220.7532306.25
s526n------523728.8531296.45
s641704930.00784937.18542848.1523224.35
s713------564323.2121204.76
s82030625117.9734025325.591037923.383768.43
s832------1158922.6183786.02
s838------18715716.041511463.31
s119621918117.3522718319.3822116326.241411279.93
s1238------22418019.641521398.55
s142348735028.1376833855.991238233.3347446.38
s148832825123.4842727036.7713810821.74102983.92
s1494------14011220.00101955.94
s537833719243.0348920857.4628522222.11100991.00
s9234------19313530.0572702.78
s13207------21816524.311481461.35
s15850------1189321.1994913.19
s359321219422.31---584718.9738372.63
Table 6 Results of SATComp for ISCAS89 benchmarks.
[1]   Hamzaoglu I. and Patel J. H., New techniques for deterministic test pattern generation, J. Electron. Test, vol. 15, nos. 1&2, pp. 63-73, 1999.
[2]   Pomeranz I., 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.
[3]   Roth J. P., Diagnosis of automata failures: A calculus and a method, IBM J. Res. Dev., vol. 10, no. 4, pp. 278-291, 1966.
[4]   Schulz M. H., Trischler E., and Sarfert T. M., 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.
[5]   Boon A. G., Kit C. C., Keng C. K., and Khian O. C., 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.
[6]   Bolchini C., Quintarelli E., Salice F., and Garza P., 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.
[7]   Dimopoulos M. and Linardis P., 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]   Pomeranz I., 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.
[9]   Pomeranz I., 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.
[10]   Li S. J., Liu W. M., and Wang S. S., Qualitative constraint satisfaction problems: An extended framework with landmarks, Artificial Intelligence., vol. 201, no. 4, pp. 32-58, 2013.
[11]   Cai D. B. and Yin M. H., On the utility of landmarks in SAT-based planning, Knowledge-Based Systems, vol. 36, pp. 146-154, 2012.
[12]   Gao J., Li R. Z., and Yin M. H., A randomized diversification strategy for solving satisfiability problem with long clauses, Science China Information Sciences, vol. 60, no. 9, pp. 121-131, 2017.
[13]   Drechsler R., Diepenbeck M., Eggersgl S., and Wille R., Passat 2.0: A multifunctional SAT-based testing framework, presented at the 14th Latin American Test Workshop-LATW, Cordoba, Argentina, 2013.
[14]   Eggersgl S., Krenz-Baath R., Glowatz A., Hapke F., and Drechsler R., 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.
[15]   Eggersgl S., Wille R., and Drechsler R., Improved SAT-based ATPG: More constraints, better compaction, in Proc. of International Conference on Computer-Aided Design, Hong Kong, China, 2013, pp. 85-90.
[16]   Eggersgl S., Yilmaz M., and Chakrabarty K., Robust timing-aware test generation using pseudo-boolean optimization, in Proc. of 21st Asian Test Symposium, Guam, USA, 2012, pp. 290-295.
[17]   Shi J. H., Fey G., Drechsler R., Glowatz A., Friedrich H., and Jurgen S., 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]   Stephan P., Brayton R. K., and Sangiovanni-Vincentelli A. L., Combinational test generation using satisfiability, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 15, no. 9, pp. 1167-1176, 1996.
[19]   Lei Z. D. and Cai S. W., 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.
[20]   Liu M., Ouyang D. T., Cai S. W., and Zhang L. M., Efficient zonal diagnosis with maximum satisfiability, Science China Information Sciences, vol. 61, no. 11, p. 112101, 2018.
[21]   Zhou H. S., Ouyang D. T., Liu M., Tian N. Y., and Zhang L. M., A PMS method combined with structure characteristics for diagnositic problem, (in Chineses), Scientia Sinica Informationis, vol. 49, no. 6, p. 685, 2019.
[22]   Bushnell M. and Agrawal V., Essentials of Electronic Testing for Digital, Memory and Mixed-signal VLSI Circuits. Berlin, Germany: Springer Science & Business Media, 2004.
[23]   Zhao W., Zhao L., Wu W. D., Chen S, G., Sun S. H., and Cao Y., Loading-balance relay-selective strategy based on stochastic dynamic program, Tsinghua Science & Technology, vol. 23, no. 4, pp. 127-134, 2018.
[24]   Brglez F., 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]   Brglez F., Bryan D., and Kozminski K., Combinational profiles of sequential benchmark circuits, IEEE Trans. on Circuits and Systems, vol. 3, pp. 1929-1934, 1989.
[26]   Corno F., Reorda M. S., and Squillero G., Rt-level itc?99 benchmarks and first ATPG results, IEEE Design & Test of Computers, vol. 17, no. 3, pp. 44-53, 2000.
No related articles found!