電機系

Chapter 4 Fault
Simulation
錯誤模擬
Outline

 Introduction to Fault Simulation

 Fault Simulation for Combinational Circuits
 Techniques for Sequential Circuits
 Fault Grading

2
What is Fault Simulation?

Given :
 A circuit

 A test (sequence of test vectors)

 A fault model

Determine:
 Fault coverage (the fraction of modeled
faults detected)
 Undetected faults

3
Applications of Fault
Simulation
 Determine fault coverage of a given test sequence
 Measure test quality by fault coverage
 Determine undetected faults for test generation
 Construct fault dictionary for diagnosis
 Use a fault simulator to compute & store the response for
every fault
 If the output response of the circuit under test matches any
of the response in the fault dictionary, the fault location is
identified

4
 Conceptual Fault Simulation
Faulty copy #n (D/0)
Patterns

Faulty copy #2 (B/1)

Faulty POs for B/1
Faulty copy #1 (A/0)
Faulty POs for A/0
Fault-free Circuit
Primary Inputs A B
D Fault free POs
(PIs)
C

 One logic simulation for every fault-free and faulty circuits

 Complexity ~ O(F x P x G)
 F: # of faults; P: # of patterns; G: # of gates
 A simple technique: fault dropping.
5
Fault Simulation Techniques

 Parallel-Fault (Single-Pattern) Simulation

 Deductive Fault Simulation
 Concurrent Fault Simulation
 Parallel-Pattern Single-Fault Simulation
 Critical Path Tracing

6
Parallel Fault Simulation
 Simulate multiple circuits at a time
 The inherent parallel operation of computer words to
simulate faulty circuits in parallel with fault-free circuit
 The number of faulty circuits (one for each fault) to be
simultaneously processed is limited by the word length,
e.g., 32 circuits for a 32-bit computer
 The fault-free logic simulation is repeated for
each pass
 This can be avoided by storing fault-free values in
another word.

7
Speedup of Parallel Fault
Simulation
 There are extra costs associated with
parallel fault simulation, so the speed up is
only sub-linear.
 An event, a value-change of a single fault or
fault-free circuit leads to the computation of
the entire word
 A proper fault grouping is needed.
 Group similar faults in the same simulation

8
 Example: Parallel Fault
Simulation
 Assume 4-bit computer words
 Consider three faults: J s-a-0, B s-a-1, and F s-a-0
 Bit allocation: A/0 B/1 F/0 FF Fault free bit

A/0

A 10 1 1 1
×
G 0 1 0 0
C 0 1 0 0
B/1
× E 1 0 1 1

1 0 0 D
B 0 0 J 1 1 0 1
×
H 1 0 0 1
F 1 1 00 1

F/0
9
 Fault Injection by Circuit
Modeling
 By changing only the circuits, we can use a
parallel logic simulator to implement a parallel
fault simulation.

101111
s-a-0
The bit position
corresponding to fault a.

10
Parallel Fault Simulation –
Summary
 Most effective for
 Interconnected logic gate netlist
 Stuck-at faults
 Two-valued logic
 Little resource required
 Easy to implement
 Fixed and low memory requirement
 Some extra cost
 Faults injected in the same word may not generate the
same events.
 The fault-free circuit is simulated in each pass.
11
 Fault List in Deductive Fault
Simulation
 Maintain a fault list of every signals in a logic set.
 A fault is in a fault list of each signal if
 The fault changes the fault-free value of the signal, or
 The fault is propagated to the signal

La={a0, a1 } La={a1 } a=0 c=0

Lc={c0, c1 } Lc={c1 }
Lb={b0, b1 } Lb={b0 } b=1

Fault list before simulation Fault list after logic simulation

12
Propagation of Fault List

 Create an initial fault list at every signal (inject

collapsed faults)
 Propagate fault list starting from PIs.
 Propagate through gates level by level (logic
deduction)
 Propagation rules are set operations and depends only
on gate type and its input values.
 A fault is detected if it appears in the fault list of a
primary output.

13
An Example of Fault List
Propagation
a=0 d=0
La = {a1} c=0 Ld = {a1, c1 , d1}
Lc = {a1, c1}
b=1 e=0
Lb = {b0} Le = {a1, c1 , e1}

 Input a = 0, b = 1
 a = 0  La = {a1}
 a1: a stuck-at-1
 b0 in Lb is not propagated to Lc because a = 0 is the
controlling value.

14
Rule of Fault List Propagation

a b z Output fault list

0 0 0 {La  Lb}  z1
0 1 0 {La - Lb}  z1
AND
1 0 0 {Lb - La}  z1
1 1 1 {La  Lb}  z0
0 0 0 {La  Lb}  z1
0 1 1 {Lb - La}  z0
OR
1 0 1 {La - Lb}  z0
1 1 0 {La  Lb}  z0
0 1 La  z 0
NOT
1 0 La  z 1

15
Fault List Propagation Rule
 Notations:
 Let I be the set of inputs of a gate Z with a
controlling value c and inversion i
(i.e., i is 0 for AND, OR and 1 for NAND, NOR)
 Let C be the set of inputs with value c

Non-controlling case: union

C=f then Lz  { ∪
if c=  Z s  a  c  i
 L j} ∪
j I

Controlling cases: intersection

else Lz  {   L j }  Z s  a  c  i
∩ L j}  { ∪
j C j I  C

16
A Generalized Propagation
Rule – Cont’d
 If no input has value c, any fault effect on any
input propagates to the output.
 If some inputs have value c, only a fault effect
that affects all the inputs at c without affecting
any of the inputs at c’ propagates to the
output.

17
An Example of Deductive Fault
Simulation

a=1

e=1
b=1 g=1
c=1

d=1 f=0

La  {a0 } Le  La  Lc  {e0 }  {a0 , b0 , c0 , e0 }

Lb  {b0 } L f  {b0 , d 0 , f1}
Lc  {b0 , c0 } Lg  {Le  L f }  {g 0 }  {a0 , c0 , e0 , g 0 }
Ld  {b0 , d 0 }

18
 The Deductive Fault Simulation
Algorithm

 Levelize the circuit from PIs to POs.

 Step 1: Read a test vector.
 Step 2: Perform logic simulation.
 Step 3: Perform fault list propagation.
 Step 4: Determine detected faults.
 Goto step 1

19
Fault Collapsing

b f
j
m
g
c
h

d i k

e
Collapsed fault list: {a0,a1,b1,c0,c1,d1,e0,g0,h0,h1}
20
Logic Simulation
0 a

0 b f 0
j 0
m 1
g 1
1 c
h 1

1 d i 1 k 1

0 e

21
Fault List Propagation
0 a La  {a1}
L f  La  Lb  f

0 b f 0 L j  Lg  L f  {c0 , g0 }
Lb  {b1} j 0
m 1
g 1
Lg  {co , g0 }
1 c Lm  Lk  L j  {h0 }
Lc  {c0 } Lh  {co , h0 }
h 1

1 d i 1 k 1
Ld  f
Lk  Li  Le  {c0 , h0 }
0 e
Le  f
Li  Lh  Ld  {c0 , h0 } h0 is detected and
removed from the fault lists.
22
 Apply the Next Vector
01 a

01 b f 01
j 0
m 1
g 1
1 c
h 1

1 d i 1 k 1

0 e

23
 Fault List Propagation
01 a La  {a0 }
L f  La  Lb  {a0 }

01 b f 01 L j  Lg  L f  f
Lb  f j 0
m 1
g 1
Lg  {co , g0 }
1 c Lm  Lk  L j  {c0 }
Lc  {c0 } Lh  {co }
h 1
h0 removed

1 d i 1 k 1
Ld  f
Lk  Li  Le  {c0 }
0 e
Le  f
Li  Lh  Ld  {c0 } c0 is detected and
removed from the fault lists.
24
Faults in Concurrent Fault
Simulation
 Maintain a fault list for every signal in a list of
faulty gates.
 Each faulty gate stores the status of a fault
1. If a fault is activated (i.e., the signal is the fault site)
or
2. Propagated to this gate.

25
Faulty Gate Structure in
Concurrent Fault Simulation
 Each element in the fault list contains
 Fault index
 For example, a0 in the following

 Fault states: input and output values of an element

a=1 1
1 c=1
b=1 1

0
a0 0 This faulty gate (for a stuck-at 0) changes
1 a faulty input to 0 and output to 0.

26
Concurrent Fault Simulation

 An extension of event-driven simulation

 Event-driven simulation for both fault free events
and faulty events.
 Events in concurrent fault simulation
 Fault-free event: (signal, value)
 Generated by PI changes
 Applied to both fault free and faulty circuits.
 Faulty event: (fault index, signal, value)
 Generated by faults
 Applied only to the faulty circuit.

27
Maintain the Faulty List

 After fault-free and faulty event propagation, an

element is in the list iff the I/O values of the
faulty circuit are different from the fault-free
values.
 Faulty gates with the same output values as true
circuits are kept,
 Fault can propagate through multiple paths: we might
need to evaluate a faulty gate several times before we
know no faulty effects pass
 A local fault (at inputs or outputs of a gate) will
remain in the list even there is no difference of
I/O values with faulty free circuits.
 Note that dropped faults will be deleted.
28
Fault Dropping

 We can hash every dropped faults, and

process every faulty list to remove dropped
faults.
 We can also remove dropped faults at fault
site, and remove faulty gates if no fanin faulty
list contains the fault.

29
Concurrent Fault Simulation –
Example

0 1 1 1
a=1 1
a0 0
0
b0 0
0
c0 0
1
e0 0

1 e=1 detected
1 1
b=1 1
0
1 g=1
c=1
0 0 0 0 1 1 1
a0 0 b0 1 c0 0 e0 0 d0 1 f1 1 g0 0
10 0 1 0 0 1 1 0
d=1 f=0
b0 d0 f1
01 01 11

30
 Concurrent Simulation -
Convergence
a0, c0 and e0 converge
into good gates.

0 10 1 1
a = 10 1
a0 0
0
b0 0
0
c0 0
1
e0 0

10 e = 10
10 10
b=1 1
0
10 g=10
c=1
0 0 0 0 10 10 1
a0 0 b0 1 c0 0 e0 0 d0 1 f1 1 g0 0
10 0 1 0 0 1 1 0
d=1 f=0
b0 d0 f1
01 01 11

31
 Concurrent Simulation -
Convergence

0 10 1 1
a = 10 1
a0 0
0
b0 0
0
c0 0
1
e0 0

10 e = 10
10 10
b=1 1
0
10 g=10
c=1
0 0 0 0 10 10 1
a0 0 b0 1 c0 0 e0 0 d0 1 f1 1 g0 0
10 0 1 0 0 1 1 0
d=1 f=0
b0 d0 f1
01 01 11

32
Concurrent Simulation -
Divergence

0 1 0
a=0 0
b0 0
1
a1 1
1
e1 1

0 e=0
0 0
b=1 1
0
0 g=0
c=1
0 0 0 1 1 0
b0 1 d0 1 f1 1 a1 1 e1 1 g1 1
10 1 1 1 0 0 0
d=1 f=0
b0 d0 f1
01 01 11

33
Concurrent Simulation -
Divergence

0 1 0
a=0 0
b0 0
1
a1 1
1
e1 1

0 e=0
0 0
b=1 1
0
0 g=0
c=1
0 0 0 1 1 0
b0 1 d0 1 f1 1 a1 1 e1 1 g1 1
10 1 1 1 0 0 0
d=1 f=0
b0 d0 f1
01 01 11

34
Disadvantages of Deductive &
Concurrent Fault Simulation

 Large memory to record the status of all circuits

(fault-free & faulty).
 Dynamic memory (linked lists)
 Evaluation overhead on the linked lists
 Comparing fault lists
 Removing faults
 Adding faults
 Performance overhead in memory management
 However, concurrent fault simulation is very popular
because it is flexible.
 Different fault types, timing, etc.
35
Parallel-Pattern Single-Fault
Propagation (PPSFP)
 Use multiple computer words to simulate multiple
input patterns.
 It can be based on an event-driven simulation.
 Simple and Extremely Efficient
 Basis of most modern combinational fault simulators
 Note that this is mostly the case we use a fault simulator,
since ATPG is also limited to combinational circuits.
 It is also applicable to sequential circuits.

36
 Parallel-Pattern v.s. Parallel-
Fault
Parallel-pattern
(P1, P2, P3 are events by patterns)  Parallel fault simulation will be
more efficient if
P1
 Faulty events are generated
P2
PIs F POs and propagated to POs.
 Otherwise, events are useless.
P3
 In general, parallel faults
generate different events,
Parallel-fault and they are usually not
(F1, F2, F3 are events by faults)
detected simultaneously by
a single PI pattern.
F1
 Parallel pattern simulation is
PIs F2 POs
more efficient.
F3
37
 Re-visit Parallel Fault
Simulation
 Bit allocation: A/0 B/1 F/0 FF Fault free bit

 There are 9 events, but only one fault is detected!

A/0
B/1 A 10 1 1 1
×
G 0 1 0 0
B 0 0
1 0 0 C 0 1 0 0
× E 1 0 1 1

D 0 1 0 0 J 1 1 0 1
×
H 1 0 0 1
F 1 1 00 1

F/0
38
 Example: Parallel Pattern
Simulation
 Consider one fault F/0 and four patterns: P3,P2,P1,P0
 Bit allocation: P3 P2 P1 P0
 There are only three faulty events!
1 1 1 1
A

0 1 0 1 1 1 0 1
C 0 1 0 1 G 0 1 0 1
B D E 1 0 1 0
J
0 1 0 1 H
x
F 1 0 0 0
1 0 0 1 1 0 0 1 0 0 0 0
0 0 0 0

39
Critical Path Tracing
 Find faults detected by a test without simulating all faults.
 The key is to find critical lines in the circuits by tracing from POs.
 line w is critical for a pattern t iff t detects w stuck-at v
 fault-free value of w is v’ (under t)
 Any PO is critical.
 Find whether any inputs of gates to PO are critical recursively
 If a line of a gate output is critical, the critical property can be
transferred to its sensitive inputs.
 A gate input i is sensitive if complementing the value of i changes
the value of the gate output

Non-sensitive input 1 0
Z PO
Sensitive input 0
i if z is critical, i is critical.
40
Algorithm of Critical Path
Tracing
 For a fanout-free circuit,
 Critical lines can be determined by backward
traversing the sensitive gate inputs from PO’s, in
linear time
 In general, special processing has to be done for
stems
 General Critical path tracing:
1. Fault-free simulation
2. Extract single-PO logic cones and process each cone
1. Process stems with highest levels

2. If the stem is critical, mark critical lines in the fanout

free region according to the sensitivity properties.

41
Critical Property of a Stem

 A stem is critical
 If all the capture lines are critical.
 All sensitized paths to POs for the stem pass
through the capture lines (dominator).
 Note that this is only an approximation!
Capture lines for B

1
1
1 1
B
1 1
(stem)
1
42
Problems of Critical Path
Tracing
 The fault coverage by complete critical path tracing
is approximate.
 Self-masking paths lead to over-estimation
 Multiple-path sensitization leads to under-estimation.
 Not very useful as a standalone simulator.
 Applied to individual fanout-free regions
 Note that stem faults are only simulated to its dominators
and then faults at dominators become representatives.

43
Self-masking Paths
 Detected faults in the fanout-free region: {J/0, H/0, G/1, F/0,
E/0, D/1, C/1}
 Stem criticality is hard to infer from branches.
 For example, is B/1 detectable by the given pattern?
 B/1 is not detectable even though both C and D are critical,
because their effects cancel out each other at gate J
 Self masking when paths go through different inversions

1
G
C 0
0 x 1
D E
B 1
H 1 J
1 F
44
Multiple Path Sensitization

A
1
G 1
1 C 1
B D
H 1 J
(stem)
1
F

Both C and D are not critical, yet B is critical and B/0

can be detected at J by multiple path sensitization.

45
Techniques for Sequential Fault
Simulation

 Fault simulation without restoration

 Fault grouping for parallel fault simulation
 Single Event Faults
 Management of hypertrophic faults
 Parallel pattern simulation for sequential
circuits

46
Sequential Circuit Model

 For sequential circuits, a Huffman model will

be used for the following discussion.

PI Combinational PO
Logic
PPI PPO

FFs

PPI: pseudo primary inputs (i.e., outputs of flip-flops)

PPO: pseudo primary outputs (i.e., inputs of flip-flops)

47
Faulty State in Sequential
Simulation
 Faults will propagate to FF’s
 Need to record faulty states
 Like multiple faults
P1 P2 P3
PO PO PO
f f f

S0 S1 S2 S3

Ex: Input Sequence (P1, P2, P3)

State Sequence (S0  S1  S2  S3)
48
Fault Simulation without
Restoration
 A new fault can be simulated without restoring
status of previous fault status to fault-free value.
 To store and restore fault-free values is inefficient
 Techniques for simulation without restoration
 Only two sets of values are retained at each gate: one for
fault-free and one for faulty ones.
 Each active fault at any given time is given a unique
identifier (ID).
 Only faulty values with the same ID are used.

 Otherwise, true values are used.

 Efficient in both time and memory space[ROOFS89].

49
Simulation without Restoration

POs PIs POs

PIs
F1

PPIs PPOs PPIs PPOs

F2

With Restoration: Effect of F1 is cleared before simulating F2

PIs F1 POs

PPIs PPOs
F2

Without Restoration: F2 is simulated right over effect of F1

50
Fault Grouping

 Faults with coincident events can be grouped

together for parallel simulation.
 Static fault grouping
 Based on circuit structure such as fan-in cone, depth-first
path from POs.
 Dynamic fault grouping
 Fault grouped according to the similarity of faulty states
 At the beginning of each time frame, faults are
dynamically re-grouped for effective usage of all bits in a
word

51
 Fault Grouping in Parallel
Fault Simulation
 The lower grouping case is
F1 POs
PIs evidently more desirable than the
upper case because similar faulty
F3
PPIs PPOs events are simulated in parallel.
F2  Similar events have higher
probability to be
 dropped together
POs
PIs F1  detected together
F3  Distinct faulty events will
PPIs F2 PPOs cause unnecessary simulation
of inactive faults

52
 Single Event Faults
 Single event faults are those
whose effects originate only
F1 POs from the fault sites of the
PIs
current time frame.
 Sophisticated combinational
PPIs PPOs techniques, such as simulate-
F2 to-dominators, can then be
applied with significant
performance improvement.
For circuit in a time frame, faults  Only single-event stem faults
are classified into single event or multiple-event faults are
faults, e.g. , F1, and multiple event parallel-simulated.
faults, e.g., F2.
 [HOPE DAC92]
53
Hypertrophic Faults
 A hypertrophic fault is a fault that diverges from the
fault-free circuit with a large number of X’s
 Usually a stuck-at fault occurring at a control line and thus
prevents the circuit initialization
 A small number of hypertrophic faults can account for a large
percentage of fault events and CPU time
 These faults are sometimes dropped
 as potentially detected faults to reduce simulation time.
(Fault coverage is approximate)
 In parallel fault simulator
 such as PROOFS, these faults can be simulated in parallel
with fault-free circuit with little additional memory while
achieving performance close to approximate simulator
[HyHOPE IEE Circuits, Devices and Systems 94].

54
Parallel Pattern Simulation for
Sequential Circuits
 Sequential circuits are state dependent by nature
 However, many of them have a short memory, which can
be exploited by parallelism of sequences or patterns.
 The basic mechanism of both parallel sequence and
pattern
 To initialize unknown FFs as Xs
 Simulate the circuit and update the FFs by multiple passes.
 States will converge to the true values eventually.
 The convergence rate (# of passes)
 Determines the speed of simulation.
 Usually small compared with the word length
 Dependent on the circuit as well as the given sequence.

55
 Sequential Simulation
Example

B=XXXX
A=0100 C=XXXX

4th 1st All initialized to X

1st A=0 B=XXX1 C= XX1X

A=0 B=XX11 C= X11X
A=1 B=X011 C= 011X
4th A=0 B=1011 C=1011X

To be used for 5th

56
Parallel Sequential Simulation
Example

B=XXXX
A=0100 C=XXXX

A=0100 B=1X11 C=1X11X

A=0100 B=1011 C=1011X
A=0100 B=1011 C=1011X

Converge for three passes

57
Parallel Sequential Simulation
with Look-ahead Heuristic
These three states
use the previous values.
B=XXXX
A=1100 C=0111

A=1100 B=1011 C=10111

only one pass!

Usually most state variables stay the same, so they are

good guess for next simulation.
58
Parallel Sequential Simulation
Example (If Look-ahead not used)

B=XXXX
A=1100 C=XXX1

A=1100 B=XX11 C=XX111

A=1100 B=X011 C=X0111
A=1100 B=1011 C=10111

Also need three passes

59
An Extreme Example of Short-
Memory Circuit

A
Comb. Comb. out1
B logic logic
R1 R2
R3
out2
C

clk
A pipelined data-path

Because there is no feedback, every patterns can be simulated

independently.
60
Fault Grading
 Approximate fault coverage
 Can be obtained in much shorter computational time
than regular fault simulation.
 Not suitable for high fault coverage.
 It often occurs that the accuracy requirement exceeds
error ranges of fault grading.
 Typical fault grading methods:
 Toggle test, e.g. DATAS
 Detection probability computation, e.g. STAFAN
 Fault sampling
 Estimate from a selected subset of total faults

61
Toggle Test
 Circuit node transition
 is computed during logic simulation and the number of
node transition or toggle rate is used as the basis of fault
coverage estimation.
 e.g. zero toggle rate implies either s-a-0 or s-a-1 is not
detected.
 Only logic simulation is performed.
 very low computational cost
 Controllability-based estimation
 Single stuck-at faults are only activated but not necessary
propagated to POs.

62
STAFAN
 Compute fault detection probability from logic
simulation.
 dl = detection probability of s-a-0 on l = C1(l)O(l)
 dl = detection probability of s-a-1 on l = C0(l)O(l)

0 - count 1 - count
C0(l )  , C1(l ) 
n n
sensitization - count
S (l )  l
n m
O( l )  S (l )O( m)

- m is the immediate successor of l

- observability can be computed backwards from POs
63
STAFAN(cont.)

 The probability of detecting a fault with n test vectors

d n  1 (1 d )n
f f
 n is the # of vectors
 (1-df)n is prob. of not being detected after n test vectors

 d nf
 The fault coverage is f 


 Φ is the number of total faults of interests

 More sophisticated than toggle test with same computation
complexity 64
 Fault Sampling

 M: total number of collapsed faults

m: number of faults randomly selected
K: number of faults detected by the test set T
k: number of selected faults detected by T
 Actual fault coverage F = K/M
 Pk(M, m, K): the probability that T will detect k faults
from a random sample size of m, given that it
detects K faults from the entire set of M faults.

65

CkK CmMkK
Pk (m, M , K ) 
CmM

 Pk is hypergeometric distribution with

mean mk  m K M  mF
s
variance k  m K M [1  k M ] ( M  m) ( M  1)
2

 mF (1  F )(1  m M )
 For large M, this distribution can be
approximated by a normal distribution with
mean mk and standard deviation sk.

66
 The estimated fault coverage f is a random
variable with normal distribution:

m f  mk m  F
s 2f  s k2 m 2  (1 m) F (1  F )(1  m M )
 With a confidence level of 99.7%, the estimated
fault coverage f[F-3sf,F+3sf].

emax  3 F (1  F )(1  m M )1 m
 3 F (1  F ) m if m  M

Independent of M!!
67
Maximum Errors of the Estimated
Fault Coverage

68