M M Vaseekar
email: vaseekar@engr.siu.edu

Kumar S Tragoudas

S Chakravarty
email: sreejit.chakravarty@intel.com

R Jayabharathi
email: rathish.jayabharathi@intel.com

Implicit and Exact Path Delay Fault Grading in Sequential Circuits

1 The first path implicit and exact non-robust path delay fault grading technique for non-scan sequential circuits is presented. Non enumerative exact coverage is obtained, by allowing any latched error representing a delayed transition to propagate to a primary output with the support of other potentially latched errors. The generalized error propagation is done by symbolic simulation. Appropriate data structures for function manipulation are used. The advantage of the proposed method is demonstrated experimentally with consistent improvement in coverage over an existing pessimistic heuristic despite enforced bounds on the memory requirements.

Introduction

The need for verifying the temporal correctness of the manufactured circuit is ever increasing. The objective of delay testing is to detect timing defects which could degrade the performance of a circuit. The path delay fault (PDF) model is considered to be the most accurate and also the most appropriate delay model for testing delay defects in deep sub-micron technology. A PDF can be tested robustly, but in many circuits the majority of PDFs can only be sensitized non-robustly. We consider non-robust fault grading of PDFs in non-scan sequential circuits in this paper. The goal of fault grading is to determine the faults tested by a test set under a specific delay fault model. It is used to reduce the effort of the delay test generator as well as to indicate the completion of the test generation process by verifying that the desired coverage levels have been obtained.

Various techniques have been designed for PDF grading in combinational and sequential circuits. Most of the techniques assume that the flip-flops(FF) feeding the combinational part of the circuit are directly observable and controllable using full scan [START_REF] Gharaybeh | The path-status graph with application to delay fault simulation[END_REF][START_REF] Padmanaban | Exact Path Delay Fault Coverage with Fundamental Zero-Suppressed BDD Operations[END_REF]. These full-scan techniques require the usage of enhanced scan flip-flops which are excessively expensive in many circuit designs. For example, microprocessor testing is traditionally done without such DFT support. Area, performance and feasibility considerations may prevent the use of full scan. Furthermore, testing using full-scan, targets many sequentially untestable PDFs.

The fundamental difficulty in PDF testing of nonscan sequential circuits is associated with the propagation of latched errors (each representing a potentially delayed transition along a set of PDFs that end on the same flip-flop) to primary outputs(PO). Existing techniques introduce assumptions during the error propagation phase to simplify the process at the expense of pessimism in the grading process [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF][START_REF] Pomeranz | SPADES-ACE: A Simulator for Path Delay Faults in Sequential Circuits with Extensions to Arbitrary Clocking Schemes[END_REF][START_REF] Tekumalla | Identification of primitive faults in combinational and sequential circuits[END_REF]. The most restricted method allows for error propagation along a path as long as it does not depend on any other error captured in another flip-flop. This guarantees sequential robustness [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF]. A less restrictive sequentially non-robust approach assumes that only one error can be captured at a flip-flop during the PDF sensitization phase [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF]. We will consider this method for comparison in the rest of the paper. Figure 1 shows two robustly sensitized critical PDFs 1-2-4 and 1-3-5 latched as potentially delayed transitions at flip-flops 4 and 5. Even under the assumption that both paths are critical, with similar gate 1 delays, it cannot be guaranteed that when there is a delay fault in PDF 1-2-4, there will also be a delay fault in PDF 1-3-5. Furthermore, delays of the gates vary with different sensitizing patterns and also due to process variations in manufacturing. Therefore the latched value on the end flip-flop of each (critical) sensitizable path should be considered as a potential error that may or may not occur. In the proposed method there are no restrictions on the number of flip-flops that are allowed to have an error during the propagation phase. The method is also exact. The grading methods in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF] cannot handle this generalization unless the underlying grading algorithm is invoked an exponential number of times to the length of the error propagation subsequence.

Testing for delay faults can be done so that all patterns are applied at the rated clock (at-speed), (see [START_REF] Pomeranz | At-Speed Delay Testing of Synchronous Sequential Circuits[END_REF], among others) or using a variable clock method (see [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF][START_REF] Pomeranz | SPADES-ACE: A Simulator for Path Delay Faults in Sequential Circuits with Extensions to Arbitrary Clocking Schemes[END_REF], among others). The latter is a pessimistic method where only one pattern in the test sequence is applied at a rated clock and will be the approach followed in this paper. Let this pattern be p 2 and the predecessor pattern p 1 . The sub-sequence prior to pattern p 1 initializes the flip-flop in appropriate states. The slow application of p 1 allows for all signals to settle to an appropriate logic prior to the rated-clock application of p 2 . Delayed path propagations are then captured as errors on flip-flops or observed directly at the POs. The subsequence following pattern p 2 is subsequently applied with a slow clock to propagate any captured errors to POs. Any vector in this sub-sequence is called a propagation vector.

Our technique is based on the derivation of functions by symbolic simulation and their appropriate manipulation which ensures that any sensitized and observable PDF will be detected with or without the support of other latched error combinations representing potentially delayed transitions. Such functions essentially provide with parallelism of the traditional fault simulation procedure in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF]. This also eliminates the exponential time behavior of an exact grading simulation method based on the procedure in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF].

The formed functions, model the propagation of the delayed transitions from a flip-flop to another flipflop or PO. Their generation is independent to the number of PDFs. They are stored and manipulated using Binary Decision Diagrams (BDDs). In an initial step, the proposed non-enumerative PDF grading method uses the implicit technique in [START_REF] Padmanaban | Exact Path Delay Fault Coverage with Fundamental Zero-Suppressed BDD Operations[END_REF] for combinational circuits to store the PDFs that are sensitized during the rated clock phase in different ZBDDs. The distinction is made upon the ending flip-flop or PO on each sensitized PDF. That way, a latched error represents a set of implicitly stored PDFs. Subsequently the proposed fault grading method systematically and implicitly identifies whether a propagation vector v i , results to an error at any FF or PO denoted by F , and for each F determines which error prior to applying v i propagates to F . This is done with the help of the functions formed by symbolic simulation. Thus, if F is observable we are able to implicitly determine all PDFs propagating to it through the corresponding error.

This paper is organized as follows. Section 2 presents an overview of the symbolic simulation method required for the proposed fault grading technique. Subsequently, it outlines the fault grading methodology and illustrates it with an example. The methods are presented without explicit reference to the data structures that are used to represent the functions. Section 3 gives experimental results that demonstrate the need for an exact grading scheme. The improvement over existing heuristics is very significant for all benchmarks we experimented with. Section 4 concludes.

The proposed method 2.1 Overview

Let f j denote a flip-flop. Let d j be an error representing a potentially delayed rising transition and d j be an error representing a potentially delayed falling transition latched at f j at the end of the rated clock. The four different cases that may occur are shown in Table 1.

Table 1: Encoding delayed transitions value Good Faulty 0 0 0 1 1 1 dj 1 0 d j 0 1
The propagation of an error captured at a flip-flop (at the end of the respective sensitized PDF) is determined by symbolic simulation. Consider the application of the first propagation vector. Since an error at a flip-flop (encoding a delayed transition) may or may not occur, we maintain a variable f j at the output of the flip-flop f j to denote a d j error. Similarly a variable f j for a flip-flop f j denotes a d j error. Note that a variable is allowed to have any of the two assignments 0 or 1 and likewise an error may or may not occur. For convenience of representation, we use the same name for the flip-flop and its variable. We do a symbolic simulation and for each next-state flip-flop f x we obtain the function F x at its input. Thus F x will be a function of

(f 1 , f 2 , f 3 ). Assume that F x = f 1 .f 2 .f 3 + f 1 .f 3 .
We conclude that error d x is latched at f x either due to f 1 (in the first cube) or f 3 (in the second cube). This indicates the existence of a possible input assignment that could propagate both the errors latched at f 1 and f 3 , respectively to f x . The union of PDFs represented by d 1 and the PDFs by d 3 will yield the PDFs represented by error d x . We also conclude that error d x is latched either due to f 2 (in the first cube) or f 3 (in the first cube) or f 1 (in the second cube). Thus there exists a possible input configuration that could also bring a d x at f x . As far as PDF coverage linked to error d x we take the union of PDFs represented by d 2 , d 3 and d 1 . It should be noted that the set of PDFs represented by both d 1 and d 1 is the same. Then for the next slow clock propagation vector we will have both d x and d x in flip-flop f x for symbolic simulation.

f f 1 x f 3 f 2 d d' d 1 2 3 1 0 1 0 1 0 Good Value Faulty Value
Let F f1 x represent all the cubes that contain variable f 1 and F f3

x represent all the cubes that contain variable f 3 in F x . Functions F f2

x ,F

f 3 x , F f 1
x are derived similarly for error d x . Consider another flip-flop f y and without loss of generality assume that only error d y is latched. Error d y is the same as d x if and only if F f1 x = F f1 y and F f3 x = F f3 y , and, in addition, f 1 and f 3 must be the only variables that allow error d y . If this is the case, for the next slow clock propagation vector, d y is denoted as d x .

Likewise d y is the complement of d x if and only if F f2 y = F f2 x and F

f 3 y = F f 3
x and F

f 1 y = F f 1
x , and, in addition, f 2 , f 3 , f 1 are the only variables that allow error d y . If this is the case, for the next slow clock propagation vector, d y is denoted as d x . The above mentioned variable bindings are needed to ensure that the use of symbolic simulation during any propagation vector is correct and does not overestimate the coverage. It can be shown that the number of BDD operations required to determine all variable bindings prior to any symbolic simulation is in the order of O(F 3 ) where F is the num-ber of flip-flops. However, the procedure is much faster in practice.

The same process is followed for any subsequent propagation vector. A minor difference is that at the beginning of the simulation a flip-flop may have both errors latched. A flip-flop f i that has both errors d i and d i latched, is still treated as variable f i . Assume that after symbolic simulation we obtain function F x = f i (A) + f i (B). Then both d i and d i propagate due to d x and d x as long as either A or B is not N U LL. We calculate the PDFs covered under d x (respectively, d x ) as before, by taking the union of the PDFs in errors for d i (respectively, d i ) as depicted by variable f i .

Illustration

The grading method supports any number of initialization and propagation vectors provided that only one vector is applied at the rated clock to detect PDFs, and is illustrated with an example. For each propagation vector we show how to use symbolic simulation method to implicitly identify any detectable PDF. The example also shows that the approach in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF] is quite pessimistic.

Consider the circuit shown in the Figure 3. Assume a four vector sequence v1(1110000100), v2(0010000011), v3(1011100011), v4(1111100011) where v2 is applied at the rated clock, and v3, v4 are propagation vectors. Figure 3 shows the symbolic simulation values at different clocks, separated by commas. Testable PDFs are detected using vectors v1,v2 as in [START_REF] Padmanaban | Exact Path Delay Fault Coverage with Fundamental Zero-Suppressed BDD Operations[END_REF] and are stored as a ZBDD. PDFs ending in flip-flops are latched as errors representing potentially delayed transitions. Table 2 (left part under clock 2) shows the delayed transitions, and the PDFs represented by them in columns 1 -3. Symbols f (respectively, r ) denotes a falling transition (respectively, rising transition) on an edge of a PDF. Also note that all PDFs ending at the same flip-flop are represented by a symbol as shown in column 3 of Table 2. Let F k list be a list of symbols that represents all PDFs detected by v2 at flip-flop f k . For example the symbol P d 4 is listed in F f4 list instead of the ZBDD representation.

Vector v3 is applied with a slow third clock to propagate the set of latched errors {d Similarly F f 1 = f 1 and can latch d 1 . It can be seen that variable binding is not possible in this case as both F f 2 and F f 1 have different variables. The above mentioned activities are summarized in the right hand side of Table 2 (under clock3), columns 4-6, when applying the first propagation vector v 3 .

,0,1,1 1,1,1,1 1,0,0,1 1,0,1,1 0,1,1,1 0,0,0,0 0,0,0,0 21 1,0,0,0 0,0,1,1 0,1, 1 2 3 4 f f f f 3 4 0,0, 0,0, ,0 1,1,1,f' 1 2 +f' 1,0,1,d f' 1 ,0 19 d 1 ,d' 1 0,0,0, d' 2 0,0, d 3 ,1 0,1, 4 d' ,0 ,0 .f f' 1,1 1,0,0,0 0,1,1,1 0
This demonstrates the advantage of the method, as the existing non-robust model of [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF] could not have propagated either of the latched errors. This is because, the good machine value as considered in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF] at f 4 is 0 (f 3 is 1), which leads to a controlling value to the gate 20, thus in such cases there is a significant loss of fault coverage.

The procedure is repeated for v4 with variables {f 1 , f 2 } representing {d 1 , d 2 } respectively. It is observed that the function formed at PO is F 19 = f 1 +f 2 denoting a possibility of d 19 at PO due to f 1 or f 2 . Since PDFs corresponding to different delayed transitions are mutually exclusive, we work in an implicit manner and perform a union of PDFs represented in the F f1 list and F f2 list, which is a constant time operation. PDFs P d 4 ,P d 3 and P d 1 are covered by this test. Thus this method yields high coverage in testing non-scan sequential circuits by allowing delayed transitions to propagate to flip-flops in the presence of other potentially delayed transitions, non-robustly and non-enumeratively.

The fault grading algorithm

The procedure of the fault grading algorithm is given below. C is the circuit and t is the test set consisting of three types of vectors. Let t in denote the set of initialization vectors, t r the single activation vector and t p the set of propagation vectors, respectively. The initialization() function initializes the flipflops by simulating t in . The grading() function identifies the PDFs tested, with t r applied at the rated clock, as per [START_REF] Padmanaban | Exact Path Delay Fault Coverage with Fundamental Zero-Suppressed BDD Operations[END_REF]. PDFs ending at the PO are added to the ZBDD P DF s detected while those ending at flip-flop are stored as ZBDDs and added as symbols to their respective X list.

The cone() function returns the sub-circuit cone C sub with respect to X. Working with every output cone of the circuit reduces the complexity of the algorithm. The symbolic sim() function performs the symbolic simulation with the flip-flop variables and t pj and returns F a as explained in section 2.1 and 2.2 where a can be either X or X or both. The check propagation() function checks whether the d i or d i in f i propagates as d X or d X to X. If the latched d i or d i propagates to X then the binding() function checks for possible partial variable binding with previously computed d X or d X errors in the circuit C . At the end of the loop any possible variable binding is detected and the symbols are substituted.

If X is a flip-flop the update() function updates the X list with the PDFs in f i list. If X is a PO the PDFs in f i list are added to P DF s detected. The procedure is further simplified by updating the PDFs detected as a list of symbols, rather than a ZBDD and performing a final ZBDD Union operation, as no new PDFs are introduced in the propagation phase. The fault grading procedure ends when all the propagation vectors have been applied. This procedure is repeated for other test sets and P DF s detected is updated. The total number of PDFs stored in the P DF s detected will give the coverage of PDFs for the set of test patterns. The time complexity of the proposed algorithm is polynomial. The method is exact as it guarantees the detection of any sensitized PDFs, provided they are sensitized in only one clock.

Experimental Results

We present experimental results for the non-scan version of some ISCAS'89 and ITC'99 sequential circuits to demonstrate the enhancement in the fault coverage over the existing method in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF]. To ensure low memory requirements by the BDD structure, we implemented a restricted version of the proposed algorithm where flip-flops are greedily partitioned into sets of size utmost ten. The propagation of an error latched at flipflop f i in set A can only be assisted by errors on flipflops within set A . All other flip-flops that are not in set A are assigned error free good machine values. Thus very simple functions F x are formed and the approach can execute with less than 256 MB RAM. This however, may increase the execution time for some benchmarks because for each propagation vector we have to perform as many symbolic simulation as the number of sets. Note that the method in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF] requires O(F ) logic simulations per propagation vector where F is the number of flip-flops. The proposed grading tool has been implemented in the C language.

Two sets of experiments were performed on a 750MHz SunBlade 1000 workstation and are shown in Table 3. In all the experiments, the initial state of flipflops is assumed to be 0. In both experiments the PDFs are stored as ZBDDs. BDDs are used for generating the functions, determining variable binding and determining the propagation of latched delayed transitions.

The first set of experiments, listed in the left-hand side of Table 3 (columns 2 -6), are conducted considering three vector sequences for sequential grading. The first two vectors are obtained from function-based ATPGs [START_REF] Michael | ATPG for Path Delay Faults without Path Enumeration[END_REF][START_REF] Padmanaban | Using BDDs and ZBDDs for efficient identification of Testable Path Delay Faults[END_REF] for PDFs in combinational or full-scan circuits, and are used as the initialization and fault activation vectors in the sequence. The second vector is applied at the rated clock to sensitize the PDFs nonrobustly. Test sets for the first three circuits were derived from a compact ATPG [START_REF] Michael | ATPG for Path Delay Faults without Path Enumeration[END_REF]. As it was time consuming to derive test sets for larger circuits using [START_REF] Michael | ATPG for Path Delay Faults without Path Enumeration[END_REF], we used the ATPG from [START_REF] Padmanaban | Using BDDs and ZBDDs for efficient identification of Testable Path Delay Faults[END_REF], which is less compact. The last propagation vector which is applied at a slow clock is the same as the second vector of the ATPGs [START_REF] Michael | ATPG for Path Delay Faults without Path Enumeration[END_REF][START_REF] Padmanaban | Using BDDs and ZBDDs for efficient identification of Testable Path Delay Faults[END_REF]. The PDFs represented by the latched errors propagating to a primary output are immediately detected. The latched errors that propagate to next state flip-flops, by the third vector are assumed to be shifted out to an observable point, for determining the possible coverage. We experiment with such three vector sequences because we were unable to obtain the sequential ATPG tool in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF].

Column 1 of Table 3 gives the circuit names. Column 2 presents the number of test sets (each test set has three vectors). Column 3 and 4 compare the coverage of PDFs with the non-robust model of [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF]. The 5 th column shows the improvement in the coverage as a percentage. It can be observed that the proposed methodology yields a better coverage than [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF]. Often the improvement is very significant and over 20%. The results for s6669, s38417 and s38584 confirm the scalability and implicitness of the method. It also shows that the method can handle path intensive circuits. It should be noted that, though the percentage improvement is not so high in s38417 and s38584, the number of PDFs covered has significantly increased over the heuristic method. It is also important to note here that appropriately derived error propagation sequences (by a sequential ATPG for PDFs) could favor the presented method, and the improvement would have been more drastic, since they could allow for many errors to propagate to PO or flip-flop. Column 6 in Table 3 gives the execution time in seconds. The listed time includes the time for generating all the required functions, but most of the execution time is spent on the actual fault grading process.

The second set of experiments, listed in Table 3 from columns 7 -12, uses test sequences derived from a genetic algorithm based ATPG (GATTO) [START_REF] Corno | a genetic algorithm for automatic test pattern generation for large synchronous sequential circuits[END_REF] for stuck at faults in non-scan sequential circuits. The columns provide information similar to columns 2 -6. Each test sequence, which has n vectors, was repeatedly executed It is noted that the execution time for a single propagation vector is very low and experimentally confirms that the method is implicit and can handle any number of propagation vectors. The low PDF coverage in both experiments is attributed to the lack of compact and implicit sequential PDF ATPGs where each sequence detects many faults. Such tests would have also better shown the impact of the exact method over heuristic approaches. It is known that the listed benchmarks are not PDF testable by random pairs of vectors even in the presence of full scan. The fault coverage using randomly generated test sequences for sequential PDF testing results in very low coverage and analyzing such an experiment has little value. We were not able to access the sequential ATPG in [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF]. However, existing sequential PDF ATPGs are fault enumerative [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF]. Thus each generated test sequence targets only one PDF and incidentally may detect a few more, but the PDF coverage still remains low. Therefore, it is not expected that the impact of our exact method over heuristic grading methods [START_REF] Chakraborty | On Variable Clock Methods for Path Delay Testing of Sequential Circuits[END_REF][START_REF] Pomeranz | SPADES-ACE: A Simulator for Path Delay Faults in Sequential Circuits with Extensions to Arbitrary Clocking Schemes[END_REF] will be greater (than what is shown here) when experimenting with sequences from such tools.

Conclusions

We propose the first method for exact path delay fault grading in non-scan sequential circuits using a variable clock. The propagation of captured errors that repre-sent delayed transitions, which has been treated in a pessimistic manner by previous approaches, is handled accurately using functions. ZBBDs and BDDs are used to store PDFs compactly and manipulate functions, respectively. Experimental results show that the fault coverage is significantly increased over existing heuristic approaches.

Figure 1 :

 1 Figure 1: Multiple latching of PDFs

  Consider a portion of the circuit as shown in Figure 2. Let f 1 , f 2 , f 3 be three input flip-flops, and f x be the next-state flip-flop. Now assume that errors d 1 , d 2 , d 3 are present at the beginning of the slow clock.

Figure 2 :

 2 Figure 2: Example

  1 , d 3 , d 4 }. To determine the propagation of these errors, we perform a symbolic simulation with the corresponding variables {f 1 , f 3 , f 4 }, and v3. The function F f 2 is f 3 .f 4 . Thus at the end of the third clock errors d 3 and d 4 propagate to flip-flop f 2 and will be represented by error d 2 for symbolic simulation purposes when considering propagation vector v4 later. It is important to note that since both d 3 and d 4 propagate to the same output, a set union operation of the PDFs corresponding to these errors will yield the PDFs covered by both. Thus F f2 list

Figure 3 :

 3 Figure 3: PDF grading

n

  times. Each time a different vector served as the fault activation vector. The vectors applied before the activation initialize the states of the flip-flops and the vectors applied after the activation vector propagate the captured delayed transitions to an output. Thus each test set would have a varying number of initialization and propagation vectors. The total number of such test sets are reported in column 7. The average number of propagation vectors per test set are reported in column 11, and column 12 gives the execution time taking into account all the propagation vectors for the entire test set.

Table 2 :

 2 Delayed transitions and PDFs

			Clock2			Clock3
		Delayed transition PDFs represented Symbol	Delayed transition PDFs represented Symbol
		d1	2f -12r	P d1	d 1	2f -12r	P d1
		d3	8f -18r	P d3
						9r -16r -21f,	P d3
			9r -16r -21f,	P d 4		10r -16r -21f,	+P d 4
		d 4	10r -16r -21f,		d 2	8f -18r -21f,
			8f -18r -21f			8f -18r
			19
		13
		17
			20
		14
		15	18
	0,1,	16

Table 3 :

 3 Result PDF grading

			Single Propagation Vector using ATPG [5, 6]				Multiple Propagation Vectors using ATPG [2]
	Benchmarks	Test Sets	Coverage	Exact Coverage	Improvement	Execution	Test Sets	Coverage	Exact Coverage	Improvement	Average #	Execution
			[3]	(proposed)	(%)	Time (sec)		[3]	(proposed)	(%)	Propagation Vectors	Time(sec)
	s641	947	1794	2039	13.65	10.54	265	366	401	9.56	11	2.16
	s713	403	2429	3078	26.72	4.57	265	414	463	11.83	14	2.08
	s820	753	883	968	9.62	2.25	240	192	215	11.98	19	1.56
	s1269	10182	7125	8017	12.52	31.02	422	2888	4196	45.29	16	18.64
	s3271	7707	2508	2807	11.92	15.23	1424	6634	9958	50.11	18	373.58
	s6669	115272	280377	341677	20.71	913.36	438	104738	144907	38.35	15	383.01
	s38417	39799	76451	81073	6.05	1583.20	704	7911	10718	35.48	21	6607.60
	s38584	92239	90163	99533	10.39	2676.16	1266	14422	16294	12.98	19	4593.99
	b03	1244	988	1213	22.77	6.95	151	163	198	21.47	10	1.35
	b04	6152	5702	6078	6.59	14.32	627	6059	6537	7.89	18	36.86
	b09	1058	1048	1392	32.82	7.47	456	211	243	15.16	21	10.77
	b10	831	676	828	22.48	1.16	467	342	383	11.98	16	4.51
	b11	3689	3310	3725	12.53	28.99	467	660	830	25.75	22	23.83
	b12	6152	10025	10783	7.56	91.79	254	247	324	16.42	20	2.08

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

 [START_REF] Bryant | Graph-based algorithms for boolean function manipulation[END_REF]This research is supported in part by a grant from Intel Corp.


Irith Pomeranz

Sudhakar M Reddy

The Accidental Detection Index as a Fault Ordering Heuristic for Full-Scan Circuits

We investigate a new fault ordering heuristic for test generation in full-scan circuits. The heuristic is referred to as the accidental detection index. It associates a value ADI (f ) with every circuit fault f . The heuristic estimates the number of faults that will be detected by a test generated for f . Fault ordering is done such that a fault with a higher accidental detection index appears earlier in the ordered fault set and targeted earlier during test generation. This order is effective for generating compact test sets, and for obtaining a test set with a steep fault coverage curve. Such a test set has several applications. We present experimental results to demonstrate the effectiveness of the heuristic.

Introduction

Dynamic test compaction procedures for full-scan circuits [START_REF] Goel | Test Generation & Dynamic Compaction of Tests[END_REF]- [START_REF] Hamazaoglu | Test Set Compaction Algorithms for Combinational Circuits[END_REF] typically attempt to generate test vectors that detect as many faults as possible. In this way they reduce the number of test vectors required for detecting all the detectable circuit faults. Dynamic compaction heuristics added to a test generation procedure typically increase the test generation time significantly, to several times the original run time of the test generation procedure without the dynamic compaction heuristics. Some of the dynamic test compaction heuristics can be expected to increase the run time. For example, using the unspecified values of a test vector to detect secondary target faults [START_REF] Goel | Test Generation & Dynamic Compaction of Tests[END_REF] implies that in the worst case, for a circuit with n faults, there will be O (n ) test generation attempts for every vector instead of a single attempt when secondary target faults are not used. Other dynamic compaction heuristics do not increase the worst-case complexity of test generation. One such heuristic is fault ordering. Under a fault ordering heuristic, the faults are placed in the set of target faults F in a certain order, and the test generation procedure considers the faults in the order they appear in F . For example, in [START_REF] Pomeranz | COMPAC-TEST: A Method to Generate Compact Test Sets for Combinational Circuits[END_REF], the fault ordering heuristic uses maximal sets of independent faults in fanout free regions [START_REF] Akers | On the Role of Independent Fault Sets in the Generation of Minimal Test Sets[END_REF]. Faults in larger sets are placed at the beginning of F to ensure that the first tests generated are necessary for detecting all the faults.

In this work we investigate a new fault ordering heuristic. We refer to the heuristic as the accidental detection index. An accidental detection index is associated with every circuit fault f , and it estimates the number of faults that will be detected by a test generated for f . This has several applications.

(1) For dynamic test compaction, a fault with a higher accidental detection index should be targeted earlier in order to ensure that each new test vector added to the test set detects as many faults as possible. Similar to other dynamic compaction heuristics, this reduces the final test set size.

(2) The procedures of [START_REF] Jiang | Defect-Oriented Test Scheduling[END_REF] and [START_REF] Lin | On Static Test Compaction and Test Pattern Ordering for Scan Designs[END_REF] reorder a test set so as to obtain a fault (or defect) coverage curve which is as steep as possible. With every additional test, a steeper fault coverage curve has a higher fault coverage. The motivation for studying this problem is as follows. The reordered test set is useful if the test set is too large to fit in the tester memory and it is necessary to remove some tests in order to avoid multiple loads of the tester memory. Removing the last tests of a reordered test set with a steeper fault coverage curve reduces the fault coverage by a smaller amount. Similarly, removing the last tests of a reordered test set can be used to reduce the test application time while minimally reducing the fault coverage. In addition, with a reordered test set, more defects are expected to be detected by the earlier tests. Thus, an appropriate reordering of the test set reduces the time a defective chip is expected to spend on a tester until the defect is detected. The method of [START_REF] Jiang | Defect-Oriented Test Scheduling[END_REF] reorders the test set based on aposteriori probabilities for tests in the test set to detect defective chips. The method of [START_REF] Lin | On Static Test Compaction and Test Pattern Ordering for Scan Designs[END_REF] uses the results of ndetection fault simulation, and does not require any aposteriori information. Using the method of [START_REF] Lin | On Static Test Compaction and Test Pattern Ordering for Scan Designs[END_REF], tests that detect larger numbers of faults appear earlier in the reordered test set, satisfying the requirement for a steep fault coverage curve. If test generation is performed such that faults with a higher accidental detection index are targeted earlier, a steeper fault coverage curve is expected even without reordering the test set. In addition, the test vectors obtained in this way are expected to be more effective in obtaining a steeper fault coverage curve than test vectors obtained without the accidental detection index heuristic.

In this work we compute the accidental detection index based on a given set of input vectors U (a small set of random vectors that detects a certain percentage of the circuit faults). We order the set of faults including the faults detected by U . In other words, we do not drop the faults detected by U from the set of target faults F . This is done for the following reasons. First, most of the test generation effort is expended for the detection of hard-todetect faults, which are not detected by U . Thus, dropping the faults detected by U from F is not likely to reduce the test generation time. Second, a test for a fault with a high accidental detection index that is detected by U may accidentally detect a hard-to-detect fault and save the test generation effort otherwise required to detect it. More important, random input vectors are not desirable if the goal is to generate a compact test set or achieve a steep fault coverage curve. To achieve these goals it is better to perform test generation considering all the target faults.

Fault ordering was considered earlier in [START_REF] Cabodi | Fast Differential Fault Simulation by Dynamic Fault Ordering[END_REF]- [START_REF] Krauss | Efficient Fault Ordering for Automatic Test Pattern Generation for Sequential Circuits[END_REF]. In [START_REF] Cabodi | Fast Differential Fault Simulation by Dynamic Fault Ordering[END_REF] and [START_REF] Lee | HOPE: An Efficient Parallel Fault Simulator for Synchronous Sequential Circuits[END_REF], fault ordering is done to speed up fault simulation of synchronous sequential circuits by grouping together faults that cause similar events. Here, we are not concerned with the events that a fault causes during fault simulation. In [START_REF] Krauss | Efficient Fault Ordering for Automatic Test Pattern Generation for Sequential Circuits[END_REF], fault ordering is done to support the generation of compact test sequences for synchronous sequential circuits by targeting hard-to-detect faults first. The accidental detection index defined here addresses more directly the issue of identifying faults whose tests will detect large numbers of other faults. These may or may not be hard-to-detect faults. Moreover, for the application of steepening the fault coverage curve, we prefer to place the hard-to-detect faults (the faults not detected by U ) at the end of the ordered set of faults since their accidental detection index is unknown and may be low.

The paper is organized as follows. In Section 2 we define the accidental detection index. In Section 3 we discuss fault ordering based on the accidental detection index. In Section 4 we present the results of test generation using the fault orders of Section 3. We consider the two applications of dynamic test compaction and generation of test sets with steep fault coverage curves.

Accidental detection index

In this section we define the accidental detection index ADI (f ) for a fault f and provide a method for estimating its value.

The accidental detection index of a fault f is defined so as to capture the number of faults that will be detected by a test vector generated for f . Except for f , all the other faults detected by the test vector are detected accidentally. Since f may have several test vectors, a conservative definition of the accidental detection index of a fault f considers the minimum number of faults that will be detected by a test vector generated for f . It is also possible to use the average value, where the average is computed over all the test vectors that detect f . We take the conservative approach and define the accidental detection index of a fault f as the minimum number of faults that will be detected by a test generated for f .

Computation of the exact value of the accidental detection index of a fault f will have a high computational complexity. In this work, we compute an estimate for the accidental detection index based on a set of input vectors U . In our experiments, U is a set of random vectors of limited size N . We discuss the selection of N later.

We denote by F the set of target faults (single stuck-at faults in our case). We denote by F U the subset of F detected by U . We compute an accidental detection index ADI (f ) only for a fault f ∈ F U , i.e., only for faults detected by U . For a fault f ∈ F -F U that is not detected by U the accidental detection index is by definition zero, i.e., ADI (f ) = 0 for f ∈ F -F U . For f ∈ F U , we include f itself in the count of faults for the accidental detection index. Therefore, ADI (f ) ≥ 1 for every f ∈ F U .

In order to compute ADI (f ) for f ∈ F U , we simulate the faults in F U under U without fault dropping and find for every fault f ∈ F U the subset of input vectors D (f ) ⊆ U that detect f . In addition, we find for every input vector u ∈ U the number of faults detected by u . This number is denoted by n det (u ). Instead of fault simulation without fault dropping it is also possible to use ndetection fault simulation to estimate n det (u ) for every u .

Let D (f ) = {u 1 ,u 2 , . . . ,u m }. For every u i ∈ D (f ) we have the number n det (u i ) of faults that will be detected if u i is generated for detecting f . The minimum value of n det (u i ) over all u i ∈ D (f ) is an estimate of the minimum number of faults that will be detected accidentally by a test generated for f . We use this value as the accidental detection index of f , i.e., we set

ADI (f ) = min{n det (u i ):u i ∈ D (f )} for f ∈ F U .
The following example demonstrates this definition. We consider the combinational logic of MCNC finite-state machine benchmark lion . The circuit has four inputs and 40 single stuck-at faults included in the set of target faults F . We include all the 16 input vectors of the circuit in the set U . All the faults in F are detected by U and included in F U . The input vectors in U detect the numbers of faults shown in Table 1. For every u ∈ U we show in Table 1 the value of n det (u ). The vector u is given by its decimal representation.

Next, we consider several of the faults of lion and compute for them the accidental detection index ADI (f ). The fault f 0 is detected by the set of input vectors D (f 0 ) = {9, 10, 11, 12, 13, 14, 15}. The smallest value of n det (u ), where u ∈ D (f 0 ), is obtained for u = 11, and it is equal to 7. This value implies that in the worst case, a test generated for f 0 will detect seven faults. The best case is if u = 13 is generated and detects 14 faults. However, we use the smallest value as the accidental detection index and set ADI (f 0 ) = 7.

The fault f 2 is detected by the set of input vectors D (f 2 ) = {4, 7, 13}. The smallest value of n det (u ) is obtained for u = 4, and it is equal to 12. This value implies that in the worst case, a test generated for f 2 will detect 12 faults. We obtain ADI (f 2 ) = 12.

The fault f 15 is detected by the set of input vectors D (f 15 ) = {10, 14, 15}. All three input vectors have the same value of n det (u ), equal to eight. Therefore, ADI (f 15 ) = 8.

Ordering the set of target faults

The accidental detection index is incorporated into the test generation process by ordering the set of target faults before test generation starts. We describe two pairs of fault orders based on the accidental detection index in this section. The first order in every pair is more suitable for the application of steepening the fault coverage curve. The second order in every pair is more suitable for dynamic test compaction. We also describe two orders that be used later for comparison purposes.

From the definition of the accidental detection index, a test for a fault with a higher accidental detection index will detect more faults accidentally than a test for a fault with a lower accidental detection index. Consequently, it is expected that the test generation process will be improved if the faults are ordered by decreasing value of ADI (f ) such that faults with higher accidental detection indices appear earlier. We denote by

F decr = <f 1 ,f 2 , . . . ,f n > the set of faults F reordered such that ADI (f i ) > ADI (f j ) for every 1 ≤ i < j ≤ n .
We note that, in this work, the accidental detection indices are computed based on a set of input vectors U that may not detect all the circuit faults. A fault f that is not detected by U is assigned ADI (f ) = 0. We can treat the faults with ADI (f ) = 0 in one of two ways. Since we cannot obtain a higher estimate of ADI (f ) from U , we can assume that the ability of a test for f to accidentally detect other faults is low and keep f at the end of the fault set. This is the approach taken in defining F decr . A different approach is to place faults with ADI (f ) = 0 at the beginning of the fault set since they are hard-to-detect, and they are not likely to be accidentally detected by tests for other faults. Consequently, it may be advantageous to target them first. To accommodate this view we define an ordered fault set, denoted by F 0decr , that includes the faults with zero accidental detection indices first, followed by the remaining faults in order of decreasing accidental detection index. The only difference between F decr and F 0decr is that in F decr the faults with ADI (f ) = 0 appear at the end, while in F 0decr they appear at the beginning.

We point out that some of the faults with ADI (f ) = 0 may be undetectable. For undetectable faults, their placement in the ordered fault set will not affect the test set size or the steepness of the fault coverage curve. Thus, we do not expect a difference between F decr and F 0decr when the limited set of input vectors U detects all the detectable circuit faults. When detectable faults have ADI (f ) = 0, we expect F decr to yield a steeper fault coverage curve than F 0decr since it follows more closely the accidental detection indices. We expect F 0decr to yield a smaller test set since it first generates tests for the faults that are not likely to be accidentally detected by tests for other faults. Depending on the application, either F decr or F 0decr should be used.

A dynamic ordering procedure will update the values of n det (u ) and ADI (f ) as faults are included in the ordered fault set. This will imitate the detection of faults by the test generation procedure when it considers the ordered fault set. We denote the resulting ordered fault sets by F dynm and F 0dynm (since values of n det (u ) and ADI (f ) are updated dynamically during the ordering process). We demonstrate the construction of F dynm next by considering MCNC finite-state machine benchmark lion . The values of n det (u ) for this circuit are shown in Table 1.

Initially, F dynm = φ. The highest accidental detection index is obtained for f 22 with D (f 22 ) = {7} and ADI (f 22 ) = 15. We therefore include f 22 in F dynm first to obtain F dynm = <f 22 >. The value of n det [START_REF] Lin | On Static Test Compaction and Test Pattern Ordering for Scan Designs[END_REF] for input vector 7 can now be reduced by one, since f 22 does not need to be considered further. In general, we do not attempt to estimate which other faults will be detected by a test for a fault f , since this depends on the particular test generated for f . We only assume that f will be dropped from the set of target faults after it is considered, and we update the values of n det (u ) for every u ∈ D (f ). Following this we also update the value of ADI (f ˆ) for every f ˆ∈ F -F dynm .

The highest accidental detection index for lion is now obtained for f 18 with D (f 18 ) = {7, 13} and ADI (f 18 ) = 14. We include f 18 in F dynm to obtain F dynm = <f 22 ,f 18 >. The values of n det [START_REF] Lin | On Static Test Compaction and Test Pattern Ordering for Scan Designs[END_REF] and n det (13) for input vectors 7 and 13 are reduced by one since f 18 does not need to be considered further.

The highest accidental detection index is now obtained for f 14 with D (f 14 ) = {2} and ADI (f 14 ) = 13. We include f 14 in F dynm to obtain F dynm = <f 22 ,f 18 ,f 14 >. The value of n det (2) is reduced by one since f 14 does not need to be considered further.

The highest accidental detection index is now obtained for f 21 with D (f 21 ) = {7, 13} and ADI (f 21 ) = 13. Here it is important to note that the original value of ADI (f 21 ) was 14, since n det [START_REF] Lin | On Static Test Compaction and Test Pattern Ordering for Scan Designs[END_REF] was originally 15 and n det (13) was originally 14. However, after f 22 was entered into F dynm , n det [START_REF] Lin | On Static Test Compaction and Test Pattern Ordering for Scan Designs[END_REF] was reduced to 14, and after f 18 was entered into F dynm both values were reduced to 13, resulting in ADI (f 21 ) = 13. We include f 21 in F dynm to obtain F dynm = <f 22 ,f 18 ,f 14 ,f 21 >. The values of n det [START_REF] Lin | On Static Test Compaction and Test Pattern Ordering for Scan Designs[END_REF] and n det (13) are reduced by one.

Continuing in the same manner, we obtain an ordered fault set that takes into account the changes in ADI (f ) as faults are considered during test generation.

If the circuit has faults with ADI (f ) = 0, we include them in F dynm at the end following the same process. We also define an ordered fault set F 0dynm , that includes the faults with ADI (f ) = 0 first. We then follow the procedure demonstrated above to determine the order of the remaining faults in F 0dynm . Similar to the case of F decr and F 0decr , when detectable faults have ADI (f ) = 0, we expect F dynm to yield a steeper fault coverage curve than F 0dynm since it follows more closely the accidental detection indices. We expect F 0dynm to yield a smaller test set since it first tests for the faults that are not likely to be accidentally detected.

For comparison purposes we also define the ordered fault set F orig , where the faults are listed in their original order (given as part of the circuit description). In addition, we define the ordered fault set F incr 0 where the faults with ADI (f ) > 0 are ordered by increasing accidental detection index, and the faults with ADI (f ) = 0 are placed at the end. This fault order is expected to yield the worst results in terms of test set size. We confirm this point experimentally as another indication of the effectiveness of the accidental detection index.

Experimental results

In this section we present experimental results of test generation with different fault orders. The test generation procedure we use does not include any dynamic compaction heuristics. We denote an ordered fault set by F ord . This can be F orig , F incr 0 , F decr , F 0decr , F dynm , or F 0dynm . We denote the test set computed for F ord by T ord .

The circuits we consider are the combinational logic of ISCAS-89 and ITC-99 benchmarks. For ISCAS-89 benchmarks we consider irredundant versions of their combinational logic, referred to as ircirc where circ is the original circuit name.

The set of input vectors U for the computation of the accidental detection indices consists of N random input vectors, where N is selected as follows. We initially include in U 10,000 random input vectors. This is sufficient for achieving a high fault coverage for all the circuits considered. We simulate U with fault dropping until all the vectors are simulated, or until approximately 90% of the circuit faults are detected. If this happens after N vectors are simulated, we keep in U only the first N vectors. This ensures that accidental detection indices are computed for a sufficiently large percentage of the faults. At the same time, it typically does not take a large number of input vectors to reach 90% fault coverage in the circuits considered. Consequently, the accidental detection index can be computed efficiently. The process can be speeded up further by removing from consideration vectors in U that do not detect any new faults during fault simulation with fault dropping of U .

The accidental detection indices are shown in Table 4. The results relevant to dynamic test compaction are reported in Table 5. Run times are reported in Table 6. In Figure 1 and Table 7 we provide results for the application of steepening the fault coverage curve. In Table 4, after the circuit name we show the number of inputs, and the number of random input vectors included in U . Under column ADI we show the value of ADI min = min{ADI (f ):f ∈ F U }, the value of ADI max = max{ADI (f ):f ∈ F U }, and the ratio ADI max /ADI min . For the faults left undetected by U , the accidental detection index is zero by definition. The minimum and maximum accidental detection indices are computed considering only detected faults.

It can be seen from Table 4 that the differences between the smallest and the largest accidental detection indices are significant. Therefore, the accidental detection index is expected to make a difference in the test set size and in the steepness of the fault coverage curve if used as a fault ordering heuristic.

In Table 5 we show the results of test generation using F orig , F dynm , F 0dynm and F incr 0 . We consider F orig and F incr 0 (for some of the circuits) for comparison purposes. We do not consider F decr and F 0decr since F dynm and F 0dynm proved to be better. We show the test set sizes for the different ordered fault sets under columns orig , dynm , 0dynm and incr 0, respectively.

From Table 5 it can be seen that both F dynm and F 0dynm reduce the test set size compared to using F orig . Using F incr 0 increases the test set size. This supports the effectiveness of the accidental detection index and the ordering of faults by decreasing values of the index. Using F 0dynm results in the smallest test sets overall. This is due to the fact that hard-to-detect faults (faults with ADI (f ) = 0) are placed first in F 0dynm . We expect F dynm to provide a steeper fault coverage curve if the faults with ADI (f ) = 0 do not have high accidental detection indices. The results reported later address this point.

Next, we report the effect of fault ordering on the run times of test generation as follows. Let the test generation time for an ordered fault set F ord be RT ord . We report the relative run times RT ord /RT orig for F orig , F dynm and F 0dynm in Table 6.

From Table 6 it can be seen that the test generation time for F dynm is between 0.45 and 2.21 times the run time for F orig , while for F 0dynm it is between 0.53 and 1.96 times the run time for F orig . The average run times are 1.14 and 0.98 of the run time for F orig , respectively. In many cases the run time for F dynm and F 0dynm is reduced compared to that obtained for F orig . This is an advantage compared to other dynamic compaction heuristics [START_REF] Goel | Test Generation & Dynamic Compaction of Tests[END_REF]- [START_REF] Hamazaoglu | Test Set Compaction Algorithms for Combinational Circuits[END_REF] that typically increase the run time significantly. To demonstrate the effect of fault ordering on the steepness of the fault coverage curve, we plot the increase in fault coverage as the number of test vectors increases during test generation for irs 420. We use the three ordered fault sets, F orig (for which the data points are given by o 's), F dynm (for which the data points are given by d 's) and F 0dynm (for which the data points are given by z 's). The curve obtained for irs 420 is shown in Figure 1. The x-axis is the number of tests as a percentage of the largest test set size. The y-axis is the fault coverage. In order to provide results for additional circuits in a concise way we compute the expected value of the number of tests that need to be applied in order to detect a faulty chip. This parameter is related to the steepness of the fault coverage curve as follows. With a steeper curve, the average number of tests it takes to detect a fault is lower. As a result, faults (and defects) are detected earlier during the test application process.

Let T ord = <t ord 1 ,t ord 2 , . . . ,t ordk ord >. Let the number of faults detected by <t ord 1 ,t ord 2 , . . . ,t ordi > be n ord (i ) (the values of n ord (i ) are used for plotting the fault coverage curve in Figure 1). We have n ord [START_REF] Goel | Test Generation & Dynamic Compaction of Tests[END_REF] faults detected after the application of a single test, n ord (2)-n ord (1) faults detected after the application of two tests, and so on. By defining n ord (0) = 0, we have that n ord (i )-n ord (i -1) faults are detected after the application of i tests, for 1 ≤ i ≤ k . The average number of tests that need to be applied for a fault to be detected is defined as

AVE ord = n ord (k ord ) Σi=1 k ord i . [n ord (i )-n ord (i -1)] .
In From Figure 1 and Table 7 it can be seen that in most of the cases considered, the fault coverage curve obtained for F dynm is steeper than the other two even though the size of the test set obtained for F 0dynm is smaller. The curve for irs 420 demonstrates a case where placing the faults with ADI (f ) = 0 (the faults that are undetected by U ) at the beginning of F 0dynm causes fewer accidental detections to be obtained for the first few test vectors than when these faults are placed at the end as in F dynm , or when they are placed arbitrarily as in F orig . The last row of Table 7 shows that, on the average, the expected value of the number of tests applied before a faulty chip is detected is reduced by 13% when the ordered fault set F dynm is used.

Concluding remarks

We defined the accidental detection index ADI (f ) of a fault f as the minimum number of faults that will be detected by a test generated for f . We provided a method for computing an estimate of the accidental detection index based on the results of simulating a set of input vectors U . We used the accidental detection index to order the set of target faults before starting test generation. Fault ordering was done such that a fault with a higher accidental detection index appeared earlier in the ordered fault set. The ordered fault set was shown to be effective for dynamic test compaction, and for obtaining a test set with a steep fault coverage curve. For the application of dynamic test compaction it was shown that it is better to place faults with ADI (f ) = 0 at the beginning of the ordered set of faults, and order the remaining faults by decreasing accidental detection index. For the application of steepening the fault coverage curve it was shown that it is better to order all the faults by decreasing accidental detection index, placing faults with ADI (f ) = 0 at the end of the ordered set.

  oo o o oo oo oo oo oo oo oo oo o oo oo o oo oo oo oo o d d dd dd dd dd dd dd dd dd dd dd dd d dd dd dd dd dd d z z zz z zz z z zz zz z zz zz zz zz zz z

Figure 1 :

 1 Figure 1: Fault coverage curve for irs420In order to provide results for additional circuits in a concise way we compute the expected value of the number of tests that need to be applied in order to detect a faulty chip. This parameter is related to the steepness of the fault coverage curve as follows. With a steeper curve, the average number of tests it takes to detect a fault is lower. As a result, faults (and defects) are detected earlier during the test application process.

Table 1 : Input vectors of lion

 1

	u	0	1	2	3	4	5	6	7
	n det (u )	11	11	13	13	12	11	11	15
	u	8	9	10 11 12 13 14 15
	n det (u )	11	11	8	7	11	14	8	8

Table 4 : Accidental detection index

 4

	ADI

Table 5 : Test generation

 5

			tests
	circuit	orig	dynm	0dynm incr0
	irs208	42	33	34	41
	irs298	43	36	37	43
	irs344	28	26	25	31
	irs382	42	45	35	47
	irs400	37	37	35	44
	irs420	70	62	60	71
	irs510	65	67	66	74
	irs526	75	74	64	86
	irs641	74	66	59	77
	irs820	149	130	125	179
	irs953	110	106	99	120
	irs1196	179	162	153	209
	irs5378	254	240	224	-
	irs13207	411	397	342	-
	average	112.8	105.8	97.0	-

Table 6 : Relative run times

 6

			t.gen
	circuit	orig	dynm 0dynm
	irs208	1.00	1.18	0.76
	irs420	1.00	1.88	1.10
	irs510	1.00	1.06	0.77
	irs641	1.00	0.96	1.27
	irs820	1.00	0.68	0.73
	irs953	1.00	1.03	0.93
	irs1196	1.00	2.21	1.96
	irs5378	1.00	0.45	0.53
	irs13207 1.00	0.83	0.78
	average	1.00	1.14	0.98

Table 7 : Steepness of fault coverage curves

 7 Table 7 we report the values of AVE ord normalized to AVE orig , i.e., we show the values of AVE ord /AVE orig for F orig , F dynm and F 0dynm . A lower value in Table 7 implies a steeper fault coverage curve, where a fault is expected to be detected earlier during the test application process.

			AVEord
	circuit	orig	dynm	0dynm
	irs208	1.000	0.644	0.833
	irs298	1.000	0.796	0.870
	irs344	1.000	1.023	0.853
	irs382	1.000	1.081	0.918
	irs400	1.000	0.963	0.973
	irs420	1.000	0.614	0.894
	irs510	1.000	0.834	0.895
	irs526	1.000	0.964	0.957
	irs641	1.000	0.830	0.807
	irs820	1.000	0.825	0.875
	irs953	1.000	0.998	1.191
	irs1196	1.000	0.790	0.868
	irs5378	1.000	0.865	0.873
	irs13207 1.000	0.960	0.767
	average	1.000	0.870	0.898

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

1. Research supported in part by SRC Grant No. 2004-TJ-1244. 2. Research supported in part by SRC Grant No. 2004-TJ-1243.


Raja K K R Sandireddy

Vishwani D Agrawal
email: vagrawal@eng.auburn.edu

Diagnostic and Detection Fault Collapsing for Multiple Output Circuits

We discuss fault equivalence and dominance relations for multiple output combinational circuits. The conventional definition for equivalence says that "Two faults are equivalent if and only if the corresponding faulty circuits have identical output functions". This definition, which is based on indistinguishability of the faults, is extended for multiple output circuits as "Two faults of a Boolean circuit are equivalent if and only if the pair of the output functions is identical at each output of the circuit". This is termed as diagnostic equivalence in this paper. "If all tests that detect a fault also detect another fault, not necessarily on the same output, then the two faults are called detection equivalent". Two detection equivalent faults need not be indistinguishable. The definitions for fault dominance follow on similar lines. A novel algorithm based on redundancy identification has been proposed to find the equivalence and dominance collapsed sets based on diagnostic and detection collapsing. Applying the algorithm to a 4-bit ALU would collapse the total fault set of 502 faults to 253 and 155, respectively, according to diagnostic equivalence and dominance. The collapsed sets have 234 and 92 faults, respectively, for detection equivalence and dominance. In comparison, the traditional structural equivalence and dominance collapsing results in 301 and 248 faults, respectively. Finally, we use library-based functional collapsing in a hierarchical system and find that smaller fault sets are obtained with an order of magnitude reduction in CPU time for very large circuits.

Introduction

The classical definition of equivalence says, "two faults are equivalent if and only if the corresponding faulty circuits have identical output functions". Equivalent faults are indistinguishable because they cannot be isolated from each other at the primary outputs by any input vector. Fault equivalence can be classified as structural equivalence and functional equivalence. Structural equivalence is identifiable from the circuit graph or structure. For example, all single stuck-at-1 (s-a-1) faults on the inputs and output of an OR gate are structurally equivalent. Functional equivalences involve circuits consisting of multiple gates.

Another form of collapsing that can further reduce the fault set size is dominance fault collapsing. A fault, all of whose tests detect some other fault, is said to be dominated by the other fault. For an OR gate, the output stuck-at-0 (s-a-0) fault dominates a single s-a-0 fault on any input. In the equivalence collapsed set, when a fault is not detected, the status of the entire set of faults that is equivalent to it is known. Such is not the case in the dominance collapsed set [START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits[END_REF]. Still there are advantages of using the latter for ATPG. Structural fault collapsing alone can reduce the fault set size to about 40 to 60% of all faults. Most ATPG programs use only structural equivalence fault collapsing. The Fastest program, developed at the University of Wisconsin, can do both equivalence and dominance fault collapsing, but it does only structural collapsing [START_REF] Kelsey | An efficient Algorithm for Sequential Circuit Test Generation[END_REF].

In Section 2, we discuss the background and previous contributions to fault collapsing. In Section 3, the conventional definitions of equivalence and dominance are analyzed with special attention to multiple output circuits. In Section 4, a redundancy based technique has been proposed to find the dominance relations between faults. The results are discussed in Section 5. An application of the new functional collapsing algorithm is demonstrated for large circuits using hierarchical collapsing [START_REF] Hahn | A Hierarchical Approach to Fault Collapsing[END_REF][START_REF] Prasad | A New Algorithm for Global Fault Collapsing into Equivalence and Dominance Sets[END_REF].

Background

We use a graph model described in the literature [START_REF] Akers | On the Role of Independent Fault Sets in the Generation of Minimal Test Sets[END_REF][START_REF] Prasad | A New Algorithm for Global Fault Collapsing into Equivalence and Dominance Sets[END_REF]. The fault equivalence and dominance relations are represented by a directed graph. In this graph each fault is represented by a node. If fault f 1 dominates fault f 2 then this is represented by a directed edge from node f 2 to f 1 . This edge indicates that any test for f 2 must detect f 1 . Clearly, the presence of edges f 1 → f 2 and f 2 → f 1 indicates that the two faults f 1 and f 2 are equivalent. Fault dominance graph, or simply a dominance graph, represents the dominance relations among the faults of a circuit.

Figure 1 shows the dominance graph for all faults of an OR gate. The subscript fault notation has been used, that is, a 0 means that the fault is on line named 'a' and is sa-0. The dominance graph is conveniently represented by its dominance matrix shown in Table 1. A 1 entry at the intersection of a row and a column means that the fault corresponding to the column dominates the fault corresponding to the row. For example, the 1 in the second row and the last

a 0 a 1 b 0 b 1 c 0 c 1 a 0 1 0 0 0 1 0 a 1 0 1 0 1 0 1 b 0 0 0 1 0 1 0 b 1 0 1 0 1 0 1 c 0 0 0 0 0 1 0 c 1 0 1 0 1 0 1 column indicates that c 1 dominates a 1 .
Equivalence of two faults is expressed by two 1's placed at both intersections of the rows and columns of those faults. Since there is also a 1 in the last row and second column indicating that a 1 dominates c 1 , it can be said that a 1 and c 1 are equivalent. This dominance matrix is used in the algorithm of Section 4.1 to represent all the dominance relations between the faults.

Functional Collapsing

Though the above dominance relations are generally called structural, the dominance matrix can also include the relations between the functionally collapsible faults. It should be noted that the functional fault collapsing inherently includes structural collapsing.

Functional Equivalence

For an input vector, V , to be a test for a fault, we have [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF]

F 0 (V ) ⊕ F 1 (V ) = 1 (1)
where F 0 is the fault-free function and F 1 is the faulty function, respectively. Consider a second fault that produces a faulty function F 2 . According to the definition of fault equivalence, two equivalent faults have exactly the same tests. Therefore, for two faults to be equivalent, we have

[F 0 (V ) ⊕ F 1 (V )] ⊕ [F 0 (V ) ⊕ F 2 (V )] = 0 (2) ⇒ F 1 (V ) ⊕ F 2 (V ) = 0 (3)
which means that the two faulty functions are identical. These equations are functionally depicted in Figure 2.

Functional Dominance

If a fault f 1 , with faulty function F 1 , dominates another fault f 2 , with faulty function F 2 , then the two faults are functionally equivalent for the input vector set that tests the fault f 2 , i.e., all tests of f 2 satisfy Equation 3. Let vector V detect f 2 , so it must satisfy the following equation

F 0 (V ) ⊕ F 2 (V ) = 1 (4)
Since f 1 dominates f 2 , any vector that satisfies Equation 4 must satisfy Equation 1. Also, by contra-positive law, any vector that does not satisfy Equation 1 must not satisfy Equation 4. These conditions are combined in Equation 5that must be satisfied by all input vectors.

[F 0 (V ) ⊕ F 2 (V )] ⊕ [F 0 (V ) ⊕ F 1 (V )] = 0 (5)
This relation, as shown in Figure 3, was explained in the paper by Agrawal et al. [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF].

Previous Work

There has been considerable work in the area of fault collapsing. Several authors [START_REF] Clegg | Use of SPOOF's in the analysis of Faulty Logic Networks[END_REF][START_REF] Grüning | DIATEST: A Fast Diagnostic Test Pattern Generator for Combinational Circuits[END_REF][START_REF] Hartanto | Diagnostic Fault Equivalence Identification Using Redundancy Information & Structural Analysis[END_REF][START_REF] Lioy | Looking for Functional Fault Equivalence[END_REF][START_REF] Mccluskey | Fault Equivalence in Combinational Logic Networks[END_REF][START_REF] Schertz | A New Representation for faults in Combinational Digital Circuits[END_REF][START_REF] Veneris | Fault Equivalence and Diagnostic Test Generation Using ATPG[END_REF] concentrate on finding the fault equivalences, while others [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF][START_REF] Lioy | Advanced Fault Collapsing[END_REF][START_REF] Prasad | A New Algorithm for Global Fault Collapsing into Equivalence and Dominance Sets[END_REF] deal with fault dominance relations. Recent papers also give methods to find fault equivalences using ATPG [START_REF] Grüning | DIATEST: A Fast Diagnostic Test Pattern Generator for Combinational Circuits[END_REF][START_REF] Veneris | Fault Equivalence and Diagnostic Test Generation Using ATPG[END_REF] and simulation [START_REF] Al-Assad | Simulation-Based Approximate Global Fault Collapsing[END_REF]. Fault equivalence identification can be based on redundancy information [START_REF] Amyeen | Fault Equivalence Identification using Redundancy Information and Static and Dynamic Extraction[END_REF], and hence test generation can prove equivalence [START_REF] Hartanto | Diagnostic Fault Equivalence Identification Using Redundancy Information & Structural Analysis[END_REF]. There are techniques to find the relations between the faults on a fan-out stem, its branches and the reconvergent points [START_REF] Abramovici | Dynamic Redundancy Identification in Automatic Test Generation[END_REF][START_REF] Lioy | On the Equivalence of Fanout-Point Faults[END_REF][START_REF] Nadjarbashi | Line Oriented Structural Equivalence Fault Collapsing[END_REF][START_REF] To | Fault Folding for Irredundant and Redundant Combinational Circuits[END_REF].

Consider the full adder circuit as shown in Figure 4. This circuit has a total of 60 faults, the structural equivalent collapsed set has 38 faults and the structural dominance set has 30 faults. As reported in [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF], the functional equivalence collapsing leads to 26 faults, while functional dominance collapsing resulted in a fault set of 14 (further reducible to 12).

Definitions

We first quote the conventional definitions of equivalence and dominance [START_REF] Abramovici | Digital Systems Testing and Testable Design[END_REF][START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits[END_REF] and then extend them to multiple output circuits.

Definition 1: Fault Equivalence -Two faults of a Boolean circuit are equivalent if and only if faulty functions are identical at each output of the circuit.

Definition 2: Fault Dominance -A fault f i is said to dominate fault f j if (a) the set of all vectors that detects fault f j is a subset of all vectors that detects fault f i and (b) each vector that detects f j implies identical values at the corresponding outputs of faulty versions of the circuit [START_REF] Jha | Testing of Digital Systems[END_REF][START_REF] Poage | Derivation of Optimum Test Sequences for Sequential Machines[END_REF]. This definition has been later modified as, "A fault f i is said to dominate fault f j if the faults are equivalent with respect to the test set of fault f j [START_REF] Abramovici | Digital Systems Testing and Testable Design[END_REF][START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits[END_REF]." These definitions are extended for possible interpretations for multiple output circuits.

Definition 3: Diagnostic equivalence -Two faults of a Boolean circuit are called equivalent if and only if the pair of the output functions is identical at each output of the circuit.

This definition of equivalence, which is identical to Definition 1, implies indistinguishability of two faults.

Definition 4: Detection equivalence -Two faults are called detection equivalent if and only if all tests that detect one fault also detect the other fault, not necessarily at the same output. Two detectable faults that are diagnostic equivalent are also detection equivalent. Faults that are detection equivalent need not be indistinguishable. Typically, a test vector generation process involves fault simulation and the faults that get detected by a test vector are dropped. Inherently, the fault simulation uses detection relations, while it is often incorrectly believed to be functional (diagnostic) relation. This observation motivated the work presented in this paper.

Definition 5: Diagnostic dominance -If all tests of a fault f 1 detect another fault f 2 on the exact same outputs where f 1 was detected, then f 2 is said to dominate f 1 .

Definition 6: Detection dominance -If all tests of a fault f 1 detect another fault f 2 , irrespective of the output where f 1 was detected, then f 2 is said to detection dominate f 1 . This detection dominance is same as the test covering relation proposed by Abramovici et al. [START_REF] Abramovici | Dynamic Redundancy Identification in Automatic Test Generation[END_REF] or test implication proposed by To [START_REF] To | Fault Folding for Irredundant and Redundant Combinational Circuits[END_REF]. The detection equivalence is referred to as test equivalence by Lioy [START_REF] Lioy | On the Equivalence of Fanout-Point Faults[END_REF] and To [START_REF] To | Fault Folding for Irredundant and Redundant Combinational Circuits[END_REF]. Like equivalence, diagnostic dominance between two detectable faults also implies detection dominance. We note that Definitions

A New Result on Functional Dominance

Finding functional dominances using the implementation as shown in Figure 3 is a computationally expensive procedure. This is because we need to implement it for all the permutations of faults taken two at a time. A modified and less expensive scheme is shown in Figure 5 where, initially all the three blocks are the fault free copies of the circuit with function F 0 . Consider a non-redundant fault, say x 1 , and introduce it in the bottom block whose function is now designated as F 1 . Consider another fault, say y 0 , which is dominated by x 1 in the given circuit. Whenever y 0 in the top block is activated and propagated to the AND gate, it is blocked by the output of the XOR gate (a logic 1), because fault x 1 is also detectable when y 0 is detected. So, all faults that are dominated by x 1 in the given circuit are redundant in the top block. In a single iteration of the ATPG, we will find all faults that are dominated by the fault introduced in block F 1 . A redundant fault in the given circuit (stand-alone F 0 ) will appear to be dominated, in Figure 5, by any fault introduced in bottom block. While that is a correct conclusion, without elaborating on the reasons, we consider only non-redundant faults in the given circuit.

In the implementation of Figure 3, the ATPG is run n(n -1) times, n being the number of non-redundant faults in the circuit, and in each run of ATPG, we test the redundancy of one fault. Using the scheme in Figure 5, the ATPG is run n times and in each run, we carry out the redundancy test for n -1 faults. The algorithm used for functional collapsing is as follows:

Algorithm

1. Select a non-redundant fault from the given circuit and build the circuit as shown in Figure 5 with the fault introduced in the bottom block whose function is F 1 . 2. Check for redundant faults in the top block F 0 . 3. For each redundant fault found in step 2, a 1 is placed in the dominance matrix at the intersection of the row corresponding to the redundant fault and the column corresponding to the fault in the bottom block. Thus, we obtain all values of a column of the dominance matrix in a single iteration. 4. Go to step 1 until there is no non-redundant fault left. 5. At the end of the algorithm, we get the dominance matrix with all functional dominance relations included. 6. Transitive closure of the dominance matrix is computed, which is then reduced using the algorithm equivalence of Prasad et al. [START_REF] Prasad | A New Algorithm for Global Fault Collapsing into Equivalence and Dominance Sets[END_REF]. This reduced matrix consists of the dominance relations within an equivalence collapsed set of faults. 7. If dominance collapsing is required, then the reduced matrix of the previous step is further reduced according to algorithm dominance of Prasad et al. [START_REF] Prasad | A New Algorithm for Global Fault Collapsing into Equivalence and Dominance Sets[END_REF].

The scheme of Figure 5 is for a single-output circuit. For a circuit with multiple outputs, the scheme of Figure 6 is used. It illustrates a case of two outputs and the generalization for more than two outputs is straightforward. The scheme of Figure 6(a) conforms to the diagnostic collapsing as given by Definitions 3 and 5 of Section 3, while that of Figure 6(b) does detection collapsing. It should be noted that the scheme of Figure 6(b) ensures that a test vector which detects the dominating fault on an output line blocks all AND gates because of the additional OR gate, unlike in Figure 6(a). This causes more redundancies and thereby more dominance relations between faults, that is, more 1's in the dominance matrix. Hence, the fault set obtained using detection dominance will be much smaller than that obtained for diagnostic dominance for multiple output circuits.

Consider the full adder circuit shown in Figure 4. Diagnostic dominance collapsing results in a set of 12 faults while detection dominance yields a set of 6 faults, which is the smallest set among all the reported results to date.

Results

We first present four example circuits for illustration. The smallest is a simple XOR function implemented with four NAND gates and the largest is the 4-bit ALU circuit (74181). The results according to the definitions of diagnostic and detection collapsing of Section 3 are tabulated in Table 2. These results are compared with the structural equivalence collapsed set obtained using Hitec [START_REF] Niermann | HITEC: A Test Generation Package for Sequential Circuits[END_REF] and Fastest [START_REF] Kelsey | An efficient Algorithm for Sequential Circuit Test Generation[END_REF], and the structural dominance collapsed set obtained by Fastest [START_REF] Kelsey | An efficient Algorithm for Sequential Circuit Test Generation[END_REF]. The column "Functional [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF]" has the values obtained using a hierarchical fault collapsing technique [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF]. The XOR gates of the ALU circuit are replaced with four NAND gate implementation. The collapse ratio of each collapsed set is shown by the accompanying fraction in parenthesis. The collapse ratio is defined as the relative size of collapsed set with respect to set of all faults [START_REF] Bushnell | Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits[END_REF].

For the 8-bit adder, the previous best result is reported by Agrawal et al. [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF]. Their hierarchical collapsing technique resulted in the collapsed set of 112 faults (collapse ratio 0.24) while the implementation described in this paper leads to a set of 48 faults (collapse ratio 0.10), a reduction of over 50%. This result is for detection dominance. The diagnostic dominance for multiple outputs results in a collapse ratio of 0.21, which still is smaller than that previously reported [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF]. The dominances that are missed by the hierarchical collapsing technique of [START_REF] Agrawal | Fault Collapsing via Functional Dominance[END_REF] are the functional dominances between the faults of different logic cells that cannot be found using the transitive closure of the dominance graph. Based on our experience, the collapsing using the detection dominance leads to collapse ratios in the range of 0.10-0.20. The paper by Agrawal et al. [START_REF] Agrawal | It is Sufficient to Test 25-Percent of Faults[END_REF] achieves a collapse ratio of about 25%.

From Table 2, we see that the fault set of the full adder is collapsed to a set of 26 faults according to the diagnostic equivalence collapsing. There are three more equivalences which are found using detection equivalence collapsing. These faults, in the subscripted fault notation, are j 0 collapsed with k 1 , q 1 collapsed with u 1 , and z 0 collapsed with w 1 . The lines in the full adder are named as shown in Figure 4. The fault q 1 which is detected at the output line C out by vectors 100 and 010, applied to inputs A, B, C in , is considered as detection equivalent with u 1 which is detected by the same vectors at the output Sum.

The ATPG used for collapsing algorithms is Hitec/Proofs [START_REF] Niermann | HITEC: A Test Generation Package for Sequential Circuits[END_REF].

There were some aborted faults while checking for redundancies in step 4 of the Algorithm in Section 4.1. Had these aborted faults been treated as redundant we would have inserted additional 1's in the dominance matrix resulting in a smaller, though possibly erroneous, collapsed set. So, the results in Table 2 may not represent the smallest possible collapsed set. This is the reason why the diagnostic and detection equivalence collapsed sets of 8-bit adder are the same while the corresponding full adder collapsed set sizes are different. When no fault is aborted, using a better ATPG, the algorithms would result in the minimal collapsed fault set. But this should not be considered a problem since the use of this algorithm is recommended only for smaller circuits, where we would not have any aborted faults.

The results obtained with the algorithms have been verified as described below. A test generator is run to derive test vectors for the fault sets obtained from our algorithms. Then a fault simulator is used to determine whether the test vectors detect all faults of the circuit except the redundant ones. The Gentest ATPG [START_REF] Cheng | Gentest: An Automatic Test Generation System for Sequential Circuits[END_REF] is used for this purpose and the number of test vectors with default options on Gentest is tabulated in Table 3. The test vectors are compared with the test vectors required for the structural equivalence col- lapsed [START_REF] Niermann | HITEC: A Test Generation Package for Sequential Circuits[END_REF] and dominance collapsed [START_REF] Kelsey | An efficient Algorithm for Sequential Circuit Test Generation[END_REF] sets. Accompanying each entry of the test vectors, the value in parenthesis is the number of the target faults provided to the test generator. The target faults are different from that in Table 2 in case of ALU, because there were 8 redundant faults which are not considered here. Though there is a reduction in the number of test vectors for ALU, we still have a long way to go because the minimum number of test vectors to detect all the faults is only 12 [START_REF] Akers | Test Counting: A Tool for VLSI Testing[END_REF]. It has been observed through experiments that the number of test vectors is dependent on the fault order and the selection of a test vector from among many vectors that detect a target fault.

Hierarchical Fault Collapsing

The redundancy-based algorithms of this paper should be used only with smaller circuits, because the time taken to compute the collapsed set increases exponentially as the circuit size grows. The collapsing results with ALU have been included just for demonstration. The collapsing techniques described in this paper can be used with hierarchical fault collapsing [START_REF] Hahn | A Hierarchical Approach to Fault Collapsing[END_REF][START_REF] Prasad | A New Algorithm for Global Fault Collapsing into Equivalence and Dominance Sets[END_REF]. The collapsed sets of smaller circuits like multiplexer, half-adder, xor, full-adder, etc., can be saved as library information. This information can then be used to collapse faults in larger circuits consisting of the library elements. The collapsed set of the larger circuit can again be saved for use at the next higher level of hierarchy. It should be noted that we can use detection collapsing only for the sub-circuits, whose outputs are all primary outputs. This technique has been demonstrated by collapsing different sized ripple carry adders and the results are tabulated in Table 4. All adders in the Hierarchical column are the circuits described hierarchically using a full adder. The column Functional is diagnostic equivalence collapsing set size and is compared with structural equivalence collapsing set obtained from the flattened circuit. Our collapsing program uses the update for computing transitive closure as described by Dave et al. [START_REF] Dave | Using Contrapositive Law in an Implication Graph to Identify Logic Redundancies[END_REF]. The CPU times reported in both cases are those of the same program so that we can make a better comparison for the two collapsing methods. The time reported in seconds is clocked on a 360MHz Sun UltraSparc 5 10 machine with 128MB memory. The same program provides a dominance collapsing option and for a 64-bit adder, the collapsed set has 768 faults, a collapse ratio of 20.67%. This collapsing technique can be used for any circuit that can be described hierarchically to obtain better collapse ratios in lesser time than that required for a flattened circuit. The CPU times for the flattened circuits are also for our program and these are either similar to or better than those for other available programs [START_REF] Kelsey | An efficient Algorithm for Sequential Circuit Test Generation[END_REF][START_REF] Niermann | HITEC: A Test Generation Package for Sequential Circuits[END_REF].

Conclusion

The structural collapsing techniques generally yield a collapse ratio of about 50%. When the detection dominance collapsing is used, the collapse ratio drops to the range of 10 to 20%. The fault set sizes obtained using the presented algorithm are considerably smaller than the previously reported results. The advantage of such a small collapse ratio may be in the reduction of the fault simulation effort and in the number of test vectors, though it is not clearly reflected in Table 3. There are methods [START_REF] Benmehrez | Measured Performance of a Programmed Implementation of the Subscripted D-Algorithm[END_REF][START_REF] Pomeranz | COM-PACTEST: A Method to Generate Compact Test Sets for Combinational Circuits[END_REF] that aim at obtaining, though do not guarantee, the smallest vector set to detect a given fault set. The number of test vectors when compared to the lower bound given by a method due to Akers and Krishnamurthy [START_REF] Akers | Test Counting: A Tool for VLSI Testing[END_REF] indicates that further reduction is possible. Care is needed in using dominance collapsed set since there can be instances where the dominated fault is redundant and the dominating fault (not included in the collapsed set) is testable. For fault diagnosis, we can only use the diagnostic equivalence collapsed set.

We have used an ATPG to find redundancies. There are recent methods [START_REF] Dave | Using Contrapositive Law in an Implication Graph to Identify Logic Redundancies[END_REF][START_REF] Iyer | FIRE: A Fault-Independent Combinational Redundancy Identification Algorithm[END_REF][START_REF] Mehta | A Fault-Independent Transitive Closure Algorithm for Redundancy Identification[END_REF] of redundancy identification, not based on ATPG but using non-exhaustive search, that are less time consuming. Their use may provide trade off between the CPU time efficiency of the algorithms and the smallest possible collapsed set found.

Figure 1 .

 1 Figure 1. Dominance graph of an OR gate.

Figure 2 .Figure 3 .

 23 Figure 2. Two ways to view fault equivalence.

Figure 4 .

 4 Figure 4. A full adder circuit.

Figure 5 .

 5 Figure 5. Identifying functional dominance.

3 and 5 (

 5 diagnostic type) are identical to Definitions 1 and 2 that are often discussed in the literature.

Figure 6 .

 6 Figure 6. Schemes for collapsing faults with a) diagnostic and b) detection criteria.

Table 1 . Dominance matrix of OR gate.

 1

Table 2 . Comparison of fault collapsing results.

 2

					Number of collapsed faults (Collapse Ratio)
	Circuit	All	Structural	Functional	Functional collapsing -New results
	name	faults	[19, 26]	[3]		Diagnostic criterion Detection criterion
			Equiv. Dom. Equiv. Dom. Equiv.	Dom.	Equiv.	Dom.
	XOR	24	16	13	10	4	10	4	10	4
			(0.67) (0.54) (0.42) (0.17) (0.42)	(0.17)	(0.42)	(0.17)
	Full	60	38	30	26	14	26	12	23	6
	Adder		(0.63) (0.50) (0.43) (0.23) (0.43)	(0.20)	(0.38)	(0.10)
	8-bit	466	290	226	194	112	194	96	194	48
	Adder		(0.62) (0.49) (0.42) (0.24) (0.42)	(0.21)	(0.42)	(0.10)
	ALU	502	301	248	-	-	253	155	234	92
	(74181)		(0.6)	(0.49)			(0.5)	(0.31)	(0.47)	(0.18)

Table 3 . Comparison of the test vectors.

 3

		No. of test vectors (no. of target faults)
	Circuit	Structural	Functional
	name	Equiv.	Dom.	Diagnostic Detection
				Dom.	Dom.
	Full Adder	6 (38)	6 (30)	7 (12)	6 (6)
	8-bit Adder 33 (290) 28 (226)	32 (96)	28 (48)
	ALU	44 (293) 44 (240)	39 (147)	38 (84)

Table 4 . Hierarchical fault Collapsing.

 4

				No. of collapsed faults
	Circuit	All	Flattened	Hierarchical
	name	faults	(Structural)	(Functional)
			Equiv. CPU s Equiv. CPU s
	Full Adder	60	38	0.01	26	0.01
	8-bit	466	290	0.02	194	0.03
	16-bit	930	578	0.03	386	0.04
	32-bit	1858	1154	0.08	770	0.08
	64-bit	3714	2306	0.2	1538	0.1
	128-bit	7426	4610	0.7	3074	0.2
	256-bit	14850	9218	2.6	6146	0.5
	512-bit	29698	18434	10.4	12290	1.3
	1024-bit	59394	36866	44.8	24578	4.2
	2048-bit	118786 73730	188.1	49154	13.6

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE


Zaid Al-Ars
email: zaid.al-ars@catram.com

Said Hamdioui

Georg Mueller

Ad J Van De Goor

Framework for Fault Analysis and Test Generation in DRAMs

Keywords: tool framework, DRAM testing, faulty behavior, defect simulation, test generation

With the increasing complexity of memory behavior, attempts are being made to come up with a methodical approach that employs electrical simulation to tackle the memory test problem. This paper describes a framework of algorithms and tools developed jointly by the Delft University of Technology and Infineon Technologies to systematically generate DRAM tests using Spice simulation. The proposed Spice-based test approach enjoys the advantage of being relatively inexpensive, yet highly accurate in describing the desired memory faulty behavior.

Introduction

The process of DRAM testing has developed into a rather complex combination of historically proven test sets, highly specialized expert knowledge, and cuttingedge failure analysis (FA) methods to evaluate any newly encountered failure mechanisms [START_REF] Nakamae | Evaluation of Final Test Process in 64-Mbit DRAM Manufacturing System Through Simulation Analysis[END_REF]. However, many of these test development methods follow two main paths, 1. test development based on memory specifications, and 2. test development based on post-manufacture failure analysis. This paper presents a third industrial alternative for test development, which is based on the application of Spice simulation to efficiently perform fault analysis and test generation. Simulation-based test generation serves as a tradeoff between the qualitative and inexpensive specifications-based testing, and the quantitative yet expensive manufacturing-based testing.

Section 2 starts with a global discussion of the current approach to DRAM test generation. Section 3 shows the way electrical simulation can support test generation activities. Section 4 discusses the suggested framework to implement the simulation-based fault analysis approach.

Traditional DRAM test flow

The memory test flow is a description of the stages and activities needed to test memory devices. Figure 1 shows a block diagram of a typical manufacturing test flow for a memory manufacturer [START_REF] Nakamae | Evaluation of Final Test Process in 64-Mbit DRAM Manufacturing System Through Simulation Analysis[END_REF]. The figure also called manufacturing-based test generation, which is very accurate and memory-specific, since the tests are generated by statistically analyzing test feedback data from real chips in the fab. This style of test generation assumes a large volume of failing memory parts to enable a meaningful statistical analysis of test data which, in turn, requires a rather expensive and time-consuming test adaptation loop (such as Frontend → Yield analysis → Test adaptation in Figure 1) until a stable set of tests can be generated.

Including electrical simulation

The specifications and manufacturing-based test generation approaches, each has advantages and disadvantages in terms of quality and cost of test generation, as shown in Figure 2. This paper proposes a simulation-based test generation approach, that strikes a tradeoff between specifications and manufacturing-based test generation, and provides an alternative that is both moderately cheap and device-specific. As shown in the shaded "Simulationbased" block of Figure 1, simulation-based test generation uses electrical Spice models from the design stage of the design flow, to represent the internal memory design and behavior, as well as the characteristics of the fabrication process. This provides a fairly accurate representation of the specific behavior of the memory under analysis. At the same time, simulations can support test adaptation activities based on feedback data from the yield analysis and failure analysis stages. This significantly accelerates the expensive and time-consuming feedback loop required by the manufacturing-based test generation. Model reduction-The framework starts with an electrical Spice model that describes the various circuits of the memory, and makes it possible to simulate their behavior using an electrical simulator. This model is fed into a "Model reduction" tool that generates a reduced simulation model, which helps to reduce the analysis time.

Simulation-based test generation

Defect injection-In order to perform the fault analysis on the reduced model, the failure mechanism to be analyzed needs to be modeled and injected into the simulation model. The failure mechanism is modeled using a Spice defect (resistive, parameters change, etc.) and injected using the "Defect injection" tool in Figure 3.

Fault analysis-The fault analysis itself is performed in the "Fault analysis" tool of Figure 3 which generates optimized tests using the reduced, defective simulation model. The algorithms included within this tool depend on the memory to be analyzed and on the type of the required analysis. A number of algorithms have been suggested in the literature to tackle many different problems, such as those for simulation-based test pattern generation in DRAMs .

Figure 1 .

 1 Figure 1. Block diagram of a manufacturing test flow for a memory manufacturer.

Figure 2 .

 2 Figure 2. Cost-quality tradeoff of test generation.

Figure 3 Figure 3 .

 33 Figure 3 suggests a framework to implement the simulation-based test generation approach into the test flow, where a number of steps and tools are identified that would generate the required tests based on an initial Spice simulation model from the designers.

Traditionally, memory tests performed in the test flow are generated in two steps: 1. based on information from the specification stage of the design flow and, 2. based on information from tests performed on manufactured chips in the manufacturing stage of the design flow [see the two highlighted stages of the design flow in Figure 1]. These two stages are described next. 1. Specification stage-Every test flow for a new memory design starts with an analysis of the specifications of the new memory design and an analysis of the tests used for the previous memory design [see block "Tests from old design"]. The specifications are used to generate a new set of tests by adapting the old tests to comply with the specifications of the new memory [see block "Test generation"],an approach referred to as specifications-based test generation. This approach is relatively fast and inexpensive, since it assumes that the faulty behavior of the memory does not change with changing memory technology, which is generally not true. Therefore, this approach is not memoryspecific enough to derive accurate tests for the memory.2. Manufacturing stage-After chip manufacturing, specifications-based tests, generated in the previous step, are applied to the memory in the frontend and backend stages of the test flow. For every new memory, the "Yield analysis" stage identifies new failure mechanisms for which additional tests are needed. Furthermore, memories that fail in the field are sent back to the manufacturer as application fails, where they get analyzed in the "Failure analysis" stage of the test flow. Feedback from these two analysis stages is used to adapt the tests in the "Test adaptation" stage, in order to detect any previously undetected faults. This test generation and adaptation approach is Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE