JOURNAL OF ELECTRONIC TESTING: Theory and Applications 21, 613–620, 2005 c 2005 Springer Science + Business Media, Inc. Manufactured in The United States.
Reducing Scan Shifts Using Configurations of Compatible and Folding Scan Trees H. YOTSUYANAGI Faculty of Engineering, The University of Tokushima
[email protected]
T. KUCHII AND S. NISHIKAWA Sharp Corporation
[email protected] [email protected]
M. HASHIZUME Faculty of Engineering, The University of Tokushima
[email protected]
K. KINOSHITA Faculty of Informatics, Osaka Gakuin University
[email protected]
Received March 1, 2004; Revised June 1, 2005 Editor: V. Agrawal
Abstract. In this paper, a new method for reducing scan shifts is presented. Scan design is one of the most popular designs for test method for sequential circuits. However, for circuits with many flip-flops, it requires a long test application time and high test-data volume. Our new scan method utilizes two configurations of scan chains, a folding scan tree and a fully compatible scan tree to alleviate these problems. It is observed that uncompacted test patterns typically contain a large fraction of don’t care values. This property is exploited in the fully compatible scan tree to reduce scan shifts without degrading fault coverage. Then, a folding scan tree is configured to further reduce the length of scan chain and scan shifts. Experimental results on benchmark circuits show that this scan method can significantly reduce scan shifts. Keywords: scan tree, design for testability, logic testing, sequential circuit
1.
Introduction
Scan design is known to be effective to derive high fault coverage for sequential circuits using conventional combinational test pattern generation methods.
Since scan design with a single scan chain costs much test application time for circuits with a lot of flipflops, several methods have been proposed that utilize multiple scan chains to reduce test application time [1–4, 7–9]. To reduce scan input patterns, scan
614
Yotsuyanagi et al.
pattern is provided to several scan chains through the same scan input [2–4, 8, 9] or through a decompressor circuit [7]. In [2, 9], the input reduction technique was proposed that identifies pairs of compatible inputs and connects them to reduce test signals. In [3], the parallel serial full scan technique was proposed for the full scan embedded cores. Scan chains are divided into multiple partitions and the same vector are shifted into each partition. In [8], segments of scan chains are dynamically selected or skipped to reduce the test application time. In [1], the double-tree scan structure was proposed for reducing the scan shifts and the power consumption during scan testing. In [4], the tree-structured LFSR was proposed for configuring BIST to generate all possible input patterns for each output cone. The scan tree is proposed as the one of the configurations of multiple scan chains that provide the same patterns for some part of scan chains [6, 9]. Xiang et. al. [10] proposed a scan forest construction that connects several scan trees to primary inputs. Using tree-like structure for scan chains, a scan tree can be configured without degrading the fault coverage obtained for a full scan circuit [6]. In this paper, we propose a new method to reduce scan shifts using two scan trees. One is a fully compatible scan tree that is configured based on a full scan test pattern to reduce scan shifts without degrading fault coverage. The other is a folding scan tree that is configured based on a fully compatible scan tree to reduce much scan shifts by reducing the length of scan chains. In our scan method, uncompacted test patterns are utilized to configure these scan trees. The test patterns are provided by a folding scan tree first to detect easy-todetect faults, and then are provided by a fully compatible scan tree to detect the rest of faults. Along with the two configurations of the scan trees, the method to modify scan trees is proposed for the case that the observation of the scan tree is restricted by one scanout terminal without using MISR. In this paper, scan trees are configured without the circuit layout. However the constraints caused by the circuit layout should be included in the proposed method if it is given. This paper is organized as follows. In Section 2, scan tree configuration and its test application time are described. Section 3 shows a main idea and the procedures of scan shift reduction method using fully compatible scan tree and folding scan tree configurations. The modification of scan trees for considering scan out operation is also proposed in Section 3. Section 4 shows the experimental results for benchmark circuits and Section 5 concludes the paper.
Fig. 1.
2.
Scan tree.
Scan Tree
Scan design is one of most popular design for testability technique used for sequential circuits. While the input of flip-flops is connected from the combinational part in the normal operation, it is connected from the other scan flip-flop in the test mode in order to controlling and to observing the values of flip-flops. Test application time of scan design is estimated by (len + 1) × vec + len, where len is the length of a scan chain and vec is the number of test vectors. Since test application time mostly depends on the length of a scan chain, multiple scan chains are used to reduce the length of scan chains. To reduce test application time and test data, some methods have been proposed that share some inputs of scan chains and provides the same scan data to these scan chains. In [4], a scan tree was used to configure LFSR in BIST circuit. Scan tree is proposed as one of the configurations of multiple scan chains [6, 9, 10]. An example of a scan tree is shown in Fig. 1. For simplicity, scan chains are illustrated in this paper as the connection among the flip-flops only in the test mode. The scan tree consists of three scan chains. Flipflops in the parallel part have one or more flip-flops that are always assigned the same values in the test mode. In this example, the sets of flip-flops (5, 8), (6, 9, 11) and (7, 10, 12) are always assigned the same values. The output of scan chains is selected by a MUX in our experiments to be able to observe each value of flip-flops if required for fault diagnosis. However, the method can be applied for the case that all leaf scan flip-flops observable and for the case that the MISR is utilized for observing the values of flip-flops. If it is possible to arrange flip-flops in parallel without degrading fault coverage, the test data and test application time can be reduced using a scan tree. In this example, while a single scan chain requires twelve clock cycles per a test vector to shift scan input values to all twelve flip-flops, seven cycles per a test vector are enough to shift scan input values in the scan tree.
Reducing Scan Shifts Using Configurations of Compatible and Folding Scan Trees
3.
Configurations of Scan Trees to Reduce Scan Shifts
In this section, we propose two types of configurations of scan trees to reduce scan shifts. To provide the given scan pattern with shorter scan chains, a scan tree called fully compatible scan tree is configured. Along with a fully compatible scan tree, a folding scan tree that has scan chains with shorter length is also proposed. 3.1.
Fully Compatible Scan Tree Configuration
To obtain a scan tree configuration without degrading fault coverage, the compatible set of flip-flops are calculated for a test pattern obtained by a combinational test pattern generation for full scan circuits. Two flip-flops FF a and FF b are said to be compatible for a given test pattern T if they are assigned the same values or at least one of the flip-flops has don’t care for each vector in T [3]. A compatible set of flip-flops is a set of flip-flops in which any pair of flip-flops are compatible. We define a fully compatible scan tree as a scan tree such that all sets of flip-flops placed in parallel are compatible sets. Compatible sets of flip-flops are calculated using a compatible graph. The compatible graph is a graph that shows the compatibility of flipflops. Vertices of the graph correspond to flip-flops, and an edge between two vertices represents the compatibility of the flip-flops. The compatible sets of flipflops are obtained by finding disjoint cliques in the graph. There may exist flip-flops that has no compatible flipflops or does not included in any compatible sets. In a fully compatible scan tree, such flip-flops are placed in series and connected to a scan input. Then flip-flops included in compatible sets are connected in parallel to a scan tree. The procedure to configure a fully compatible scan tree and to modify a given test pattern for the scan tree is summarized as follows.
3. Remove the nodes and all edges corresponding to the clique. 4. Repeat step 2 and 3 until no cliques found. 5. Configure a scan tree such that: (a) The FFs in compatible sets C j with smaller size are placed near the scan-in terminal. (b) All FFs in the same C j are placed in parallel. 6. Modify test pattern T such that all FFs in the same compatible set have the same value. 7. Turn the don’t care values in the test pattern into {0, 1} randomly. 8. Apply fault simulation with the modified test pattern to the circuit in the scan tree configuration, and remove unnecessary vectors. While the method in [3] requires some faults to be detected by serial test mode that uses a single full scan, our method can detect all detectable faults by the obtained scan tree. 3.2.
Folding Scan Tree Configuration
As shown in Section 3.1, the length of scan chains can be reduced using a scan tree. However, for some circuits, many flip-flops remain in the non-parallel part. In such cases, the reduction of scan shift is not effective. To reduce more scan shifts, a folding scan tree is proposed and is utilized along with a fully compatible scan tree. In a folding scan tree, the non-parallel part of a fully compatible scan tree is forced into the parallel part as shown in Fig. 2. The length of scan chain is reduced to the length of the parallel part of a fully compatible scan tree. It is effective to reduce scan shift when the non-parallel part of a fully compatible scan tree includes many flip-flops. Since the flip-flops in the non-parallel part are not compatible with the flip-flops in the parallel part, the folding scan tree configuration does not assure to provide all scan pattern obtained for the full scan circuit.
Procedure 1: configuration of a fully compatible scan tree and its scan pattern 1. Calculate the compatibility of each pair of FFs and make the compatibility graph. 2. Select the unprocessed flip-flop FF j with the maximum number of the compatible FFs and find a clique C j that contains FF j .
615
Fig. 2. Fig. 1.
An example of a folding scan tree of
616
Yotsuyanagi et al.
Fig. 3.
Folding scan tree configuration.
To avoid much degradation of the fault coverage, the order of the flip-flops in the non-parallel part is decided such that fewer conflicts occur in the folding scan tree. In our scan method, a folding scan tree is used first to detect many easy-to-detect faults, and then a fully compatible scan tree is used to detect the rest of faults. A fully compatible scan tree and a folding scan tree can be configured as shown in Fig. 3. The procedure of reducing scan shifts using a folding scan tree and a fully compatible scan tree is summarized as follows. Procedure 2: configuration of a folding scan tree and test pattern generation for the two scan tree configurations 1. For given test pattern T , apply Procedure 1 and obtain the compatibility of each pair of FFs and a fully compatible scan tree. 2. Reorder the FFs in the non-parallel part using the compatibility such that less conflicts occur in the test pattern when they are forced into the parallel part. 3. Set T f = T . 4. Modify T f such that all FFs in parallel have the same value in the folding scan tree. 5. Turn the don’t care values in T f into {0, 1} randomly. 6. Apply fault simulation with T f to the circuit in the folding scan tree, and remove unnecessary vectors. 7. If there exists no undetected faults, then quit. 8. Set Tc = T . 9. Modify Tc such that all FFs in parallel have the same value in the fully compatible scan tree. 10. Apply fault simulation with Tc for the remaining faults to the circuit in the fully compatible scan tree, and remove unnecessary vectors.
3.3.
Modifying Scan Tree for Scan-out Operation
Although several methods have been proposed to reduce test data and test application time using multiple
Fig. 4.
Selection of scan chains.
scan chains like scan trees, most of them utilize MISR to observe the output of scan chains. In this paper, we also consider scan trees with single scan-in and single scan-out to compare the test application time of a circuit with single scan chain that also has single scan-in and single scan-out. It is known that there is no need to observe all outputs of scan flip-flops to detect all faults. If a fault can be detected at a primary output, the output of flip-flops are not required to be observed. There are some faults that can only be detected at the output of scan flip-flops. To detect such faults, the output of a scan flip-flop must be shifted to the scan output. If two or more flip-flops must be shifted to detect all faults and are not on the same scan chains, the same test vector must be applied twice or more during the application of test pattern using a scan tree configuration. Fig. 4 shows an example of selecting scan chains to be observed. Assume that four flip-flops, (2, 6, 9, 12), must be observed at a test vector. On the assumption that the value of flip-flops are observed without compaction using MISR, only one scan chain is selected during the application of a test vector in our experiments. In this example, the test vector must be applied three times to observe the fault effects. To determine which scan chain is selected to be observed, the following procedure is applied, where o(FF j , vi ) is the flag that shows flip-flop FF j is to be observed at test vector vi (o(FF j , vi ) = 1) or not (o(FF j , vi ) = 0). If there is a fault that is detected only by vi and is observed only at FF j , o(FF j , vi ) is uniquely determined to 1 since we have to observe the flip-flop to detect the fault. Procedure 3: Selecting scan chains per scan to be observed. 1. Apply fault simulation with T . Set F be the set of detectable faults that can not be detected at a primary output for any test vector. 2. Set o(FF, v) = 0 for each flip-flop FF and each vector v.
Reducing Scan Shifts Using Configurations of Compatible and Folding Scan Trees 3. Set o(FF j , vi ) = 1 if there exists a fault that can be detected only at vi and at FF j . 4. For each o(FF j , vi ) = 1, delete the faults detected at vi and FF j from F. 5. If there exists fault f ∈ F that is detected only at vi and at two or more FFs, select one of the FFs FF j and set o(FF j , vi ) = 1. 6. For each o(FF j , vi ) = 1, delete the faults detected at vi and FF j from F. 7. For each o(FF j , vi ) = 1, replace FF j with FF k those are placed in parallel if it reduces the number of the scan chains to be observed. The position of FF j is fixed if it is replaced. 8. For each o(FF j , vi ) = 1, set o(FF k , vi ) = 1 for each FF k on the scan chain between the scan-in terminal and FF j . 9. For each o(FF j , vi ) = 1, delete the faults detected at vi and FF j from F. 10. If F = φ, set o(FF, v) = 1 such that a fault f ∈ F can be detected at v and at FF then go to 6, otherwise quit. To reduce the number of scan chains observed, some flop-flops placed in parallel are replaced in Step 7. Example 2: An example of replacement of the FFs in a scan tree is shown in Fig. 5. Consider the case that FF 2 , FF 5 and FF 11 are required to be observed for detecting faults f 0, f 1 and f 2 at vector v1 and that FF 8 and FF 9 are required to be observed for detecting faults f 3 and f 4 at vector v2. In a scan tree shown in Fig. 5(a), two scan chains must be observed to detect the faults. However, FF 6 , FF 9 , and FF 11 , which are placed in parallel, can be replaced without changing the scan pattern. In this case, replacing FF 11 and FF 6 can reduce the number of scan chains to be observed from two to one as shown in Fig. 5(a). The position of FF 2 , FF 5 and FF 11 are fixed. For vector v2, FF 8 and FF 11 must be observed to detect f 3 and f 4 as shown in Fig. 5(b). In this case, FF 5 can not be replaced with FF 8 . Therefore, two scan chains must be observed at vector v2. 4.
Experimental Results
We implemented the procedures in the C language, and ran on a Sun Ultra 10 workstation. Our procedures are applied to several ISCAS 89 and ITC 99 benchmark circuits which have more than forty flipflops.
617
Fig. 5. Modifying a scan tree for scan-out operation: (a) replacement of the FFs to reduce the scan chains to be observed at vector v1, (b) FFs to be observed at vector v2.
The test vectors used in our experiments are obtained using a combinational test pattern generation without test compaction. Since test vectors generated without test compaction include many don’t care values, many compatible sets of flip-flops may exist. There are about 90% of don’t-care bits in the test vectors used in our experiments. Table 1 shows the experimental results of configuring scan trees. Column FF shows the number of flip-flops for each circuit. Procedure 1 is applied to configure a fully compatible scan tree and then Procedure 2 is applied to configure a folding scan tree based on the fully compatible scan tree. Columns chain and len show the number of scan chains and the maximum length of scan chains, respectively. Column vec and detected show the number of test vectors and the number of detected faults, respectively. The number of detected faults shown under fully compatible scan tree is the number of faults that is not detected by a folding scan tree but detected by a fully compatible scan tree. Table 2 shows the results of the number of scan shifts required for a single scan chain and for our scan tree method. The number of scan shifts are shown in Column scan shift and are calculated by (len + 1) × vec + len, where len is the length of scan chains and vec is the number of test vectors. The columns under single
618
Yotsuyanagi et al.
Table 1.
Results of the obtained scan trees for benchmark circuits. Folding scan tree
Circuit
FF
chain
len
s5378
179
46
s9234.1
211
42
s13207.1
638
s15850.1
Fully compatible scan tree
vec
Detected
chain
len
vec
12
72
4,014
42
51
109
549
20
114
4,882
39
73
156
1,593
220
20
192
8,765
218
43
144
899
534
131
23
195
10,480
127
115
117
856
66
32
3
16
1,171
25
24
42
333
b07s
49
16
6
10
805
12
29
38
327
b12
121
30
9
56
2,236
27
32
59
560
b13s
53
22
7
20
759
21
11
19
72
b14s
245
59
41
161
10,946
56
132
289
1,591
b20s
490
26
98
285
22,246
24
227
318
2,606
b21s
490
21
73
240
23,701
18
242
329
2,383
b04s
Table 2.
detected
Comparison of scan shifts obtained for single scan chains and for folding scan trees. single scan
fully compatible
scan-in/out
scan-in cycles
folding + fully compatible scan-in
Circuit
FFs
vec
cycles
vec
%
cycles
%
s5378
179
109
19,799
191
9,983
50.4
s9234.1
211
145
30,951
274
20,349
65.7
6,667
33.7
10,294
52.0
14,031
45.3
28,685
92.7
s13207.1
638
259
166,139
292
12,891
7.8
s15850.1
534
128
69,014
299
34,799
50.4
10,431
6.3
38,052
22.9
18,390
26.6
46,070
66.8
b04s
66
46
3,148
72
1,824
b07s
49
41
2,099
49
1,499
57.9
1,141
36.2
2,541
80.7
71.4
1,245
59.3
2,630
125.3
b12
121
96
11,833
117
b13s
53
31
1,727
38
3,893
32.9
2,548
21.5
8,300
70.1
467
27.0
406
23.5
1,554
90.0
b14s
245
402
99,137
b20s
490
424
208,674
554
73,814
74.5
45,372
45.8
72,742
73.4
756
172,595
82.7
101,044
48.4
162,238
b21s
490
408
200,818
77.7
698
169,856
84.6
98,022
48.8
141,025
70.2
Ave.
55.0
Ave.
36.0
Ave.
74.7
scan chain show the results obtained for a single scan chain. The test vectors applied to a single scan chain are generated using test compaction method in [5]. The next three columns show the results obtained for only using a fully compatible scan tree and uncompacted test patterns. The columns under scan-in show the results of scan shift required to provide scan-in pattern to flip-flops. Using a fully compatible scan tree, the number of scan shift is reduced to 55.0% of that for a single scan chain on the average. The columns under folding + fully compatible show the results obtained using
%
cycles
scan-in/out
a folding scan tree in addition to a fully compatible scan tree. Using a folding scan tree along with a fully compatible scan tree, the number of scan shifts can be reduced to 36.0% of that for a single scan chain and to about 65% of that for a fully compatible scan tree only. Especially for s13207.1, scan shifts can be reduced to 6.3% of that for a single scan chain. The columns under scan-in/out show the results of scan shift required for both scan-in and scan-out operations under the assumption the circuits have one scan-in terminal and one scan-out terminal. Some test vectors were applied
Reducing Scan Shifts Using Configurations of Compatible and Folding Scan Trees
several times to observe flip-flops on the different scan chains. For b07s, the folding scan tree required more scan shifts than the single scan chain. If shift clock can be stopped for the time when observing two or more flip-flops at the same position on the scan chains, it is enough to apply test vectors once for observing flipflops required to detect faults and hence the number of scan shifts can be closer to the number shown in the column under scan-in. The test application cost can be better if we apply ATPG again for the folding scan tree and for the fully compatible scan tree. In our method, ATPG is applied once for obtaining uncompacted test patterns. The test pattern is modified for the folding scan tree and the fully compatible scan tree using fault simulation.
5.
6.
7.
8.
9.
10.
5.
Conclusion
We presented a method to reduce scan shift by utilizing two configurations of scan trees. One is a fully compatible scan tree that can provide the test pattern obtained for a single scan chain. The other is a folding scan tree that is used for reducing the length of scan chains. Experimental results for benchmark circuits show that our test method can reduce scan shifts to 36.0% of that for a single scan chain when considering scan-in operation only, and to 74.7% when considering both scan-in and scan-out operations. Since the scan trees configured in our experiments depend only on the test pattern, the trees may be modified if there exists the layout constraints of the scan flip-flops. There exists a case that one test vector is applied several times to observe the fault effect propagated to flip-flops. To reduce more scan shift for scan-out operation may be possible by not simply repeating the application of the same vectors but by modifying vectors for scan-out. A method for optimal configurations of scan trees for scan-out operation has to be considered as a future work. References 1. B.B. Bhattacharya, S.C. Seth, and S. Zhang, “Double-Tree Scan: A Novel Low-Power Scan-Path Architecture,” in Proc. Int’l Test Conf., 2003, pp. 470–479. 2. C.-A. Chen and S.K. Gupta, “Efficient BIST TPG Design and Test Set Compaction via Input Reduction,” IEEE Trans. on CAD, vol. 17, no. 8, pp. 692–705, 1998. 3. I. Hamzaoglu and J.H. Patel, “Reducing Test Application Time for Full Scan Embedded Cores,” in Proc. Int’l Symp. FaultTorelant Computing, 1999, pp. 260–267. 4. W.B. Jone, J.C. Rau, S.C. Chang, and Y.L. Wu, “A TreeStructured LFSR Synthesis Scheme for Pseudo-Exhaustive Test-
619
ing of VLSI Circuits,” in Proc. Int’l Test Conf., 1998, pp. 322– 330. S. Kajihara, I. Pomeranz, K. Kinoshita, and S.M. Reddy, “CostEffective Generation of Minimal Test Sets for Stuck-at Faults in Combinational Logic Circuits,” IEEE Trans. on CAD, vol. 14, no. 12, pp. 1496–1504, 1995. K. Miyase and S. Kajihara, “Optimal Scan Tree Construction with Test Vector Modification for Test Compression,” in Proc. Asian Test Conf., 2003, pp. 136–141. S.M. Reddy, K. Miyase, S. Kajihara, and I. Pomeranz, “On Test Data Volume Reduction for Multiple Scan Chain Designs,” in Proc. VLSI Test Symp., 2000, pp. 103–108. S. Samaranayake, N. Sitchinava, R. Kapur, M.B. Amin, and T.W. Williams, “Dynamic Scan: Driving Down the Cost of Test,” IEEE Computer, pp. 63–68, 2000. S. Sybille, H.-G. Liang, and H.-J. Wunderlich, “A Mixed Mode BIST Scheme Based on Reseeding of Folding Counters,” in Proc. Int’l Test Conf., 2000, pp. 778–784. D. Xiang, S. Gu, J.Sun, and Y. Wu, “A Cost-Effective Scan Architecture for Scan Testing with Non-scan Test Power and Test Application Cost,” in Proc. Design Automation Conf., June 2003, pp. 744–747.
Hiroyuki Yotsuyanagi received his B.E., M.E. and Ph.D degrees from Osaka University, in 1993, 1995 and 1998, respectively. In 1998 he joined the Department of Electrical and Electronic Engineering, the University of Tokushima, where he is currently an Associate Professor. His research interest includes test synthesis for sequential circuits and current testing for CMOS ICs. He is a member of the IEICE and the IEEE.
Toshimasa Kuchii received B.E., M.E., and Ph.D. degrees in Electrical and Electronic Engineering from the University of Tokushima in 1994, 1996, and 1999, respectively. He is currently a DFT engineer at Sharp Corporation. His research interests are DFT methodologies for SoC devices, PLL jitter testing, and DFT for image sensor devices.
Shigeki Nishikawa received B.E. in the Department of Information and Behavioral Sciences from Hiroshima University in 1980. He is currently a manager of LSI test engineering department at Sharp Corporation. His research interests are DFT, DFM and the total solution of testing technologies in the CAE tools.
Masaki Hashizume received his B.E. and M.E. degrees in electrical engineering from the Univ. of Tokushima and Dr.E. degree from Kyoto Univ., in 1978, 1980 and 1993, respectively. He is currently a Professor of the Department of Electrical and Electronic Engineering, Faculty of Engineering, the Univ. of Tokushima. His research interests are logic synthesis and supply current testing of logic circuits. Kozo Kinoshita received B.E., M.E., and Ph.D. in Communication Engineering from Osaka University in 1959, 1961, and 1964, respectively. From 1964 to 1966 he was an Assistant Professor and from 1967 to 1977, an Associate Professor of Electronic Engineering at Osaka University, Osaka, Japan. From 1978 to 1989, he was
620
Yotsuyanagi et al.
a Professor in the Department of Information and Behavioral Sciences, Hiroshima University, Hiroshima, Japan. From 1989 to 2000, he again joined Osaka University as a Professor in the Department of Applied Physics, and is enumerates professor of Osaka University. Since April 2000, he has been a professor at Faculty of Informatics, Osaka Gakuin University, and is the Dean of Informatics. His fields of interest are test generation, fault diagnosis, memory testing, cur-
rent testing, crosstalk testing, compact testing and testable design for logic circuits. He organized a series of Asian Test Symposium and was the Group Chair of Asian and Pacific Activities in Test Technology Technical Council of IEEE Computer Society until 2002. Prof. Kinoshita is IEEE Life Fellow, IEICE Fellow and a member of the Institute of Information Processing of Japan. He was a member of the editorial board of JETTA until 2000.