Parallel X-fault simulation with critical path tracing technique

Parallel X-Fault Simulation with Critical Path Tracing Technique Raimund Ubar, Sergei Devadze, Jaan Raik, Artur Jutman Department of Computer Engineering Tallinn University of Technology Tallinn, Estonia {raiub, serega, jaan, artur}@pld.ttu.ee Abstract—In this paper, a new very fast fault simulation method to handle the X-fault model is proposed. The method is based on a two-phase procedure. In the first phase, a parallel exact critical path fault tracing is used to determine all the detected stuck-at faults in the circuit, and in the second phase a postprocess is launched which will determine the detectability of X-faults. Keywords-digital circuits; fault simulation; X-fault model; parallel exact critical path fault tracing

I.

INTRODUCTION

Shrinking geometries in today’s deep-submicron processes produce new failure mechanisms in electronic devices which has forced the researchers to develop more advanced and complex fault models compared to the simple traditional stuckat fault (SAF) model [1]. New fault models help to improve the confidence of test quality measures and to increase the accuracy of fault diagnosis. New fault modeling techniques in their turn are a challenge for inventing new efficient fault simulation methods to increase the speed of test analysis and fault diagnosis. In this paper a new very fast fault simulation method for combinational circuits or sequential circuits with full scan paths is proposed, which is able to handle the recently proposed X-fault model [22]. The method can be used for evaluating the X-fault coverage of the given set of test patterns or for analyzing failed test patterns to extract diagnostic information and construct the diagnosis tables for fault location purposes. The organization of the paper is as follows. First, in Section II, an overview about the recent developments in fault modeling techniques and fault simulation methods is given. In Section III, theoretical basics are presented to understand the proposed approach, Section IV and V describe the first phase of simulation dealing with SAF model, and Section VI extends the approach to cover the X-fault model. Experimental results are discussed in Section VII, and finally, Section VIII summarizes the paper. II.

STATE-OF-THE-ART OF FAULT ANALYSIS

Fault models are used in test generation and fault diagnosis whereas the efficiency of both procedures relies heavily on the efficiency of the fault simulation.

978-3-9810801-6-2/DATE10 © 2010 EDAA

A. Fault modeling methods Traditional fault simulators based on the single SAF model handle simple physical defects which force a single site to a fixed logic value of 0 or 1. For better modeling of arbitrary physical defects in the circuit components of nanometer technology, a conditional fault model has been proposed as one extension of the classical SAF model [2,3]. A conditional SAF model consists of a signal line with SAF (as a topological part of the model) and an activation condition (the functional part). Such a metric has been used for many years under different names like fault tuple model [4], pattern fault model [5], input pattern fault model [6], or functional fault model [7] which can represent any arbitrary change in the logic function of a circuit block, where a block is defined to be any combinational subcircuit described at any level of the design hierarchy. For complete exercising of blocks in combinational circuits on the gate level, a similar pattern oriented gateexhaustive fault model was proposed in [8], which was extended to target bigger regions (collections of gates) by region-exhaustive fault model in [9]. Many researchers have focused on developing new fault models for particular types of failure mechanisms like signal line bridges [10-14], transistor stuck-opens [15,16], failures due to changes in circuit delays [17] etc. A more complex defect, such as a resistive short or open, causes multiple effects around the defect site. For example, the behavior of a fanout gate may be affected by a defect which forces on the fanout branches of the gate intermediate voltages. As a result, multiple faulty logic values may appear on the fanout branches depending on the threshold voltages of the branches. A unified fault model for interconnect opens and bridges using constrained multiple line stuck-at faults is proposed in [18]. To deal with the ambiguities of the changing logic values on the branches, the Byzantine fault model was introduced [19,20] where a floating line with n branches may lead to 2n – 1 possible fault cases. Methods are proposed to reduce the number of 2n – 1 to a reasonable smaller subset, which however needs additional information about the layout, vias or buffers, threshold voltages of the transistors driven by the floating nodes, or about the occurrence probabilities of possible logic behaviors of physical defects [18,21].

For efficient diagnosis of realistic faults leading to the Byzantine effect a novel X-fault model was developed in [21-23]. It represents all possible behaviors of physical defects in a gate and/or on its fanout branches by using different X symbols on the fanout branches. A dedicated symbolic technique was proposed in [21,22] for X-fault simulation and for analyzing the relations between observed and simulated responses to extract diagnostic information and to score the results of diagnosis. B. Fault simulation methods Most of fault simulation methods have been developed for the SAF model. Parallel pattern single fault propagation (PPSFP) [24] has been widely used in combinational circuit fault simulation. Many proposed fault simulators incorporate PPSFP with other techniques such as critical path tracing [25,26], stem region [27] and dominator concept [26]. These techniques have reduced further the simulation time. In [28] a novel high-performance resistive bridging fault simulator is proposed which is based on fault sectioning in combination with parallel-pattern or parallel-fault multiple stuck-at simulation. In [29] parallel-pattern approach is used for simulating interconnect-open defects. Another group of methods like deductive [30], concurrent [31] and differential fault simulation [32] are based on logic reasoning rather than simulation. Deductive fault simulation scales better than parallel fault simulation as their complexities are O(n2) and O(n3), respectively [33], where n is the number of logic gates in a circuit. Differential fault simulation combines the merits of concurrent fault simulation and single fault propagation techniques, and was shown to be up to twelve times faster than concurrent fault simulation and PPSFP [1]. This group of methods is very powerful since all the detectable faults are calculated by a single run of the test pattern. What they cannot do is to produce reasoning for many test patterns in parallel. The Critical Path Tracing (CPT) consists of simulating the fault-free circuit and using the computed signal values for backtracing all sensitized paths from primary outputs to primary inputs, to determine the detected faults. The trace continues until the paths become non-sensitive or end at primary inputs. Faults on the sensitive (critical) paths are detectable by the test. CPT is also based on reasoning, and can process all the faults by a single run, however precise results are only guaranteed in fanout-free regions (FFR) of circuits. A modified critical path tracing technique that is linear time, exact, and complete is proposed in [34]. However, the rule based strategy does not allow parallel analysis of many patterns. A novel concept of parallel exact critical path tracing which can be applied efficiently also beyond the FFRs was developed in [35,36]. For some of the advanced fault models dedicated fault simulation methods have been developed, e.g. symbolic X-fault simulation [21,22], simulation of resistive bridging faults based on resistance intervals [13] etc. These methods, however, allow simulating faults one by one, and methods for analyzing faults in parallel for many patterns are missing.

In this paper we propose an extension of the exact parallel critical path tracing method [36] to be applied for the extended class of X-faults [21-23]. Fault simulation is carried out in two phases: (1) logic SAF simulation to determine the active fanout stems, and (2) determining the detected X-faults for all active fanout stems found by the first phase. III.

THEORETICAL BACKGROUND

In the first logic fault simulation phase to determine the detected SAF faults in the circuit for the given set of test patterns we use the novel method of parallel exact critical path tracing [36]. Consider a fanout-free region (FFR) represented by a Boolean function y = F(x1,…, xi, xj, … xn). The task of logic fault simulation can be reduced to calculation of Boolean derivatives: if ¶y/¶xj = 1 then the fault is propagated from xj to y. This check can be performed in parallel for a set of test patterns. In order to extend the parallel critical path tracing beyond the fanout-free regions we use the concept of partial Boolean differentials [37]. Consider a fan-in subcircuit F of the converging fanout region depicted in Fig. 1, and represented by a function y = F(x1, …, xi, xj, … xn).

X1 f1(z, X1)

z

. . . Xi

x1 .

fi(z, Xi)

xi . . xj . xn . .

y F

Figure 1. Reconvergent FFR in a circuit

Assume that the inputs x1,…,xi of the subcircuit F are connected to the fanout stem z via subcircuits without reconvergencies and represented by functions x1 = f1(z,X1), …, xi = fi(z,Xi), where Xi are vectors of variables. Then all possible fault propagation conditions for the circuit in Fig. 1 can be represented by the full Boolean differential [35]:

dy = dF = y Å F (( x1 Å dx1 ),..., ( x i Å dx i ), ( x j Å dx j ),..., ( x n Å dx n ))

(1)

By the Boolean variable dx we denote the erroneous change of the value of x because of a propagated fault. In [36] we have shown that if a SAF is detected by a test pattern at y then the fault at the fanout stem z which converges in y at the inputs x1, …, xi, is also detected iff ¶y ¶x ¶x = y Å F (( x1 Å 1 ),..., ( xi Å i ), x j ,..., xn ) = 1 ¶z ¶z ¶z

(2)

From (2), a method results for generalizing the parallel exact critical path tracing beyond the fanout-free regions. All

the calculations in (2) can be carried out in parallel since they are Boolean operations. In a general case of nested reconvergencies the formula (2) can be used recursively. If a stuck-at fault is detected by a test pattern on the output y of a subcircuit in Fig. 2 with two nested reconvergencies, y = Fy(x1,z,Xy) and z = Fz(x,Xz), where Xy and Xz are not depending on x, then the fault at the common reconverging fanout stem is also detected iff

of the fanout nodes we introduce subscripts at the node variables. The node label is interpreted as the signal variable of the corresponding gate: the variable z represents the output of a gate, and the variable zj represents the j-th branch of the gate’s fanout.

1 1

d x y = y Å Fy ( x1 Å

¶x1 , z Å d x Fz , X y ) =1 ¶x

2

6

3

2 3

(3)

1 2

3 4

5

Figure 3. Reconvergency Graph

x1 x

z Fz Xz

Fy

y

Xy

Figure 2. Nested reconvergencies in a circuit

The formula (3) can be used for calculating the influence of the fault at the common fanout stem x on the output y of the converging fanout region by calculation of partial Boolean differentials, first dxFz, and then dxy. The formula (3) can be iteratively generalized for arbitrary configuration of nested reconvergencies by topological analysis of the circuit. On the other hand the derived full Boolean differentials can be easily transformed into fast computable critical path tracing procedures to be carried out in parallel for sets of test patterns. The parallel path tracing fault analysis is carried out in the following sessions: (1) topological pre-analysis of the circuit to create a model for fault tracing; (2) parallel simulation of a given set of test patterns; (3) parallel fault backtracing to find all detectable SAF. IV.

TOPOLOGICAL ANALYSIS OF THE CIRCUIT

An example of RG is shown in Fig. 3. Here we have: RO = {1,2}, RI = {3,5,6}, RI(1) = {3,5,6}, RI(2) = {6}. The result of the topological analysis is also an ordered set N* of all the nodes in RG. For the graph in Fig. 3 we have N* = (6,5,4,3,2,1). The ordered set N* will be the basis for creating the model for fault backtracing in the circuit according to the proposed method. This strategy allows creation of an optimized calculation model by the breadth-first processing of nodes. V.

CREATION OF THE CALCULATION MODEL

To each edge (zj,y) in the reconvergency graph a signal path through the gates in the circuit corresponds. Denote by the pair zy the formula of the Boolean derivative ¶y/¶z. If the path between z and y consists of a simple chain of gates without reconvergencies we can build for the path a formula zy by the chain rule [37] using logic AND of Boolean derivatives of the gates on the path. Note, that the formulas zy are constructed step by step in the process of paths’ backtracing. If two nodes z and y form a reconvergency like in Fig. 1, we use the formula (2) rewritten now to highlight the fanout branches zi in the following way:

The topological analysis of the circuit consists of two procedures: (1) creation of the Reconvergency Graph (RG), and (2) creation of the calculation model.

¶y ¶x ¶x = y Å F (( x1 Å 1 ),..., ( xi Å i ), x j ,..., xn ) = 1 ¶z ¶z1 ¶zi

Consider RG as a graph G = (N,U) where N is the set of nodes which represent either outputs of the gates with fanout branches or the outputs of fan-in gates where at least two paths from the same fanout stem converge.

The subformulas ¶xi/¶zi in (4) are created step by step during path tracing. These formulas are used also for calculating the detectabilities of faults on the paths:

Denote by RO Í N the subset of all fanout stems and by RI Í N the subset of all fan-in nodes of the circuit. In general case, RI Ç RO ¹ Æ. Denote by RI(i) Í RI, iÎRO, the subsets of all reconvergent fan-in nodes which have reconverging paths from the fanout stem i. RG is created by tracing the circuit in direction from the primary inputs to primary outputs, and as the result, the subsets RO, RI and all RI(i) will be found. An edge (z,y) Î U in the graph G between two neighbour nodes z and y represents a signal path of the circuit through gates without fanouts and without fan-ins with reconvergencies. To specify the branches

¶y ¶xi ¶y = Ù ¶zi ¶zi ¶xi

(4)

(5)

We can calculate now for the given path (z,y) ¶xi/¶zi as a part of the formula (4), and then update the result according to (5) to get the values of ¶y/¶zi. In such a way we achieve in critical path tracing two goals: we calculate the activation of the faults on the paths, (1) up to the output of the gate with reconvergency, and (2) up to the inputs of the same gate to be able to take into account the reconvergency effect. In the case of the nested reconvergencies, we take them into account by

superpositioning formulas (4) as shown in (3). This operation follows also automatically during the backtracing analysis of the circuit. Consider as an example in Table I the procedure for creation of the calculation formulas for the RG in Fig. 3. TABLE I. Steps 1-3 4-5 6-7 8-9 10-11 12-13 14 15-16 17 18 19

In this paper, instead of processing X-faults by inserting symbolic values on the fanout branches and propagating them by symbolic calculation through the circuit, which allows to simulate only a single X-fault at a time one by one, and only for a single test pattern, we generalize the presented parallel critical path tracing approach for the case of X-fault model. Denote the detectability of the faulty combination c = (c1,c2,...,cn) on the fanout node z with n branches at y as in Fig. 4 by Dzy(c). We show now, how Dzy(c) can be calculated by extending the calculation model presented in Section V.

CALCULATION MODEL FOR SAF SIMULATION

Nodes 6 5 4 3 2 1

defects such as Byzantine effects. The disadvantage is that the number of unknown faulty behaviors can explode exponentially with the number of fanout branches. To reduce the complexity, attempts have been made to restrict the number of faulty combinations on the fanouts [18,21].

Created formulas for SAF 226 56 36 = 35Ù56 46 = 45Ù56 136 = 134Ù46 236 = 233Ù36 126 = 123Ù36 R26(216’, 226’, 236’) 112, 116 = 112ÙR26 R13(112Ù233’, 123’) R15 (R13Ù35’, 134Ù45’) R16 (112Ù216’, 112Ù226’, R15Ù56’) 216 35 45 134 233 123

In Table I, 19 formulas are created by processing the nodes in the order of N* shown in the column 2. The formulas ziy and zy denote the derivatives ¶y/¶zi and ¶y/¶z, respectively, and the formulas zy’ mean ¶xi/¶z where xi is the input of the gate y. The notation Rzy(z1y’,...,ziy’) is introduced to denote the formula (4), where the parametres ziy’ represent the derivatives ¶y/¶zi, and i is the number of inputs of the gate y where the paths from z reconverge. After creating the calculation model we proceed to the test pattern simulation phase. First, a subset of test patterns will be simulated in parallel to determine the signal values on all of the nodes in the circuit. Second, based on these values and using the formulas in the calculation model we determine which SAF faults are detected by the simulated subset of test patterns.

It is interesting to note that a part of the problem of X-fault simulation is already during SAF simulation as a “side-effect” of the method. This part covers the following cases of the X-fault: (1) the case c=cmax when all fanout branches are affected by faulty signals, and (2) the case when a single fanout branch is faulty. For the given example, these faults are simulated by the formulas in Table II with references back to Table I. TABLE II. Nodes 1/6 2/6

TABLE III. Nodes 1/3 1/5

VI.

X-FAULT SIMULATION

The X-fault model [22] is defined as follows. A fanout gate has one X-fault, corresponding to any physical defect in the gate or on its n fanout branches. The X-fault assumes n different symbols Xi, i=1,...,n, on the n fanout branches to represent all possible combinations of faulty logic values in fault simulation.

G

z

z1

x1

z2

x2

z3

x3

F

y

Figure 4. A subcircuit with reconverging fanout

Fig. 4. shows a X-fault site for a gate G with 3 fanout branches, where z1, z2, and z3 denote 3 branches with arbitrary faulty logic values. By the vector c=(c1,c2,c3), ciÎ{0,1}, we can represent any possible faulty logic combination for the vector of branch variables (z1,z2,z3). The positive feature of X-fault model is that it can handle unknown behaviors of complex

2/6

1/6

X-FAULT COVERAGE BY SAF SIMULATION Already available formulas for X-fault model D16 (111) = R16 D16 (001) = 136, D16 (010) = 126, D16 (100) = 116 D26 (111) = R26 D26 (001) = 236, D26 (010) = 226, D26 (100) = 216 CALCULATION MODEL FOR X-FAULT SIMULATION

Updated SAF formulas for X-fault model D13(01X) = R13(Æ, 123’) D13(10X) = R13(112Ù233’, Æ) D15(011) = (D13(01X) Ù35’, 134Ù45’) D15(101) = (D13(10X) Ù35’, 134Ù45’) D15(110) = (R13Ù35’, Æ) D26(011) = R26(Æ, 226’, 236’) D26(101) = R26(216’, Æ, 236’) D26(110) = R26(216’, 226’, Æ) D16(011) = R16 (Æ,Æ,D15(011) Ù56’) D16(101) = R16 (112Ù216’, 112Ù226’, D15(101) Ù56’) D16(110) = R16 (112Ù216’, 112Ù226’, D15(110) Ù56’)

A direct consequence of this “side-effect” is that X-fault simulation for the fanout stems with two branches is fully covered by the proposed method for SAF simulation. For all other faulty combinations for the fanout stems with at least three branches where at least two branches are affected by the fault, the X-fault detectability can be calculated as in Table III. For each fanout stem z Î FO and each y Î FI(z) we have already created the formula Dzy(cmax) = Rzy during the first phase of simulation for SAF faults (see Table II). For all other combinations c = (c1,c2, ...,ck), where at least two components ci are not zero, the available already formulas Rzy(R1,R2,...,Rk) can be modified so that any ci = 0 implies Ri = Æ, which has

the meaning that ¶xi/¶zi = 0. The new added formulas for the current example are shown in Table III. The formulas needed for X-fault simulation should be added to the set of formulas in the calculation model for SAF simulation. In such a way the whole simulation method proposed for the X-fault model consists of two phases: SAF simulation, and postprocessing to cover the X-fault model. VII. EXPERIMENTAL RESULTS Table IV presents the results of the first phase of SAF simulation based on the proposed exact parallel critical path tracing of propagated erroneous signals. TABLE IV.

RESULTS OF THE SAF SIMULATION AND COMPARISON

#Fan # Branches -outs Max Aver c2670 290 28 3.7 c3540 356 22 4.5 c5315 510 31 5.0 c6288 1456 16 2.6 c7552 812 72 4.1 s13207 1224 37 3.7 s15850 1518 34 3.6 s35932 5295 1449 3.4 s38417 4569 49 3.2 s38584 3946 88 4.5 b14 2409 82 4.8 b15 2353 95 4.8 b17 8145 149 4.8 Average speed gain

Circuit

Fsim 0.8 2.0 1.4 12.1 2.7 2.5 5.4 9.2 16.2 12.1 N/A N/A N/A 1.7

Simulation time, s C1 C2 2.2 24 7.4 43 5.6 57 27.8 284 8.1 88 5.6 70 12.1 111 23.6 390 31.4 310 23.2 320 49.2 N/A 39.1 N/A 117 N/A 4.7 43

New 0.4 0.9 0.8 7.4 1.2 2.0 2.7 5.7 7.0 6.4 14.5 26.6 77.8 1

Experiments were carried out for ISCAS’85, ISCAS’89 and ITC’99 to compare different known fault simulators: FSIM [38], state-of-the-art commercial fault simulators C1 and C2 from major CAD vendors, and the proposed method. Simulation times were calculated for the sets of random 10000 patterns. The time for topology analysis is included and is negligible compared to the gain in speed. Experiments were run on a 1.5GHz UltraSPARC IV+ workstation using SunOS 5.10. Another experiment was carried out in order to estimate the cost of the second phase of simulation. Such approximation is possible since the support for X-fault simulation is achieved by the extension of calculation model used for SAF simulation. Hence the number of extra formulas for calculation of the detectability of X-faults (in addition to the formulas constructed for SAF simulation) determines the time and memory resources needed for X-fault postprocessing. In order to perform the estimation, the average time for formula evaluation was calculated as the time spent on complete SAF simulation (Table IV) divided by the number of formulas processed for this purpose. By using the average time needed for processing of formula we can estimate the time required for X-fault simulation basing on the number of extra formulas calculated for each of benchmarks. The estimation of additional memory space required for postprocessing also takes into account the size of arguments for each of X-fault simulation formulas (since different formulas can occupy different amount of memory).

TABLE V. Circuit c2670 c3540 c5315 c6288 c7552 s13207 s15850 s35932 s38417 s38584 b14 b15 b17 Average

Mem MB 0.2 0.3 0.3 1.6 0.5 0.8 1.1 1.8 2.7 2.4 4.7 5.6 16.7

INCREASE OF RESOURCES FOR X-FAULT SIMULATION FC 84% 72% 65% 98% 67% 86% 82% 99% 88% 76% 86% 72% 74% 81%

Limit 4 Mem 1.7 2.4 1.1 7.2 1.2 1.0 2.6 1.1 1.2 1.1 1.9 3.4 3.2 2.2

Time 2.5 1.8 1.3 2.5 1.3 1.1 5.7 1.4 2.0 1.5 1.8 2.1 2.2 2.1

FC 92% 84% 73% 98% 82% 91% 93% 99% 94% 87% 92% 82% 83% 88%

Limit 6 Mem 2.0 6.7 1.9 7.2 2.6 1.1 5.3 1.1 1.8 1.6 6.3 14.5 8.5 5.1

Time 3.1 4.5 3.1 2.5 3.6 1.2 13.2 1.4 4.8 2.8 5.4 6.4 4.8 5.3

Table V presents results of estimating additional cost for X-Fault simulation in times compared to the first phase of SAF simulation, regarding the memory space (column 2, Table V) and time (column 8, Table IV). Increase in cost is shown in columns Mem and Time, respectively. Two sessions were carried out with limits 4 and 6 to the maximum number of faulty signals on fanout branches. The columns FC show the X-fault coverage, i.e. the percentage of all X-fault combinations processed regarding to the number of all possible combinations. The additional memory and time cost for the second phase of simulation depends on the X-fault coverage that is needed to be achieved. As we see from Table V, both the average time and memory costs increase twice for the fault coverage 81%, and five times for the fault coverage 88%. We have treated here the conventional X-fault model [22] where all the 2n – 1 faulty combinations on the fanout branches are possible and have equal occurrence probabilities. Using the probability calculation approach proposed in [21], or using additional information about the layout [18,21], the number of 2n – 1 can be significantly reduced, which will result in higher probabilistic fault coverage and will reduce both the memory and time costs of simulation. VIII. CONCLUSIONS In this paper we proposed a new method of exact parallel critical path tracing for X-fault simulation. Differently from the known X-fault symbolic simulation approach which allows to handle a single X-fault and a single test pattern at a time, in the proposed new method all the detectable X-faults can be determined simultaneously by one run for a subset of test patterns in parallel. This feature of the method makes it very attractive for X-fault model based fault diagnosis, since the simulated results in the form of all suspected fault candidates can be achieved for all the failing patterns (or at least for a part of them) by a single run. Experimental results show that the speed of the parallel exact critical path tracing for SAF simulation, used as the first phase of simulation, outperforms significantly the known SAF based simulators. The estimated additional memory and time

costs for the second phase of simulation are reasonable. Thanks to the parallelism, the new method is clearly more powerful in terms of speed than the known single pattern single fault symbolic X-fault simulation method. An interesting result is that all the X-faults for 2-branch fanouts are processed as a side-effect already during the proposed SAF simulation phase, and do not need any postprocessing with additional cost. ACKNOWLEDGEMENTS The work has been supported by Estonian SF grants 7068, 7483, EC FP7 IST project DIAMOND, ELIKO Development Centre, and Research Centre CEBE funded by EU Structural Funds. REFERENCES [1] [2] [3] [4] [5] [6]

[7]

[8] [9] [10]

[11]

[12]

[13]

[14]

[15]

[16]

[17] [18]

L.-T.Wang, Ch.-W.Wu, X.Wen, “VLSI Test Principles and Architectures. Design for Testability,” Elsewier, 2006. U.Mahlstedt, J.Alt, I.Hollenbeck, “Deterministic Test Generation for Non-Classical Faults on Gate Level,” 4th ATS, 1995, pp. 244-251. S.Holst, H.-J.Wunderlich, “Adaptive Debug and Diagnosis Without Fault Dictionaries,” 13th ETS, 2008, pp.199-204. K.N.Dwarakanath, R.D.Blanton, “Universal Fault Simulation using fault tuples,” DAC, Los Angeles, June 2000, pp.786-789. K.B.Keller, “Hierarchical Pattern Faults for Describing Logic Circuit Failure Mechanisms,” US Patent 5546408, Aug. 13, 1994. R.D.Blanton, J.P.Hayes, “On the Properties of the Input Pattern Fault Model,” ACM Trans. Design Automation of Electronic Systems, Vol. 8, No. 1, pp. 108-124, Jan. 2003. R.Ubar, “Fault Diagnosis in Cominational Circuits by Solving Boolean Differential Equations,” Automatics & Telemechanics, No.11, 1979, Moscow, pp.170-183 (in Russian). Transl. in: “Detection of Suspected Faults in Combinational Circuits by Solving Boolean Differential Equations,” Automation and Remote Control, Vol.40, No 11, part 2, Nov. 1980, Plenum Publishing Corporation, USA, pp. 1693-1703. Y.Cho, S.Mitra, E.J.McCluskey, “Gate Exhaustive Testing,” International Test Conference, 2005. A.Jas, S.Natarajan, S.Patil, “The Region-Exhaustive Fault Model,” 16th Asian Test Symp. Beijing, China, Oct. 2007, pp. 13-18. J.M.Acken, S.D.Millman, “Accurate Modeling and Simulating of Bridge Faults,” Custom Integrated Circuits Conf., San Diego, CA, May 1991, pp. 17.4.1-17.4.4. P.Maxwell, R.Aiken, “Biased Voting: A Method for Simulating CMOS Bridging Faults in the Presence of Variable Gate Logic Thresholds,” Proc. International Test Conference, 1993, pp. 63-72. L.Zhuo, X.Lu, W.Qiu, W.Shi, D.M.H.Walker, “A Circuit Level Fault Model for Resistive Opens and Bridges,” Proc. VLSI Test Symposium, Napa, CA, Apr./May 2003, pp. 379-384. P.Engelke, I.Polian, M.Renovell, “B.Becker. Simulating resistive bridging and stuck-at faults,” IEEE Trans. on CAD of IC and Systems, Vol. 25, No. 10, pp. 2181-2192, Oct. 2006. A.Rousset, A.Bosio, P.Girard, C.Landrault, S.Pravossoudovitch, A.Virazel, “Fast Bridging Fault Diagnosis Using Logic Information,” 16th ATS. Beijing, China, Oct. 2007, pp.33-38. S.K.Jain, V.D.Agrawal, “Modeling and Test Generation Algorithms for MOS Circuits,” IEEE Trans. Comput., Vol. C-34, No. 5, pp. 426-433, May 1985. H.K.Lee, D.S.Ha, “SOPRANO: An Efficent Automatic Test Pattern Generator for Stuck-Open Faults in CMOS Combinational Circuits,” DAC, Orlando, FL, June 1990, pp. 660-666. A.Kristic, K.T.Cheng, “Delay Fault Testing for VLSI Circuits,” Dordrecht, The Netherlands, Kluwer Academic Publishers, Oct. 1998. G.Chen, S.Reddy, I.Pomeranz, J.Rajski, P.Engelke, B.Becker, “A Unified Fault Model and Test Generation Procedure for Interconnect Opens and Bridges,” 10th ETS, Tallinn, May 2005.

[19] D.Lavo, T.Larrabee, B.Chess, “Beyond the Byzantine Generals: Unexpected Behavior and Bridging Fault Diagnosis,” Proc. International Test Conference, 1996, pp. 611-619. [20] S.Huang, “Speeding up the Byzantine Fault Diagnosis Using Symbolic Simulation,” Proc. VTS, 2002, pp.193-198. [21] Y.Yamato, Y.Nakamura, K.Miyase, X.Wen, S.Kajihara, “A Novel PerTest Fault Diagnosis Method Based on the Extended X-Fault Model for Deep-Submicron LSI Circuits,” IEICE Trans. Inf. & Syst., Vol.E-91-D, No. 3 March 2008, pp.667-674. [22] X.Wen, T.Miyoshi, S.Kajihara, L.-T. Wang, K.Saluja, K. Kinoshita, “On Per-Test Fault Diagnosis Using the X-Fault Model,” ICCAD, Nov. 2004, pp.633-640. [23] I.Polian, Y.Nakamura, P.Engelke, S.Spinner, K.Miyase, S.Kajihara, B.Becker, X.Wen, “Diagnosios of Realistic Defects Based on the X-Fault Model,” DDECS, April 2008, pp. 1-5. [24] J.A.Waicukauski, et al., “Fault Simulation of Structured VLSI,” VLSI Systems Design, Vol.6, No.12, pp.20-32, 1985. [25] M.Abramovici, P.R.Menon, D.T.Miller, “Critical Path Tracing Alternative to Fault Simulation,”. DAC, pp.2-5, 1987 [26] K.J.Antreich, M.H.Schulz, “Accelerated Fault Simulation and fault grading in combinational circuits”, IEEE Trans. on CAD, Vol. 6, No. 5, pp.704-712, 1987. [27] F.Maamari, J.Rajski, “A method of fault simulation based on stem region,” IEEE Trans. CAD, Vol.9, No.2, pp.212-220, 1990. [28] P.Engelke, B.Becker, M.Renovell, J.Schlöffel, B.Braitling, I.Polian, “SUPERB: Simulator Utilizing Parallel Evaluation of Resistive Bridges,” ACM Trans. on Design Automation of Electronic Systems, Vol.14, No.4, Article 56, 21 p., 2009. [29] S.Hillebrecht, I.Polian, P.Engelke, B.Becker, M.Keim, W-T. Cheng, “Extraction, Simulation and Test Generation for Interconnect Open Defects Based on Enhanced Aggressor-Victim Model,” International Test Conference, Papers 33.3, 10 p., 2008. [30] D.B.Armstrong, “A deductive method for simulating faults in circuits,” IEEE Trans. Comp., C-21(5), 464-471, 1972. [31] E.G. Ulrich, T.Baker, “Concurrent simulator of nearly identical digital networks,” IEEE Trans. on Comp., 7(4), pp.39-44, 1974. [32] W.T.Cheng, M.L.Yu, “Differential fault simulation: a fast method using minimal memory,” DAC, pp.424-428, 1989. [33] P.Goel, “Test Generation Cost Analysis and Projections”, Proc. DAC, pp.77-84, 1980. [34] L.Wu, D.M.H.Walker, “A Fast Algorithm for Critical Path Tracing in VLSI,” Int. Symposium on Defect and Fault Tolerance in VLSI Systems, Oct. 2005, pp.178-186.. [35] R.Ubar, S.Devadze, J.Raik, A.Jutman, “Ultra Fast Parallel Fault Analysis on Structural BDDs,” ETS, Freiburg, May 20-24, 2007. [36] R.Ubar, S.Devadze, J.Raik, A Jutman, “Parallel Fault Backtracing for Calculation of Fault Coverage,” 13th ASPDAC, Seoul, Korea, 2008, pp. 667-672. [37] A.Thayse, “Boolean Calculus of Differences,” Springer Verlag, 1981. [38] H.K. Lee, D.S. Ha, “An efficient, forward fault simulation algorithm based on the parallel pattern single fault propagation,” Proc. International Test Conference, pp. 946-955, 1991