Evaluation and Generation of I_{DDQ} Diagnostic Tests for Bridging Faults in Combinational Circuits

Sreejit Chakravarty

1

Dept. of Computer Science State University of New York Buffalo, NY

Kent Fuchs and Janak Patel Center for Reliable and High Performance Computing University of Illinois Urbana, IL 61801

Technical Report Number 95-11, Department of Computer Science State University of New York, Buffalo, NY 14260.

ABSTRACT

Diagnosis is the process of identifying the fault in a faulty chip. We assume that I_{DDQ} measurement is used during diagnosis. A novel algorithm for evaluating the effectiveness of a set of input vectors to diagnose bridging faults in combinational circuits is presented. We also present a simulation based test generator for computing I_{DDQ} tests for diagnosing bridging faults. Experimental evaluation of the algorithms are presented. The results obtained are very encouraging.

1 Introduction

In a circuit when two or more distinct lines, due to a defect, are connected we get a bridging

fault. Such faults model 40 - 50% of physical defects in contemporary MOS technologies[11,

17]. Circuits with such faults can be identified by applying a set of input vectors and

monitoring either the steady state supply current ( I_{DDQ} Measurement ) or the logic level

at the primary outputs ( Logic Measurement ). We assume that faults are being detected

using I_{DDQ} measurement and the bridging faults involve only two lines. The abbreviation

TBF is henceforth used to refer to such faults.

1Research supported by NSF Grant No. MIP-9102509. This work was done while the author was visiting CRHC, Univ. of Illinois, Urbana, IL

Diagnosis is the process of identifying the fault(s) that caused system failure. It involves the application of a set of input vectors ( Diagnostic Test Set ) and capturing the response of the circuit to these set of vectors. The response is then analysed and the possible set of faults is narrowed down to a few candidate faults ( residual set). I_{DDQ} measurement based analysis of such responses, assuming TBFs in combinational circuits, has been discussed in [7, 8]. In addition to analysing the responses there is a need for computing good diagnostic test sets. The better the test set the smaller the set of residual faults. We address the problem of computing diagnostic tests for I_{DDQ} measurement based diagnosis of TBFs in combinational circuits.

Prior to developing an algorithm for computing diagnostic tests ( Diagnostic Test Generation ) we need quantitative measures to measure the effectiveness of diagnosing TBFs using a given set of input vectors. We use the diagnostic measures described below [4, 12, 13, 19, 21].

Two faults F 1, F 2 are said to be equivalent, with respect to a set of input vectors T, if and only if for each input vector T_{i} in T the reponses of the two faulty circuits respectively with F 1, F 2 in them are the same. This binary relation on the set of TBFs is an equivalence relation and partitions it into equivalence classes. Let E_{1}, …, E_{m} be the equivalence classes, of the set of TBFs, with respect to the test set T; M be the number of TBFs; and P be the number of fault equivalence classes of size 1. Diagnostic Resolution(DR), of a diagnostic test set T, is the percentage of TBFs that can be completely distinguished from all other TBFs using T. More formally, DR = \frac{P}{M} × 100. Diagnostic Power(DP), of a diagnostic test set T, is the percentage of pairs of TBFs that are not equivalent with respect to T. Expected Residual Size(ERS), of the test set T, is the expected value of the size of the residual set computed using T. More formally, ERS(T) = ∑_{i=1}^{m} \frac{∥E_{i}∥∗∥E_{i}∥}{M}. We use DR and ERS as the two diagnostic measures. In addition, we note that there is a wide variation in the size of the set of equivalence classes. To compare two diagnostic test sets with almost equal ERS we use the standard deviation of the size of the equivalence classes ( SD-ECS) as a third measure. The process of computing DR, ERS and SD-ECS is henceforth referred to as diagnostic simulation.

Diagnostic simulation algorithms for stuck-at faults has been discussed in [5, 6, 13, 19, 21].

We are unaware of any published work on diagnostic simulation of TBFs. We fill this void by presenting a novel algorithm for diagnostic simulation of I_{DDQ} tests for TBFs in combinational circuits. The large number of TBFs precludes the use of any explicit fault enumeration techniques. The novel feature of this algorithm is that it adapts an implicit enumeration technique for TBFs[7, 8] and show how it can be combined with the “list splitting strategy” [5, 6, 21] to develop an efficient diagnostic fault simulation algorithm for TBFs. The “list splitting strategy” provides us with a means to avoid either storing or comparing long sequences of faulty responses thus saving us both space and time. This algorithm is discussed in Section 3.

We next present a simulation based algorithm for computing diagnostic tests. We are unaware of any published work on diagnostic test generation for TBFs. Diagnostic test generation for stuck-at faults has been discussed in [4, 12].

Our algorithm uses the algorithmic paradigm known as simple genetic algorithm (SGA)[10]. SGAs have been used for computing tests for stuck-at faults[20, 22]. It is particularly suitable when there are a large number of faults and we want to avoid targetting any specific fault during test generation. This was the primary reason for adopting SGAs which is discussed in Section 4. It requires the use of a “fitness function” for each input vector. The use of “list splitting ” by our diagnostic simulation algorithm provides a means for “incremental computation” of the equivalence classes. This attribute of the simulation algorithm makes it particularly attractive for use in an SGA based test generation algorithm. Accordingly, the “fitness function” we use is a modification of our diagnostic simulation algorithm. Experimental results are presented in Section 5. The results obtained are very encouraging.

2 I_{DDQ} Tests

Consider the circuit shown in Figure 1(a). Its switch level diagram is shown in Figure 1(b). In the fault free case, and on application of input vector T 1 =< a = 0, b = 0, c = 1, d = 1 > the steady state supply current (I_{DDQ}) is negligible. However, if the TBF < e, f > is present and the input vector T 1 is applied then there will be a conducting path along the pullup network (P 1), the TBF < e, f >, and the pulldown network (P 2). This large steady state current signals the presence of a fault.

In Figure 1 nodes h, j, k are not outputs of any of the gates nor are they primary inputs.

Such nodes are known as internal nodes. Unlike the rest of the nodes, internal nodes can take on the logic values 0, 1, f ( for floating ).Consider the input vector T 2 =< a = 1, b = 1, c = 0, d = 0 >. There is no path from node h to either V_{DD} or GND and h is said to be floating. As a result, on application of T 2 and even in the presence of any of the TBFs involving node h and any other node I_{DDQ} will be negligible. Hence T 2 will not detect any of these TBFs. Thus, we declare an input vector T to be an I_{DDQ} test for a TBF < X, Y > if and only if T (X) ≠ T (Y), &T (X), T (Y) ∈ {0, 1}[16].

3 Diagnostic Simulation

Our diagnostic simulation consists of two basic steps, UpdatePartitions, and UpdateEquivClasses. The algorithm iterates through these two basic steps,described below, for each input vector.

3.1 Partitions

Refer to Table 1. It defines a set of input vectors and the fault free logic value for each node in the circuit of Figure 1. We note that for all input vectors, nodes c, h have the same logic value. Such lines are said to be equivalent with respect to the given test set. More formally, two nodes x, y are equivalent with respect to a test set T if and only if for each input vector T_{i} ∈ T T_{i}(x) equals T_{i}(y) where T_{i}(x) ( T_{i}(y) ) is the fault free logic value at x(y) on application of T_{i}. This binary relation on the set of nodes is an equivalence relation and therefore partitions the set of nodes into equivalence classes. However, to avoid confusion with equivalence classes of TBFs we refer to the equivalence classes of nodes as partitions. The partitions of the set of nodes of the circuit of Figure 1 with respect to the test set of Table 1 are: {a}, {b}, {c, h}, {d, g}, {e, j}, {f}, {k}.

Given a Test Set T and a circuit C, the partitions of the nodes in C with respect to T can be computed by first computing a table similar to Table 1 and then performing pair-wise comparison of the values assigned to each of the nodes. This is an expensive algorithm. A faster algorithm for this is discussed in [9]. The basic idea used in this algorithm is explained below with the help of an example.

P art(INIT) is the initial set of partitions, P art(T_{i}) is the set of partitions obtained after processing the set of input vectors {T_{1}, …, T_{i}}. Refer to the example of Figure 1 and the test set of Table 1.

As shown in Figure 2(a), P art(INIT) = {P 0} = {{a, b, c, d, e, f, g, h, j, k}}. Next, P 0 is split, by processing input vector T 1, into two parts P 1, P 2. P 1(P 2) contains all nodes in P 0 set to 0(1) by T 1. In general there will be three such subsets corresponding to the values 0, 1, f.

As shown in Figure 2(b), P art(T_{1}) = {P 1, P 2} = {{a, b, d, g, k}, {c, e, f, h, j}}. Next, as shown in Figure 2(c), T 2 splits P 1(P 2) into P 3, P 4, P 5(P 6, P 7) giving us P art(T_{2}) = {P 3, P 4, P 5, P 6, P 7} = {{b}, {a, d, g}, {k}, {e, f, j}, {c, h}}.

The process uses O(N) space and computing P art(T_{i−1}) from P art(T_{i}) takes time O(N) where N is the number of nodes[9]. Henceforth we refer to the process of computing P art(T_{i}) from P art(T_{i−1}) as UpdatePartitions.

3.2 Equivalence Classes

Equivalence classes of the set of TBFs, with respect to a given set of input vectors, was defined in Section 1. TBFs in a given equivalence class need to be specified. Explicitly enumerating the TBFs in an equivalence class will be very time and space consuming. Therefore, we use an implicit enumeration technique. The use of Sets of Ordered Pairs of Sets (SOPS)[7], defined below, to represent sets of TBFs enables us to achieve this end. Let A, B be two sets of nodes in the circuit. Then the ordered pair of sets < A, B > denote the set of TBFs < x, y > such that x ∈ A, y ∈ B. A set of such ordered pairs of sets can then be used to represent an equivalence class. For example the SOPS {< {a, b, c}, {e, d} >, < {a, b, c}, {a, b, c} >} denotes the set of TBFs {< a, e >, < a, d >, < b, e >, < b, d >, < c, e >, < c, d >, < a, b >, < a, c >, < b, c >}.

In the above example lines a, b, c are repeated three times. If a large number of nodes are repeated several times the space used by the representation increases. To contain that we use pointers. As will become clear later the set of nodes in our SOPS will be node partitions. Let us assume that we have processed input vector T_{i} and P art(T_{i}) = {P 0, P 1, P 2} = {{a, b, c}, {e, d}{f}}. Then, the equivalence class {< {a, b, c}, {e, d} >, < {a, b, c}, {a, b, c} > } is represented as {< P 0, P 1 >, < P 0, P 0 >}. This usually requires less space and is used by our algorithm.

To explain how Equivalence Classes (EC) of TBFs are computed we use an example. Let EC(INIT) be the initial set of ECs and EC(T_{i}) be the set of ECs after processing input vectors {T_{1}, …, T_{i}}.

Initially, as shown in Figure 2(a), for the circuit of Figure 1 we have P art(INIT) = {{a − h, j, k}}. P0 is the pointer to this partition. Therefore, EC(INIT) = {< P 0, P 0 > } = {E0} assuming that we are targetting all TBFs in the circuit.

Next, we process T_{1}. The partition list is updated to be P art(T_{1}) = {P 1, P 2} = {{a, b, d, g, k}, {c, e, f, h, j}}. As shown in Figure 2(b), P 1(P 2) points to the subset of the partition pointed to by P 0 that is set to 0(1) by T_{1}. Thus, {< P 1, P 2 >} denotes the set of TBFs in E0 that are detected by T_{1}. Similarly, {< P 1, P 1 >, < P 2, P 2 >} denotes the set of TBFs in E0 that are not detected by T_{1}. Hence, we can split the EC E0 into two ECs: (i) the subset of E0 detected by T_{1}; and (ii) the subset of E0 not detected by T_{1}. The new set of equivalence classes with respect to {T_{1}} is given by EC(T_{1}) = {{< P 1, P 2 >}, {< P 1, P 1 >, < P 2, P 2 >}} = {E1, E2}. After computing EC(T_{1}) we can release the space used by EC(INIT). Similarly, we can release the space used by P art(INIT) after computing P art(T_{1}).

The processing of T_{2} is shown in Figure 2(c). We first compute P art(T_{2}) = {{b}, {a, d, g}, {k}, {e, f, j}, {c, h}} = {P 3, P 4, P 5, P 6, P 7}. Next each of E1, E2 in the list of equivalence classes EC(T_{1}) is split into two Equivalence Classes as was done for E0. Note that < P 3, P 3 > and < P 5, P 5 > do not represent any TBFs and are deleted. At the end of this we have:

EC(T_{2}) = { {< P 4, P 6 >, < P 3, P 7 >}, {< P 3, P 6 >, < P 4, P 7 >, < P 5, P 6 >, (1)
< P 5, P 7 >}, {< P 3, P 4 >, < P 6, P 7 >}, {< P 3, P 5 >, < P 4, P 4 >,
< P 4, P 5 >, < P 6, P 6 >, < P 7, P 7 >} }
= {E3, E4, E5, E6}

More formally, the rules for computing EC(T_{i}) from EC(T_{i−1}) are defined as follows. Let EC(T_{i−1}) be {E_{0}, …, E_{M}}. First, using UpdatePartition, P art(T_{i}) is computed from P art(T_{i−1}). Next, each E_{j} ∈ EC(T_{i−1}) is split into two set of TBFs E_{j}(Det), E_{j}(UnDet) where E_{j}(Det)(E_{j}(UnDet)) is the subset of E_{j} detected ( not detected ) by T_{i}.

Let E_{j} ∈ EC(T_{i−1}) be represented by the SOPS {< A_{1}, B_{1} >, …, < A_{Q}, B_{Q} >} where the A′_{k}s, B′_{k}s are pointers to partitions in the collection of partitions P art(T_{i−1}). E_{j}(Det) is computed as follows. For each < A_{k}, B_{k} >∈ E_{j} we compute Det(k), the subset of TBFs represented by this pair of sets that are detected by T_{i}, as follows. Let A_{k}(0), A_{k}(1), A_{k}(f) be pointers to partitions in P art(T_{i}) such that for all t ∈ {0, 1, f} A_{k}(t) points to the subset of nodes in A_{k} set to t by T_{i}. Notations B_{k}(0), B_{k}(1), B_{k}(f) are similarly defined. Then,

Det(k) = {< A_{k}(0), B_{k}(1) >, < A_{k}(1), B_{k}(0) >}  (2)
E_{j}(Det) = ⋃_{k=1}^{Q} Det(k)  (3)

Let UnDet(k) be the subset of TBFs represented by < A_{k}, B_{k} > that are not detected by T_{i}. Then,

UnDet(k) = {< A_{k}(0), B_{k}(0) >, < A_{k}(0), B_{k}(f) >, < A_{k}(1), B_{k}(1) >,  (4)
< A_{k}(1), B_{k}(f) >, < A_{k}(f), B_{k}(0) >, < A_{k}(f), B_{k}(1) >, < A_{k}(f) >, B_{k}(f) >}
E_{j}(UnDet) = ⋃_{k=1}^{Q} UnDet(k)  (5)

In both Eqn(2), Eqn(5) if any of the pairs of pointers denote an empty set of TBFs it is deleted from the list. Note that, in Eqn(2), if A_{k} is the same as B_{k} then the two pairs denote the same set of TBFs. Only one of them is retained. Similarly, in Eqn(5), if A_{k} is the same a B_{k} then < A_{k}(1), B_{k}(f) > is the same as < A_{k}(f), B_{k}(1) > and only one is retained. We achieve this by adding two other rules for pairs of the form < A_{k}, A_{k} > which are simplication of Eqn(2), Eqn(3). Using these additional rules we are guaranteed that every pair of partition pointers represent disjoint sets of TBFs and, by definition, the ECs represent disjoint set of TBFs. The use of Eqn(2) to Eqn(5) is referred to as UpdateEquivClasses and uses “list splitting”, a paradigm used earlier for diagnostic simulation of stuck-at faults[5, 6, 21].

3.3 Outline Of The Algorithm

Note that as the number of vectors simulated increases the number of pairs of partition pointers in each SOPS representing an EC increases. However, it will never be worse than explicitly enumerating all the faults in the EC. In the initial stages of the simulation the use of SOPS results in a considerable speedup. To improve the speed of simulation during the later stages we use the following strategy. Note that once an EC has reduced to size 1 we can delete it and simply keep track of the number of ECs of size 1. The better the diagnostic test set the more effective this strategy will be. The diagnostic simulation algorithm is outlined in Figure 3.

To complete the example we started in the previous subsection refer to Figure 4. For now, ignore the numbers within [], {}. Figure 4(a) shows how each partition is split into its subpartitions using UpdatePartitions. In Figure 4(b) we show how each E_{j} in EC(T_{2}), from Figure 2(c), is split into its two subsets - E_{j}(Det), E_{j}(UnDet).

Having computed EC(T_{3}), we compute the diagnostic measures. To do that we first compute the size of each EC. This is done by computing the number of TBFs represented by each pair of partition pointers. For example, in Figure 4(b) < P 10, P 12 > representes 4 TBFs. This is because each of the two pointers point to a partition of size 2 ( see Figure 4(a) ). In Figure 4(b) the number of TBFs represented by each pair of partition pointers is shown next to it, within []. Note that < P 12, P 12 > represents 1 not 4 TBFs. Also, < P 9, P 9 > and < P 12, P 12 > are deleted because they represent empty sets of TBFs.

We had taken care to make the set of TBFs represented by distinct pairs of partition pointers to be disjoint. At the same time every TBF occurs in an EC at most once. Therefore, we add the sizes of the set of TBFs represented by the pairs of partition pointers constituting an EC. For each EC of Figure 4(b) its size is shown within {}.

The measures can now be computed. We have: SINGLETONS = 0; and M, the total number of faults, to be 45. Thus: DR = \frac{0}{45} × 100 = 0%; Max-ECS, the maximum size of an EC, is 7;

ERS = \frac{(49 + 16 + 49 + +49 + 9 + 36 + 49 + 16)}{45} = 6.07;
SD ECS = \frac{4 × 7 × (7 − 6.07)^{2} + 2 × 4 × (4 − 6.07)^{2} + 3 × (3 − 6.07)^{2} + 6 × (6 − 6.07)^{2}}{45}
= 1.93.

Before presenting the experimental results we draw the reader’s attention to two important issues. If one uses dictionary based diagnosis we need to store the responses for each equivalence class computed. The responses are sometimes used in diagnostic simulation algorithms, in a post processing phase, to compute the equivalence classes [19]. However, we advocate the use of the diagnosis algorithm in [7] that does not use fault dictionaries. In addition, the use of “list splitting” [5, 6, 21] enables us to do away with the post processing phase that require the use of response vectors. Thus, we do not store the sequence of responses for the ECs. Consequently, the time and space requirement of the algorithm is drastically reduced.

The second issue is concerned with the computation of other measures proposed in [21]. Define DR(K) to be the percentage of faults that are in an equivalence class of size no more than K. Thus, DR defined in Section 1 is DR(1). Since we have the list of ECs at our disposal we can easily compute such measures by a simple modification of the above simulation algorithm. Similarly, if we were interested in DP, defined in Section 1, they could be easily computed from the list of equivalence classes. Experimental results will be presented in Section 5.

4 Diagnostic Test Generation

Our diagnostic test generator is a simulation based test generator and uses an algorithmic frame work known as genetic algorithms.

4.1 Simple Genetic Algorithm

This algorithmic paradigm, which has been used for a number of optimization problems, is outlined below. The primary reason for using this approach is that we do not have to target any specific fault making it attractive when the fault list contains a large number of faults, as is true in our case. The test generation problem is formulated as an optimization problem as follows.

We will be computing one vector at a time. Suppose we have computed the set of vectors {T_{1}, …, T_{i−1}} and the list of equivalence classes with respect to these set of vectors is EC(T_{i−1}). We next compute an input vector T_{i} such that the set of diagnostic measures with respect to the new set of equivalence classes EC(T_{i}) is optimized. That is, DR is maximized, ERS is minimized, etc. This selection process is outlined in Figure 5. Fitness Function: The selection of a vector to be the next test in the test set is based on the fitness of the vector. The fitness function F F (v), which returns a real number for every possible input vector v, that we use is the following. Let F_{1}, …, F_{P} be the P largest equivalence classes in EC(T_{i−1}) and for all 1 ≤ j ≤ P, SIZE DF_{j}(v), SIZE UDF_{j}(v) be the sizes of the subset of TBFs in F_{j} that are respectively detected, not detected by input vector v and Q be the number of such non-empty subsets. Then,

F F (v) = \frac{1}{Q} × ∑_{j=1}^{P}\{SIZE DF_{j} + SIZE UDF_{j}\}

In our experiments we used P = 10. The POPSIZE used in our experiments was 100. To compute a test the population is evolved through NUMGEN = 10 generations. Evolving the population through one generation consists of a Reproduction, Crossover and a Mutate step. Reproduction. The roulette wheel method is used to generate the initial population for the next generation. The wheel is divided into POPSIZE sectors and each vector in the population is assigned to one vector. The sectors are of unequal size. The sector assigned to vector v is proportional to F F (v). The wheel is turned POPSIZE time. For each spin, if the wheel stops in the sector for vector z then z is reproduced in the next generation. A vector can be reproduced several times. Crossover. It is the process of producing two new offsprings from two parents. If V_{1}, V_{2} are the two parent vectors, a bit position q is randomly selected for crossover. Two new vectors X_{1}, X_{2} are created as follows. Bit positions 1 through q − 1 of X_{1} ( X_{2} ) are the same as those of V_{1} ( V_{2} ). The remaining bits of V_{1} ( V_{2} ) are copied over into positions q, q + 1, … of X_{2} ( X_{1} ). In our experiments, the first vector is mated with the second, the third with the fourth and so on. Mutation. Each bit of every vector in the population is scanned and flipped with probability MUT PROB. In our experiments we used MUT PROB = .001.

Once we have created a new generation the fitness function for all the vectors are computed and compared with the best solution computed so far. After evoving through NUM-GEN generations the best vector generated during the process is included in the test set. This vector is now used to compute EC(T_{i}) by splitting all the ECs in EC(T_{i−1}) as explained in Section 3. Note that since we are using an incremental simulation algorithm we can compute EC(T_{i}) from EC(T_{i−1}) without having to go through the simulation of vectors T_{1}, …, T_{i−1} once again. Stopping Criteria. We note that after computing a number of vectors the best vector selected may have a fitness value that is the same as the previous vector included in the test set. Since we are using an approximate disagnostic simulation in our fitness function this does not imply that new equivalence classes will not be created if this vector is selected. It does mean however, that it will not be able to split up the largest equivalence classes. We take this as an indication that the process may not be able to improve the test set if the process continues. So, if the fitness value of the best selected vector does not change for five consecutive vectors computed we terminate the test generation process.

5 Experimental Results

Experimental evaluation of the diagnostic simulator and the simulation based test generator are presented. The experiments were performed on a SUN Sparkstation 2 with 64 MB of memory. No fault collapsing was used. Results for all the ISCAS85 and full scan version of some of the ISCAS89 circuits are presented. The stuck-at test set used was obtained using ATALANTA[1].

Two classes of TBFs were considered. Metal-BFs include all TBFs that are between gate outputs. All-BFs include all TBFs that are between nodes that can be either gate outputs or internal nodes.

Table 2 ( Table 3 ) presents simulation results for Metal-BFs ( All-BFs ). In these tables Total Faults is the total number of faults, Test Size is the size of the test set, DR is the diagnostic resolution, ERS is the expected value of the residual set size, SD-ECS is the standard deviation of the size of the equivalence classes, Max ECS is the maximum of the equivalence class size and Time is the CPU time in seconds. The diagnostic simulator requires considerable space if the size of the test set is large. For this reason we have not presented the results for All-BFs for s5378 etc. which were presented in Table 2.

Table 4 ( Table 5 ) presents the raw statistics for the performance of the diagnostic test generator for Metal-BF ( All-BF ). We next interpret them by comparing them with the results from Tables 2, 3.

Table 6 presents the comparison for Metal-BFs where:

Size = Size(T estGenerated)/Size(Stuck − at)
DR = DR(T estGenerated) − DR(Stuck − at)
ERS = ERS(T estGenerated) − ERS(Stuck − at)

Therefore, if Size is less than 1 then the test generator generates a smaller test set. If DR is positive then the diagnostic resolution of the generated test set is better than ( greater than ) the diagnostic resolution of the stuck-at test set. If ERS is positive then the expected residual set size of the generated test set is better than ( less than ) that of the stuck-at test set. Table 7 presents similar data for All-BFs.

I_{DDQ} measurement is a very slow process. Therefore, the size of the test set is very important so far as the diagnosis time as well as the difficulty of maitaining them is concerned. From Table 6 we note that the diagnostic test set generated, for each circuit, is considerably smaller than the stuck-at test set. In fact, on an average it is about 48% of the size of the stuck-at test set. In addition, for almost all the circuits, both DR and ERS of the generated test set is considerably better. For the two cases for which this is not true the difference is marginal. Thus, we can conclude that for Metal-BFs the proposed diagnostic test generator generates considerably better and smaller diagnostic test set.

Note that diagnostic stuck-at test sets are usually much larger than detection test set. They will therefore be much larger than the diagnostic test sets generated by the proposed test generator. We therefore suggest that diagnostic stuck-at test sets not be used. However, if better diagnosibility is required it be built on top of the test set computed by the the proposed test generator. We are currently pursuing this end.

The results for All-BFs is less encouraging. An inspection of Table 7 reveals that the diagnostic capability of the generated test set is considerably better but its size is also larger. We are currently investigating methods on improving this.

References

[1] ATALANTA. Sofware available from Prof. D. S. Ha, Bradley Department of Electrical Engineering, VPISU, Blacksberg, Va.

[2] F. Brglez, D. Bryan, and K. Kozminski, “Combinational Profiles of Sequential Benchmark Circuits,” Int’l Symp. Circuits and Systems, pp. 1929 - 34, May 1989.

[3] F. Brglez and H. Fujiwara, “A Neural Netlist of 10 Combinational Benchmark Circuits and a Target Translator in FORTRAN”, Special Session on ATPG and Fault SImulation, IEEE Int’l Symposium on Circuits and Systems 1985.

[4] P. Camurati, D. Medine, P. Prinetto, M. S. Reorda, “A Diagnostic Test Pattern Generation Algorithm,” IEEE Int’l Test Conference, pp. 52 - 58, 1990.

[5] S. Chakravarty, Y. Gong, “Diagnostic Simulation of Stuck-at Faults in Combinational Circuits,” IEEE VLSI Test Symposium, pp. 128 - 133, 1994.

[6] S. Chakravarty, Y. Gong, S. Venkataraman, “Diagnostic Simulation of Stuck-at Faults in Combinational Circuits,” Submitted to Journal of Electronic Testing: Theory and Applications.

[7] S. Chakravarty and M. Liu, “Algorithms for Current Monitor Based Diagnosis of Bridging Faults in Combinational Circuits,” Journal of Electronic Testing: Theory and Applications, Vol. 3, pp. 377 - 385, 1992.

[8] S. Chakravarty and S. Suresh, “I_{DDQ} Measurement BAsed Diagnosis of Bridging Faults in Full Scan Circuits,” IEEE Int‘l Conference on VLSI DESIGN, pp. 179 - 182, 1994.

[9] S. Chakravarty and P. J. Thadikaran, “Simulation and Generation of I_{DDQ} Tests for Bridging Faults in Combinational Circuits,” IEEE VLSI Test Symposium, pp. 25 - 32, 1993.

[10] D. E. Goldberg, GENETIC ALGORITHMS: In Search, Optimization & Machine Learning. Addison-Wesley Publishing Co.

[11] J. Galiay, Y. Crouzet, and M. Vergniault, “Physical Versus Logical Fault Models for MOS LSI Circuits: Impact on their Testability,” IEEE Trans. on Computers, Vol. C-29, No. 6, June 1980.

[12] T. Gruning, H. Koopmeiners, U. Mahlstedt, “DIAGTEST: A Fast Diagnostic Test Pattern Generator for Combinational Circuits,” IEEE/ACM Int’l Conf. on Comput.-Aided Design, pp. 194 - 197, 1991.

[13] K. Kubiak, S. Parkes, W. K. Fuchs and R. Saleh, “Exact Evaluation of Diagnostic Test Resolution,” IEEE/ACM Design Automation Conference, pp. 347 - 352, June 1992.

[14] T. Larabee, “Test pattern Generation Using Boolean Satisfiability,” IEEE Trans. on Computer-Aided Design, Vol. 11, No. 1, pp. 4-15, January 1992.

[15] H. K. Lee, D. S. Ha, “HOPE: A Fast Parallel Fault Simulator for Sequential Circuits,” IEEE/ACM Design Automation Conference, June 1992.

[16] K. J. Lee, M. Breuer, “Design and Test Rules to Facilitate I_{DDQ} Test of Bridging Faults,” IEEE Trans. on Comput.-Aided Design, Vol. 11, No. 5, pp. 659 - 669, May 1992.

[17] W. Maly, “Realistic Fault Modeling for VLSI Testing,” IEEE/ACM Design Automation Conference, pp. 173 - 180, 1987.

[18] P. Nigh, W. Maly, “Test Generation for Current Testing,” IEEE Design and Test of Computers, pp. 26 - 38, Feb. 1990.

a b c d e f g h j k
T 1 0 0 1 0 1 1 0 1 1 0
T 2 1 0 1 1 0 0 1 1 0 f
T 3 0 1 0 1 0 1 1 0 0 0

Table 1: Example Test Set.

Figure 1: Example of I_{DDQ} Tests for TBFs.

[19] E. Rudnick, W. K. Fuchs, J. H. Patel, “Diagnostic Fault Simulation of Sequential Circuits,” IEEE Int’l Test Conference, pp. 178 - 186, 1992.

[20] E. Rudnick, J. H. Patel, G. S. Greenstein, T. M. Nierman, “Sequential Circuit Test Generation in a Genetic Algorithm Framework,” IEEE/ACM Design Automation Conference, pp. 698 - 704, 1994.

[21] G. Ryan, W. K. Fuchs and I. Pomerantz, “Fault Dictionary Compression and Equivalence Class Computation for Sequential Circuits,” IEEE/ACM Int’l Conf. on Comput.- Aided Design, pp. 508 - 511, 1993.

[22] D. G. Saab, Y. G. Saab, J. A. Abraham, “Iterative [ Simulation Based Genetics + Deterministic Techniques ] = Complete ATPG”, To appear in IEEE/ACM Int’l Conf. on Comput.-Aided Design, 1994.

Total Test  Max  Time
Circuit  Faults Size DR  ERS SD-ECS ECS (CPU Secs)
c432  19110 74 78.78  1.41  1.93  40  17.27
c499  29403 100 66.04  3.07  5.9  80  28.30
c880  97903 98 59.16  2.07  3.58  85  100.82
c1355  171991 99 60.47  2.14  3.97 121  154.45
c1908  416328 146 7.24 22.72  77.83 1131  522.13
c2670  1127251 310 11.99 10.14  47.38 1077  2066.43
c3540  1476621 227 15.15 20.57 101.98 2206  2896.98
c5315  3086370 370 24.08  9.25  57.05 1746  10967.98
c6288  2995128 83 12.87 1504.92 9863.13 54625  479.45
c7552  6913621 278 17.89 14.52 109.78 3501  20875.98
s208.1  7381 36 10.32 26.58  42.39 192  2.90
s298  9180 37 29.53  3.41  5.24  58  6.52
s344  16836 23 29.19  5.04  9.11  85  7.20
s349  17020 27 14.22 12.20  22.26 136  6.62
s382  16471 39 27.11  3.80  7.26  91  12.62
s386  14706 80 48.72  4.83  10.27  82  14.08
s420 1  31626 78 10.44 121.45 278.85 1140  22.32
s444  20910 37 33.83  3.75  7.22  96  12.82
s510  27730 65 82.83  1.23  1.24  34  24.40
s526  23436 74 33.19  4.96  10.80 122  24.95
s526n  23653 69 29.41  5.75  12.38 129  24.08
s713  99681 55 5.44 29.06  73.95 693  46.20
s820  48516 122 48.29  2.84  5.39  82  84.55
s832  47895 128 51.29  3.37  7.60 102  83.08
s838 1  130816 154 9.14 722.54 1814.99 6295  147.48
s1423  279378 78 42.61 13.29  65.05 963  275.93
s1488  222111 134 59.31  2.80  7.39 164  380.53
s1494  218130 143 62.39  2.82  7.64 173  291.12
s5378  4477528 292 8.09 45.61 293.27 5799  11515.55
s9234 17073246 396 2.90 397.29 4840.34 60426  27337.75

Table 2: Simulation Results for METAL TBFs and Stuck-at Test Sets

Total Test  Max  Time
Circuit  Faults Size DR  ERS SD-ECS  ECS (CPU Secs)
c432  108345 74 50.83 19.48 129.42 1223  122.63
c499  526851 100 32.56 13.43 122.62 1990  849.82
c880  436645 98 39.00  4.43  26.82  643  601.45
c1355  675703 99 26.91 10.05  58.20 1224  1002.23
c1908  1269621 146 6.30 40.16 341.46 5254  2048.20
c2670  3904615 310 6.04 96.77 625.64 10591  6691.78
c3540  6402831 227 15.22 30.21 395.13 9904  18419.93
c6288 12941328 83 3.31 3052.36 48506.12 273970  2511.98
s208.1  27261 36 7.18 193.42 460.637 1842  12.12
s298  47278 37 25.57  8.99  39.70  415  41.68
s344  59685 23 12.02 18.87  62.80  587  24.05
s349  61425 27 7.85 49.69 130.18  949  22.47
s382  66430 39 20.66 11.37  53.14  569  57.90
s386  114003 80 19.94 23.65 116.29 1143  203.45
s420 1  121771 78 8.78 943.83 2426.84 9123  102.48
s444  81003 37 24.69 12.84  54.62  605  55.30
s510  130816 65 42.37  8.62  45.72  629  206.37
s526  152628 74 23.04 52.84 276.98 2269  207.37
s526n  152076 69 20.75 87.54 442.98 3114  192.28
s713  285390 55 6.78 98.63 447.88 3798  154.33
s820  419070 122 30.12 48.80 356.23 3744  1158.90
s832  435711 128 30.69 65.33 464.39 4530  1274.33
s838 1  513591 154 9.53  NA  NA 48042  709.15
s1423  1261666 78 24.74 24.95 225.99 3955  1857.28
s1488  1902225 134 20.25 70.21 680.75 9538  4960.00
s1494  1929630 143 21.05 56.29 532.57 8091  5593.92

Table 3: Simulation Results for ALL TBFs, stuck-at Test Sets

Total Test  Max  Time
Circuit  Faults Size DR ERS SD-ECS ECS (CPU Secs)
c432  19110 27 78.64 1.41  1.93  40  99.50
c499  29403 40 66.45 3.07  5.94  80  140.42
c880  97903 37 59.43 2.60  5.72 116  287.07
c1355  171991 78 65.36 2.03  3.68 112  668.43
c1908  416328 74 7.49 22.68  77.75 1131  1116.73
c2670  1127251 36 13.40 9.58  44.98 1026  1331.03
c3540  1476621 65 15.79 20.44 101.36 2193  2246.38
c5315  3086370 45 27.31 8.44 53.157 1746  3415.43
c6288  2995128 53 90.48 1.34  2.51 183  3104.72
c7552  6913621 58 19.78 14.11 106.12 3443  8230.52
s208.1  7381 33 40.28 3.02  4.06  44  81.03
s298  9180 21 28.69 3.43  5.24  58  61.05
s344  16836 23 49.29 3.33  6.48  75  95.95
s349  17020 23 48.96 3.34  6.62  75  93.57
s382  16471 23 38.84 2.99  5.73  78  95.28
s386  14706 29 55.98 1.88  2.44  41  99.80
s400  17205 24 37.73 3.12  5.83  79  99.17
s420 1  31626 36 22.50 22.05  54.34 359  190.42
s444  20910 26 43.58 2.92  5.94  26  113.65
s510  27730 47 90.18 1.14  1.09  32  200.00
s526  23436 31 40.21 2.94  5.43  80  134.15
s526n  23653 29 38.56 3.03  5.63  82  129.58
s641  93528 36 7.65 16.58  43.83 501  273.40
s713  99681 38 7.08 19.95  52.41 559  298.13
s820  48516 43 53.32 2.17  3.41  60  279.47
s832  47895 44 58.28 1.92  2.62  49  277.98
s838 1  130816 38 10.20 560.67 1481.19 5479  422.25
s953  96580 68 69.15 2.01  4.60 112  581.63
s1196  157080 55 58.42 2.29  6.49 178  626.58
s1238  145530 70 82.10 1.29  2.08  84  703.80
s1423  279378 40 46.45 11.12  55.66 884  687.45
s1488  222111 47 65.06 1.74  3.04 109  727.00
s1494  218130 44 69.44 1.61  2.41  90  696.35
s5378  4477528 113 11.65 20.24 135.78 3844  10152.95
s9234 17073246 157 4.83 288.27 1719.24 29219  27166.65

Table 4: Test Generation Results for METAL TBFs

Total Test  Max  Time
Circuit  Faults Size DR  ERS SD-ECS ECS (CPU Secs)
c432  108345 51 52.93 18.88 126.30 1203  1043.17
c499  526851 182 39.57  8.60  77.19 1454  10834.48
c880  436645 55 44.10  3.50  19.39 505  2339.32
c1355  675703 138 31.24  5.70  26.98 616  8088.70
c1908  1269621 294 8.03 23.33 183.03 3407  19033.28
c2670  3904615 106 12.75 23.78 272.80 6499  19076.40
c3540  6402831 191 17.02 24.87 317.95 8525  48157.10
c5315 15100260 129 23.04 16.54 343.64 12016  81282.48
s208.1  27261 71 24.44  7.25  19.49 201  629.63
s298  47278 50 29.66  6.75  29.99 344  601.92
s344  59685 31 25.45  5.53  17.70 231  438.50
s349  61425 32 24.66  6.07  19.26 247  458.60
s382  66430 60 36.33  4.38  19.47 285  784.58
s386  114003 113 26.50  8.15  49.77 651  2601.15
s400  72771 67 36.85  4.70  21.19 311  972.48
s420 1  121771 162 21.14 34.42 136.90 1268  3939.57
s444  81003 63 35.82  6.41  30.18 408  959.17
s510  130816 85 52.04  5.36  31.60 496  2504.10
s526  152628 74 39.05  6.77  44.84 668  1992.52
s526n  152076 77 38.38  6.91  45.52 674  1994.15
s641  241860 90 12.12 16.34  63.26 832  1907.97
s713  285390 89 10.87 27.65 104.09 1285  2205.05
s820  419070 157 37.19 22.37 205.46 2606  11020.87
s832  435711 169 38.32 23.42 215.41 2723  12170.18
s838 1  513591 316 16.02 1778.78 5855.40 25851  25424.42
s953  380628 196 48.50  6.48  36.60 673  10865.93
s1196  793170 271 41.66  6.17  61.90 1427  20931.37
s1238  869221 275 46.70  9.03 108.71 2165  25430.28
s1423  1261666 89 27.77 14.57 144.49 2944  8129.83
s1488  1902225 206 25.25 25.71 305.76 5590  35314.48
s1494  1929630 201 25.80 25.60 306.18 5622  35710.35

Table 5: Test Generation Results for ALL TBFs

Circuit Size DR  ECS
c432 0.36 -0.14  0.00
c499 0.40 0.41  0.00
c880 0.38 0.27  -0.53
c1355 0.79 4.89  0.11
c1908 0.51 0.25  0.04
c2670 0.12 1.41  0.56
c3540 0.29 0.24  0.13
c5315 0.12 3.27  0.81
c6288 0.64 77.61 1503.58
c7552 0.21 1.89  0.41
s208.1 0.92 29.96 23.56
s298 0.57 -0.84  -0.02
s344 1.00 20.10  1.71
s349 0.85 34.74  8.86
s382 0.59 11.73  0.81
s386 0.36 7.26  2.95
s420 1 0.46 12.06 99.40
s444 0.70 9.75  0.83
s510 0.72 7.35  0.09
s526 0.42 7.02  2.02
s526n 0.42 9.15  2.72
s713 0.69 5.03  9.11
s820 0.35 6.99  0.67
s832 0.34 1.06  1.35
s838 1 0.25 1.06 161.87
s1423 0.51 3.84  2.17
s1488 0.35 5.75  1.06
s1494 0.31 7.05  1.21
s5378 0.39 3.56 25.37
s9234 0.40 1.93 109.02
AVE. 0.48 8.48 65.32

Table 6: Comparison of Diagnostic Test Generation with ATALANTA, for Metal-BFs

Circuit Size DR ECS
c432 0.69 2.10 0.60
c499 1.82 7.01 4.83
c880 0.56 5.10 0.93
c1355 1.39 4.33 4.35
c1908 2.01 1.73 16.83
c2670 0.34 6.71 72.99
c3540 0.84 1.80 5.34
s208.1 1.97 17.26 186.17
s298 1.35 4.09 2.24
s344 1.35 13.43 13.34
s349 1.19 16.81 43.62
s382 1.54 15.67 6.99
s386 1.41 6.56 15.50
s420 1 2.08 12.36 909.41
s444 1.70 11.13 6.43
s510 1.31 9.67 3.26
s526 1.00 16.01 96.07
526n 1.12 17.63 80.63
s713 1.62 4.09 70.98
s820 1.29 7.07 26.43
s832 1.32 7.63 41.91
s838 1 2.05 6.49
s1423 1.14 3.03 10.38
s1488 1.54 5.00 44.50
s1494 1.41 4.75 30.69
AVE. 1.31 7.97 65.77

Table 7: Comparison of Diagnostic Test Generation with ATALANTA, for Alll-BFs Figure 2: Example Illustrating UpdateEquivClass

21 IddqDiagSim /* Let {T_{1}, …, T_{N}} be the given diagnostic test set. */ BEGIN Compute P art(INIT) = {P 0}. /* It will contain only one partition pointed to by P 0 */ Set EC(INIT) to {< P 0, P 0 >}. SINGLETONS = 0; For each test T_{i} BEGIN P art(T_{i}) = UpdatePartition(P art(T_{i−1})); EC(T_{i}) = UpdateEquivClass(EC(T_{i−1})); Traverse EC(T_{i}) and delete ECs of size 1. When such an EC is deleted increment SIN-

GLETONS.

Release Space used by P art(T_{i−1}), EC(T_{i−1}). END Traverse EC(T_{N}) and compute DR, ERS, SD-ECS defined in section 1. The value of SIN-GLETONS have to be taken into account in this calculation. END(* IddqDiagSim *)

Figure 3: Outline of Diagnostic Simulation Figure 4: Example Illustrating UpdateEquivClass (Contd)

23 SGAIddqTestGen POPULATION[POPSIZE] of input vectors and their fitness values; BEGIN

Initialize Population(POPULATION); While ( Stopping Criteria is not satisfied ) BEGIN Iterate NUMGEN times BEGIN REPRODUCE(POPULATION); CROSSOVER(POPULATION); MUTATE(POPULATION); UPDATE BEST SOLUTION(POPULATION); END T_{i} = Best Vector; Compute EC(T_{i}); END

END(* SGAIddqTestGen *)

Figure 5: Outline of The Diagnostic Test Generator