On Combining Pinpoint Test Set Relaxation and Run-Length Codes for Reducing Test Data Volum

2020-08-04 来源：客趣旅游网

On Combining Pinpoint Test Set Relaxation and Run-Length Codes

for Reducing Test Data Volume*

Seiji Kajihara Yasumi Doi

Dept. of Computer Sciences and Electronics

Kyushu Institute of Technology

Abstract

This paper presents a pinpoint test set relaxation methodfor test compression that maximally derives the capabilityof a run-length encoding technique such as Golomb cod-ing or frequency-directed run-length (FDR) coding. Be-fore encoding a given set of test patterns, we selectivelyrelax some specified bits of the test patterns. By changinga specified bit with value 1 to a don't-care, two consecu-tive runs of 0s in the test sequence can be concatenatedinto a longer run of 0, thereby facilitating run-length cod-ing. This procedure retains the fault coverage of the testset. Since the increase in compression depends on thelengths of the two runs that are concatenated with eachbit relaxation, a lookup table, referred to as the gain table,is pre-computed and used during the test set relaxationprocedure to maximize the likelihood of increasing theamount of test data compression. The gain table is used topinpoint the bit positions with value 1, which when re-laxed to don't-cares, will yield the most compression. Inthis way, the given test pattern set is appropriately modi-fied as a preprocessing step before test compression. Ex-perimental results for the ISCAS benchmark circuits showthat the proposed method can be used to increase the ef-fectiveness of run-length coding methods for test data com-pression.

1. Introduction

Test cost is a major component of the manufacturingcost for system-on-chip (SOC) integrated circuits. In par-ticular, test data volume is a major contributor to SOC testcost. Large test data volumes lead to an increase in testingtime and the need for multiple ATE channel reloads, eitherfrom workstations across a network or from slow hard disks.As a result, a number of techniques have recently beenpresented in the literature to reduce test data volume, and

*The work of S. Kajihara was supported in part by Monbu KagakushoGrants-in-Aid for Scientific Research 14780228. The work of L. Liand K. Chakrabarty was supported by the National Science Founda-tion under grants CCR-9875324 and CCR-0204077, and by a graduatefellowship from the Design Automation Conference.

Lei Li Krishnendu ChakrabartyDept. of Electrical and Computer Engineering

Duke University

thereby reduce test cost [1-15]. One such technique is testcompaction, which relies on ATPG techniques to generate asmall test set with maximum fault coverage [1, 2, 3]. Tech-niques to generate test sets with a close-to-minimum num-ber of patterns have been developed for full-scan sequen-tial circuits [2, 3]. For scan-based circuits however, test com-paction alone does not provide sufficient reduction in testdata volume if the number of scan flip-flops is very large,since test data volume is proportional not only to the num-ber of test vectors but also to the number of scan flip-flops.Recently, a number of methods have been proposed forreducing test data volume using compression methods. Thekey idea here is to compress test data using one of severaltechniques and use a small amount of embedded hardwarefor on-chip decompression. Test compression methods canbe classified in terms of the type of embedded hardwareemployed for test delivery. For example, when the decom-pression hardware is based on an LFSR, reseeding is one ofthe efficient test compression methods [4 , 5, 6]. There alsoexist several methods for compressing test data by encod-ing test sets using statistical and run-length encoding [7-11]. The decompression hardware for these methods con-sists of a sequential circuit implementing a finite state ma-chine. Test compression methods that use a combinationalcircuit as a decompressor have also been proposed in theliterature [12, 13]. Finally, a number of methods using anembedded processor for software-based decompressionhave been proposed, e.g. [20].

Test compression is sometimes based on test patternsgenerated by ATPG. It is known that unspecified values ofthe test patterns are very useful to derive higher compres-sion ratio. On the other hand, test generation with leavingunspecified values cannot make the size of the test set besmaller because compaction using reverse order fault simu-lation [16] or double detection [2] might be useless for theunspecified test patterns. Although high compression ratiocan be obtained from a larger test set in general, the result-ing test data volume from the large test set may still belarger than that from a compacted test set for the same cir-cuit. Thus if we can compress a highly compacted test setefficiently, test data volume can be reduced.

When a highly compacted test set is generated in whichevery bit of test patterns is specified as either to 0 or 1, thereexist values in the test set that can be changed to the oppo-site logic values without losing fault coverage. One canregards such input values as don’t-care (X). A method, calledmaximal compaction, was developed for identifying an X ina test pattern for a fault [1]. A method for identifying the Xsin the entire test set was proposed in [17]. Since there aremany combinations of X inputs in general, the method findsone including as many X inputs as possible. It is reportedthat, even for a highly compacted test set for ISCAS bench-mark circuits, approximately half of values are Xs. Since wecan treat the Xs of test patterns as well as unspecified val-ues, we can utilize the Xs for test compression.

In this paper, we present a test modification method fortest compression that maximally derives the capability of arun-length based encoding such as Golomb encoding orFDR encoding. Before encoding given test patterns, we ef-ficiently change values of some bits of the test patternsusing a technique of don’t-care identification [18]. This pro-cedure retains the fault coverage of the test set. The bitvalues to be changed are selected so that two runs in thetest patterns are concatenated into one longer run. Since again with each concatenation is different depending on therun-length of prefix and tail for the changed bit, we prepareand refer a gain table that gives the number of bits reducedby encoding after concatenation of two runs. According tothe gain table, we pinpoint bit positions that produce largergain for test modification, and apply the don’t-care identifi-cation such that Xs on the bits are found maximally. Theprocedure of test modification is iteratively applied to thetest patterns. As a result, the given test patterns are modi-fied optimally for test compression. Experimental results forISCAS benchmark circuits show that the proposed methodcan compress test sets efficiently.

This paper is organized as follows. In Section 2, we ex-plain techniques used in the proposed method. In Section3, we explain the proposed method. In Section 4, we presentexperimental results for ISCAS benchmark circuits and fi-nally conclude this paper in Section 5.

2. Preliminaries

In this section, we explain techniques used in our work.2.1 Run-length based encoding

As methods for encoding test patterns, FDR (FrequencyDirected Run-length) encoding [8] and Golomb encoding[7] is well-known. These methods compress test data byencoding successive 0s in the test patterns with a codeword.In this paper, each set of test patterns before and after en-coding are denoted by TD and TTable 1(a) and Table 1(b) show an example of code as-E, respectively.

signments with FDR coding and Golomb coding with group

Table 1 Example of codeword assignment

(a) FDR codingGrouprun-length

PrefixTailCodeword

A1000001101 A2210001000301100141010105111011 A3611000011000070011100018010110010901111001110100110100111011101011211011011013

111

110111(b) Golomb coding

Grouprun-length

PrefixTailCodeword A1

00000101001210010311011 A2410001000501100161010107111011 A38110

00110009011100110101101011

11011

t1:00100tTD:001001010100011t2:101013:00011

TE:100010000101100100

(a) Given tests(b) Test stream

Fig. 1 Example of FDR coding

m1:xffxft:x0100mt1’2:ffxxfm2’:101x13:xffxxt3’:000x1

(a) A mask set (b) Tests with Xs

Fig. 2 Don’t care identification

size 4, respectively. When a test set in Fig. 1(a) is a given,it is compressed with the FDR encoding as shown in Fig.1(b). Note that we treat test patterns in the given test set asone stream by concatenating all the test patterns in serial.The run-length based encoding produces shortercodes, when there are more 0s in the test patterns and thelength of each run is longer. Therefore the more unspeci-fied values the test set includes, the lesser the test data

volume is potentially.

2.2 Don’t-care identification

Test patterns of a test set generated do not have un-specified values generally because they are specified byrandom fill or static/dynamic test compaction [19] for thedetection of faults other than the target fault. However, someprimary input values may be changed to opposite logic val-ues without losing fault coverage. One can regard such in-put values as don’t-cares (Xs). A method for identifying Xsof a generated test set has been proposed in [17]. The methodin [17] determines as many Xs as possible in the test pat-terns of the given test set.

To Xs identified, logic values can be reassigned for thepurpose of reducing test data volume. If a reassigned valueis the same as the original value, the X is meaningless. Gen-erally the test set with Xs is not uniquely determined, andthere are many possible combinations of bit position of theXs. Desired bit position of the Xs depends on the purposeof the reassignments to the Xs, while the Xs are typicallyused for test compaction/compression or test power reduc-tion. If it is known that some bits do not have to be changedto Xs, Xs on the other bits can be increased.

A method for placing the Xs on a maximal number ofspecific bits of a test set has been proposed in [18]. Themethod allows a user to specify bits for the placement of Xsfor each one of the given test vectors. The specific set ofbits that should be maximally changed to Xs is specifiedusing a pattern set given together with the given test set.We call the pattern set a mask pattern set, and in short amask set. Each mask pattern is associated with a test pat-tern. An example of a mask set for test set T in Fig. 1(a) isshown in Fig. 2(a) where ‘x’ means a bit to be changed to anX, and ‘f’ means a fixed bit, i.e., an X on the bit is not needed.An example of a possible test set is shown in Fig. 2(b).

3. Proposed method

3.1 Motivation

It can be easily imagined that the X identification tech-nique is suitable for test compression of the given test pat-terns. Especially, when we can specify bit positions to bechanged to an X, the test patterns would be modified so asto derive the effect of test compression maximally. For therun-length encoding, since we need more 0s in the test set,we should prepare a mask set such that bit positions with 1in the given test set are set to ‘x’, and the others are set to‘f’.

Suppose that the test set in Fig. 1(a) is compressed. Themask set for the test set would be prepared as shown in Fig.3(a). For the original test stream TDsible streams, TD0, we consider two pos-tained from possible test sets with Xs. When we compress

mTDm1:ffxff2:xfxfxTD0:001001010100011:00x0010101000x1mTD13:fffxx2:0010010x01000x1

(a) A mask set(b) Test stream

Fig. 3 Example of FDR coding

TETE0:1000100001011001001:101101011010

TE2:1000100010011010

Fig. 4 Compressed test streams

after assigning 0 to Xs

TDtest data 1 with FDR encoding according to Table 1(a), compressedTE1 as shown in Fig. 4 is obtained because byassigning value 0 on the Xs in TE1. The gain obtained bymodifyingTD0 to TDTE1, which is calculated by |TE0| - |TE1|, is4 bits, where |i| means the number of bits of TETDi. On theother hand, from 2,TE2 is obtained and no gain is ob-tained by the modification. Although the number of Xs inTD1 and TD2 is the same, the gains are different. It is ob-served that there is a bit in the original test set that pro-duces larger gain by changing it to an X, while there is a bitin the original test set that does not produce large gain bychanging it to an X.

3.2 Gain table

By changing a bit value, two runs in the test patterns areconcatenated into one longer run. As shown in the aboveexample, a gain with each concatenation is different depend-ing on the run-length of 0s in prefix and tail for the changedbit. In the case of TDconcatenated with another run with length 2. As a result, a1 in Fig. 3(b), a run with length 2 wasrun with length 5 was created by assigning 0 to the X. Fromthe codeword in Table 1(a), since both codes of the run withlength 2 and the run with length 5 consist of 4 bits, the gainby changing the bit was 4 bits. On the other hand, in thecase of TDenated. But no gain was obtained because two runs with2 in Fig. 3(b), two runs with length 1 were concat-length 1 make a 2-bit code twice and the concatenated runwith length 3 makes a 4-bit code.

Based on the table for code assignments in Table 1, wecan compute the gain for each bit whose value is 1 in thegiven test streams when the bit value is changed to 0. Thegain is independent of generation of the test set and justcomputed from the prefix run-length and the tail run-lengthfor the bit with value 1 statically. Hence we prepare and refera 2-dimensional table that gives the number of bits reducedby encoding after concatenation of two runs. We call it again table. The gain table for FDR coding is given in Table.2. The line number and the column number indicate the

Table 2 Gain table for FDR coding

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 02 0 2 2 2 0 2 2 2 2 2 2 2 0 2 210 0 2 2 0 0 2 2 2 2 2 2 0 0 2 222 2 4 2 2 2 4 4 4 4 4 2 2 2 4 432 2 2 2 2 2 4 4 4 4 2 2 2 2 4 442 0 2 2 2 2 4 4 4 2 2 2 2 2 4 450 0 2 2 2 2 4 4 2 2 2 2 2 2 4 462 2 4 4 4 4 6 4 4 4 4 4 4 4 6 672 2 4 4 4 4 4 4 4 4 4 4 4 4 6 682 2 4 4 4 2 4 4 4 4 4 4 4 4 6 692 2 4 4 2 2 4 4 4 4 4 4 4 4 6 6102 2 4 2 2 2 4 4 4 4 4 4 4 4 6 6112 2 2 2 2 2 4 4 4 4 4 4 4 4 6 6122 0 2 2 2 2 4 4 4 4 4 4 4 4 6 6130 0 2 2 2 2 4 4 4 4 4 4 4 4 6 6142 2 4 4 4 4 6 6 6 6 6 6 6 6 8 6152 2 4 4 4 4 6 6 6 6 6 6 6 6 6 6 length of the prefix bit and the tail bit, respectively. Whencreating a mask set, according to the gain table we pinpointbit positions with large gain. Thus we can modify the giventest patterns so as to be compressed maximally.

3.3 Pinpoint bit modification

In order to avoid identifying Xs on bits with small gain,we define a threshold of gain, geach bit with value 1 according to the gain table and createmin. We check the gain ofa mask set so that if the gain of a bit is grater than or equaltogmin, then put ‘x’ on the bit, otherwise put ‘f’. We initiallysetgmin to 8, and we iterate a procedure to identify Xs and toassign 1 to the X as long as Xs are found. If the test setcannot be modified for the given, we decrease gmin and con-tinue the procedure.

We give an outline of the procedure below.Step 0: Set a given test set to T, and set gStep 1: From test set T and the gain table, create a mask setmin to 8.

such that bits whose gain is grater than or equal to gare set to ‘x’, and the other bits are set to ‘f’.

minStep 2: identify Xs on bits in T specified by the mask set.Step 3: For each X identified, if the gain by assigning 0 tothe X is still greater than or equal to gT’min, assign 0 to theX. Otherwise, reassign 1 to the X. Let be the resultingtest set.

Step 4: If T = T’, then set gStep 5: Set T’ to T, and go to Step 1.

min to gmin– 2. If gmin< 0, then stop.Although the don’t-care identification is performedbased on the test set and the mask set, we don’t assign 0not to all Xs found. This is because, after a value of a bit

TDgain0:001001010100011:004002000200022mask set_0:ffxffffffffffffTD0’:00X001010100011TDgain1:000001010100011:000000000200022mask set_1:fffffffffxfffxx

TD1’:000001010X000X1TD2:000001010000011gain:000000000000002

..............................

Fig.5 An example of pinpoint test relaxation

was changed to 0, the gains on the adjacent bit with “1”may vary. The gain by two bit change is not equal to thesum of the gains by individual bit change. This procedure isbased on a greedy algorithm in order to save computingtime, i.e., we try to change the bits with larger gain obtainedwith individual bit change. Hence the optimum solution onthe modified test patterns is not guaranteed.

In Fig. 5 we illustrate an example of the procedure.Example:We assume that a test set TD0is given. The gainof each bit is calculated as shown in the second line. Asthere is no bit whose gain is greater than 4, we start explana-tion from the case of gmin =4. The mask set for TDmask set_0. Suppose that a test set TD’ is obtained from0is createdinTD0TD0andmask set_0.Then, value 0 is assigned to the X in0’, and resultant test set becomes TDTD1. Depending on thegain of each bit in We suppose that two Xs in 1,mask set_1 iscreated, where gTDmin =2.TD’. While we assign 0 to the left X, we don’t assign 0 to1 are identified as shown inthe right X because the gain is reduced to 0 that is less than1gstill continue after obtaining min after the assignment to the left X. The procedure wouldTD2, until the test set cannotbe modified. We omit the explanation here.

4. Experimental results

We implemented the proposed method on a PC(PentiumIII 1.80GHz, 256MB) using C programming lan-guage, and applied it for fully scanned ISCAS’89 bench-mark circuits. As the initial test sets, we prepared highlycompacted test sets [2], and used a 200x200 matrix as thegain tables. Table 3 shows experimental results for FDR cod-ing and Golomb coding with m=4. The second column andthe third column list the number of test patterns in each testset and the number of bits in each test pattern to be com-pressed. We refer to volume of the original test data as TD,and volume of the compressed test data as TE. The col-umns headed “FDR” and “Golomb” present the number of

bits compressed with FDR coding and Golomb coding, re-spectively. Although the proposed method is available forGolomb coding, it brings better results for FDR coding.We analyzed the procedure and data compressed withFDR coding. Table 4 presents some data for discussion.The columns headed “#1s” and “#1to0s” gives the numberof bits whose value is 1 in the original test set, and thenumber of bits whose value is changed from 1 to 0 by theproposed method. The following five columns present thenumber of iterations for each gmin in the procedure. The lastcolumn gives run time. The proposed method could changesapproximately 75% of 1s of the given test set to 0. As themost of the changes were done in gmin=2, we would con-sider additional criterion for pinpointing bits in gmin=2 as afuture work. While the iterations of the procedure were more

Table 3 Compression results with FDR coding and

Golomb coding(m=4)circuits5378s9234s13207s15850s35932s38417s38584

#tests#inputs100111235971287114

214247700611176316641464

TD[bits]21400274171645005926721156144768166896

FDR[bits]10490154542284018466180726407859262

Golomb[bits]12454180965289026077266097771174991

than twenty times, it was done still in practical computingtime.

Table 5 gives comparisons of the proposed method withothers. The column of “nonpinpoint” shows the results with-out using the gain table, i.e., the procedure tries to changeall 1s in the test set to 0s without notice. The followingcolumns gives results of EFDR coding [9], variable-lengthHuffman coding [14], RESPIN++ [15], and XOR network [12].For many circuits, the proposed method showed the high-est performance on compression. For s35932, however, ourmethod could not work very well, because the number ofbits with value 1 in the test set was greater than that withvalue 0. For such a circuit, we should change value 0 to 1 in

the test set, and compress it based on the runs with 1.

5. Conclusion

In this paper, we presented a test modification methodfor test compression that maximally derives the capabilityof a run-length based encoding such as FDR encoding.Before encoding given test patterns, we changed values ofsome bits of the test patterns using the technique of don’t-care identification that retains the fault coverage of the testset in any way. The bit values to be changed were selectedsuch that two runs in the test patterns are concatenatedinto one longer run. In order to maximize the gain obtainedby the concatenation, we prepared and referred a gain tablethat gives the number of bits reduced by encoding after

Table 4 Detailed Results for FDR coding

circuits5378s9234s13207s15850s35932s38417s38584

#1s[bits]11333151547214128748134579469567733

#1to0s[bits]848910727675552421255957814754357

gmin=8

1131212

#iterations

gmin=6gmin=4gmin=2gmin=0

2242223

3444346

291713349177742

3444784

time[sec]3190118441250122541216

Table 5 Comparisson of compression results

cirucits5378s9234s13207s15850s35932s38417s38584

ours10490154542284018466180726407859262

nonpinpoint10572158462473619906175506602061960

EFDR[9]1141921250299922464355546496273853

VIHC[14]1151617736277373027194587493885674

RESPIN++XORnet[15][12]17332171982600432226N/A8913263232

concatenation of two runs. Then, we pinpointed bit posi-tions, and apply the don’t-care identification. The proce-dure of test modification was iteratively applied to the testpatterns. Experimental results for ISCAS benchmark circuitsshowed that the proposed method could compress test setsefficiently.Reference

[1] I. Pomeranz, L. N. Reddy and S. M. Reddy, “COMPACTEST:

A Method to Generate Compact test Sets for CombinationalCircuits,” IEEE Trans. CAD, pp. 1040-1049, Jul. 1993.[2] S. Kajihara, I. Pomeranz, K. Kinoshita and S. M. Reddy,

“Cost-Effective Generation of Minimal Test Sets for Stuck-at Faults in Combinational Logic Circuits,” IEEE Trans. CAD,pp.1496-1504, Dec. 1995.

[3] I. Hamzaoglu and J. H. Patel, “Test Set Compaction Algo-rithms for Combinational Circuits,” Proc. Int’l Test Conf, pp.283-289, Oct. 1998[4] S. Hellebrand, J. Rajski, S. Tarnick, S. Venkataraman and B.

Courtois, “Built-in Test for Circuits with Scan Based on Re-seeding of Multiple-polynomial Linear Feedback Shift Regis-ters,” IEEE Trans. Comp., pp. 223-233, Feb. 1995.[5] S. Hellebrand, H.-G. Liang, H. -J. Wunderlich, “A mixed-mode

BIST scheme based on reseeding of folding counters,” Int’lTest Conf., pp.778-784, Oct. 2000.

[6] C. V. Krishna, A. Jas, and N. A. Touba, “Test Vector Encoding

Using Partial LFSR Reseeding,” International Test Conf., pp.885-893, Oct. 2001.

[7] A. Chandra and K. Chakrabarty, “Test Data Compression for

System-on-a-Chip Using Golomb Codes,” VLSI Test Sym-posium, pp. 113-120, April 2000.[8] A. Chandra and K. Chakrabarty, “Frequency-directed Run-length (FDR) Codes with Application to System-on-a-chipTest Data Compression,” Proc. VLSI Test Symp., pp. 42-47,April 2001.[9] A. El-Maleh, R. Al-Abaji, “Extended Frequency-directed Run-length Codes with Improved Application to System-on-a-Chip Test Data Compression,” Int’l Conf. Electronics, Cir-cuits and Systems, pp. 449-452, 2002.

[10] A. Jas, J. Ghosh-Dastidar, and N. A. Tuba, “Scan Vector

Compression/Decompression Using Statistical Coding,” VLSITest Symposium, pp. 114-120, April 1999.

[11] H. Ichihara, K. Kinoshita, I. Pomeranz, S. M. Reddy, “TestTransformation to Improve Compaction by Statistical En-coding,” International Conf. on VLSI Design, pp.294-299,Jan. 2000.

[12] I. Bayraktaroglu and A. Orailoglu, “Test Volume and Appli-cation Time Reduction Through Scan Chain Concealment,”Design Automation Conference, pp.151-155, June 2001.[13] S. M. Reddy, K. Miyase, S. Kajihara and I. Pomeranz, “On

Test Data Volume Reduction for Multiple Scan Chain De-signs,” VLSI Test Symposium, pp. 103-108, April 2002.[14] P. T. Gonciari, B. Al-Hashimi, N. Nicolici, “Improving com-pression ratio, area overhead, and test application time forsystem-on-a-chip test data compression/decompression,”Design Automation and Test in Europe Conf., pp. 604-611,2002.

[15] L. Schafer, R. Dorsch, H. -J. Wunderlich, “RESPIN++ -Deterministic Embedded Test,” European Test Workshop,pp.37-44, May 2002.

[16] M. Schulz, E. Trischler, and T. Sarfert, “SOCRATES: A

Highly Efficient Automatic Test Pattern Generation Sys-tem,” IEEE Trans. on CAD., pp. 126-137, Jan. 1988.[17] S. Kajihara, and K. Miyase, “On Identifying Don’t Care

Inputs of Test Patterns for Combinational Circuits,” Proc.Int’l Conf. on Computer Aided Design, pp. 364-369, Nov.2001.

[18] K. Miyase, S. Kajihara, I. Pomeranz and S. M. Reddy,“Don’t care identification on specific bits of test patterns,”2002 International Conference on Computer Design, pp. 194-199, Sep. 2002.

[19] P. Goel, and B. C. Rosales, “Test Generation and DynamicCompaction of Tests,” Digest of Papers 1979 Test Conf.,pp. 189-192, Oct. 1979.

[20] A. Jas and N. A. Touba, “Using an embedded processor for

efficient deterministic testing of system-on-achip,” Int.’l

Conf. on Computer Design, pp.418-423, 1999.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

全部栏目

On Combining Pinpoint Test Set Relaxation and Run-Length Codes for Reducing Test Data Volum