VLSI TESTING

FAULT MODELING & SIMULATION

1
ACKNOWLEDGMENT

• This slides has been inspired and adapted from

• Professor James Chien Mo Li (VLSI Test © National Taiwan University)

2
FAULT SIMULATION
• Introduction
• Fault simulation techniques
 Serial fault simulation
 Parallel fault simulation (1965)
 PPSFP (1985)
 Deductive fault simulation (1972)
 Concurrent fault simulation (1974) *
• Alternatives to fault simulation
• Issues of fault simulation
• Concluding remarks

* Based on textbook
“VLSI Test Principles and Architectures” 3
by Wang, Wu, and Wen
CONCURRENT FAULT SIMULATION [ULRICH 74]
• Observation
 Fault activity is often sparse both in time and space
 Example: g sa0 fault only affects lower part of circuit
• Idea: can we just simulate parts of faulty circuit that differs from good circuit?

a 1
0 0
d 1 1
c 0 1 0/1 f
1 0/1
1 g 1/0
b
g sa0 1/0

Concurrent fault sim. Is

4
event-driven sim. with good/bad events together
VLSI Test 5.4 © National Taiwan University
 BAD GATE
• Every good gate has a list of bad gates
• Bad-gate
 Represents fault effect of a fault
 At least one gate input or output differs from its corresponding
good-gate if the fault is present
 A bad gate is denoted by
 Fault: a stuck-at 0 , b stuck-at 0
 Faulty input value, faulty output value

VLSI Test 5.4 © National Taiwan University

 EXAMPLE (P1)
• Fault-free simulation, Pattern P1 = 010
• Event-driven simulation
• Good events are events occur in a good circuit

VLSI Test 5.4 © National Taiwan University

 EXAMPLE (P1)
• Consider only three faults: A/1, J/0, C/0 (WWW Fig 3.30)
 Good gates in white: G1 ~ G4
 Bad gates in gray: A/1, J/0, C/0
• A bad gate is invisible if its faulty output same as good values
 C/0 J/0 are invisible
• A bad gate is visible if its faulty output different from good values
 A/1 is visible

VLSI Test 5.4 © National Taiwan University

 BAD EVENTS
• Bad events: Events in faulty circuit, and different from good events
• Good events activate both good-gates and bad-gates for evaluation
• Bad events only activate bad-gates of same fault for evaluation
• Only events of visible bad gates will be propagated
 Invisible bad gates will not trigger any bad event
• Example:
 Good events in white: A u→0, H u→0 , …
 Bad events in gray
 G2 A/1: u→1

8
 EXAMPLE (P1)
• Bad gate diverges from its good gate if its faulty I/O values are
different from good values
• Example:
 Bad gate (G4 A/1) diverges from its good gate
 A/1 is detected by P1

A/1: u→0

VLSI Test 5.4 © National Taiwan University

 EXAMPLE (P2)
• P1 → P2 010 → 001; Note: no other good event inside circuit
• C/0 becomes newly visible
• A/1, C/0 detected by P2 Although A/1 has been detected,
it is not dropped for demo purpose
0

C/0: 1→0

10

VLSI Test 5.4 © National Taiwan University

 EXAMPLE (P3)
• P2→ P3 001→100
• Bad gate converges (disappear) to its good gate if its faulty I/O
values become same as good values (and they are not local
faults)
• Example : Bad gates A/1 C/0 converged
 Bad gate J/0 diverged
 J/0 detected by P3

J/0: 0→1

11

VLSI Test 5.4 © National Taiwan University

 CONCURRENT FAULT SIM. FLOW
• WWW Fig 3.33

12

VLSI Test 5.4 © National Taiwan University

CONCURRENT FAULT SIMULATION SUMMARY
• Advantages
 Even faster than deductive fault simulation
 Delay fault can be supported
 Sequential fault simulation can be supported
• Disadvantage
 Difficulty in memory management
 Memory requirement not predictable

13

VLSI Test 5.4 © National Taiwan University

 FFT
• Q1: In P2, why no bad events there?
• Q2: Why delay fault is supported?
• Q3: Why sequential circuit ok?
Q: why no bad events here?

C/0: 1→0 14

VLSI Test 5.4 © National Taiwan University

COMPARISON OF TECHNIQUES

Items Serial PPSFP Deductive Concurrent

unknown logic ☺ ☺  ☺
value
Delay model ☺   ☺

Run time  ☺ ☺ ☺

Sequential ☺  ☺ ☺
circuits
Memory ☺ ☺  

15

VLSI Test 5.7 © National Taiwan University

 MOTIVATING PROBLEM
• Boss: Why can’t we speed up design sign-off?
• You: But the fault simulation is slow…
• Boss: We do not need exact fault coverage. Just give me an
estimation and DO IT FAST!

What Should You Do? 16

VLSI Test 5.6 © National Taiwan University

ALTERNATIVES TO FAULT SIMULATION
• Q: Is exact fault simulation necessary?
 Exact fault simulation is too expensive
 Sometimes, we just want to know approximate fault coverage
 with reasonable error

• Approximation is good for

 DFT check in early design phase
 Functional test pattern evaluation
• Approximation is NOT good for
 ATPG
 Diagnosis

17

VLSI Test 5.6 © National Taiwan University

TOGGLE COVERAGE (DEF-1)
 # of different values in node i
toggle coverage = all nodes i
2  total # of nodes
# = numbers
0 0 1 0 0 0

1 1 0
1 1 0
1 0 0

0 1 0 1 1 0 1 1 0 0 0 1

Toggle Coverage = 17/18 =94%

18

VLSI Test 5.6 © National Taiwan University

 TOGGLE COVERAGE
☺ Advantage: Toggle coverage is easy to obtain
 Logic simulation only, NO fault simulation
 Disadvantage: Toggle coverage is very optimistic
 Fault activation only, NO fault propagation

0 0 1 0 0 0

1 1 0
1 1 0
1 0 0

0 1 0 1 1 0 1 1 0 0 0 1

TC is Upper Bound of FC
Fault Coverage = 11/18 = 61% see 5.3 P.10 19

5 Toggle Coverage = 17/18 =94%

VLSI Test 5.6 © Nation al Taiwan University
 QUIZ
Q: Apply 3 patterns to this circuit of 7 nodes. Toggle coverage =?
A:

101
a

100
b

20

VLSI Test 5.6 © National Taiwan University

TOGGLE COVERAGE (DEF-2)
 # of different transitions in node i
toggle coverage = all nodes i
2  total # of nodes

0 0 1 0 0 0

1 1 0
1 1 0
1 0 0

0 1 0 1 1 0 1 1 0 0 0 1

Toggle Coverage = 9/18 =50%

DEF-2 more stringent 21

VLSI Test 5.6 © National Taiwan University

 FAULT SIMULATION
• Introduction
• Fault simulation techniques
• Comparison of fault simulation
• Alternatives to fault simulation
 Toggle coverage
 Fault sampling (1974)
 Critical path tracing (1979)
• Issues of fault simulation
• Concluding remarks

22

VLSI Test 5.6 © National Taiwan University

 FAULT SAMPLING [BUTLER 74]
• Idea: Actual fault simulation of whole circuit is too slow
Can we just sample a small portion of faults?
 Like Polling before election
• Notation
 M: number of total faults
m: number of sampled faults
K: number of total faults detected (unknown)
k: number of sampled faults detected
 Actual fault coverage F = K/M (unknown)
sampled
 Sampled fault coverage f = k/m

f=k/m

F=K/M
23
total population
9 VLSI Test 5.6 © National Taiwan University
 FAULT SIMULATION
• Introduction
• Fault simulation techniques
• Comparison of fault simulation
• Alternatives to fault simulation
 Toggle coverage
 Fault Sampling (1974)
 Critical path tracing (1979)
• Issues of fault simulation
• Concluding remarks

24

VLSI Test 5.6 © National Taiwan University

CRITICAL PATH TRACING (CPT) [ROTH 79]
• x is Critical Signal
x’s value change causes some primary output values to change
• Critical path
 All signals on this path that are critical signals
• Example: critical signals are circled

1 0 0
1 0 0
1 1 0

Note: In timing analysis, critical path has different definition

Critical path = Path with the longest path delay

25

VLSI Test 5.6 © National Taiwan University

 CPT ALGORITHM [ABRAMOVICI 84]
• Critical Path Tracing: Start from primary outputs to primary inputs
If gate output is critical, backtrace its critical gate input(s)
• Example: fanout-free cone (FFC)
 Critical signals: a, b, f, g. Critical paths: afg and bfg

1 a 1
f
1 b
g 1
1 c
0 d 0

CPT (O) /*O is a node*/

1. foreach gate input g of O
2. if (g is critical signal) then
3. CPT (g) ;
4. else return; 26

VLSI Test 5.6 © National Taiwan University

 CPT THEOREM
THEOREM:
If critical signal g has good value v, then g stuck-at v’ fault is detected

• Example: Detected faults: a SA0, b SA0, f SA0, g SA0

1 a 1
f
1 b
g 1
1 c
0 d 0

• CPT Advantages:
 CPT can be done in linear time
 Only logic simulation needed for FFC
 Used in first commercial ATPG tool, LASER

CPT Is Very Fast … but 27

VLSI Test 5.6 © National Taiwan University

 HOW ABOUT FANOUT STEM?
• L is critical; F is non-critical
• E is non-critical

1 1
0
1
1

0 0
1 1
?

Is This Always The Case? 28

Fanout stems are non-critical?
19 VLSI Test 5.6 © National Taiwan University
 QUIZ
Q: Determine if fanout stem E is critical or not

A:

CPT Does NOT Work Well

29
when Fanout Reconverges
20 VLSI Test 5.6 © National Taiwan University
 SO… WHAT SHOULD WE DO?
• 1. Count fanout stems as non-critical
Fast but fault coverage pessimistic

• 2. Only fault simulate fanout stems, CPT in fanout-free cones
 Slow but fault coverage accurate

fanout-free cone 30
fanout stem
21 VLSI Test 5.6 © National Taiwan University
 SUMMARY
• Alternatives to fault simulation, fast but inaccurate

 Toggle coverage
Only logic simulation needed
 Fault Sampling
 Only fault simulate a small portion of faults
 Critical path tracing
 Linear time for fanout-free cones
 Still need fault simulation when fanouts reconverge

31

VLSI Test 5.6 © National Taiwan University

 FAULT SIMULATION
• Introduction
• Fault simulation techniques
• Alternatives to fault simulation
• Issues of fault simulation
• Conclusion

32

VLSI Test 5.7 © National Taiwan University

 ISSUES OF FAULT SIMULATIONS
• Long CPU time
 Distributed computing, or Fault sampling
• Large memory requirement
 Partition faults into multiple simulation passes
• Potentially detected faults
• Compatibility with logic simulation

33

VLSI Test 5.7 © National Taiwan University

 SPEED AND MEMORY SOLUTIONS
• 1. Multiple-pass fault simulation
 Run only small portion of faults per pass
• 2. Distributed fault simulation
 Distribute faults to more than one computers
• 3. Emulation
 Use hardware emulator, like FPGA

Fault List #1

• *A simulation pass is a single simulation run

 from beginning to end of test patterns

34

VLSI Test 5.7 © National Taiwan University

 POTENTIALLY DETECTED FAULTS
• DEF: faults that may or may not be detected in practice
 Detection cannot be determined by fault simulation
• Possible reasons for potentially detected faults
 Bus contention, Oscillation, High impedance, Unknown
• Examples:
1

1 c=0

1
b X
1 X SA 1

SA 0 Fault detected?
• Different tools have different ways to calculate FC
35
 Please see tool manual for details
VLSI Test 5.7 © National Taiwan University
COMPATIBILITY WITH LOGIC SIMULATION
• To speed up fault simulation, many tools requires circuits to be
represented in a library models pre-defined by tools
• Functional verification logic simulations often involve mixed-level
codes, which make such modeling very difficult
 Circuit delay
 RTL behavior description
 User Defined Primitives (UDP)
 DFF, MUX

36

VLSI Test 5.7 © National Taiwan University

 FAULT SIMULATION
• Introduction
• Fault simulation techniques
• Comparison of fault simulation
• Alternatives to fault simulation
• Issues of fault simulation
• Conclusion

37

VLSI Test 5.7 © National Taiwan University

 COMMERCIAL TOOLS
• Cadance
 Verifault
• Mentor Graphic:
 Fastscan, flextest
• Synoopsys
 Tetramax
• Syntest
 Turboscan
 TurboFault

38

VLSI Test 5.7 © National Taiwan University

 REFERENCES
• [Abramovici 1984] M. Abramovici, P. R. Menon, and D. T. Miller, “Critical Path Tracing:
An Alternative to Fault Simulation,” IEEE Design and Test of Computers, 1984.
• [Armstrong 1972] D. B. Armstrong, A deductive method for simulating faults in logic
circuits, IEEE Trans. Comput., C-21(5), 464–471, 1972.
• [Butler 1974] T. T. Butler, T. G. Hallin, J. J. Kulzer, and K. W. Johnson, LAMP:
Application to switching system development, Bell System Tech. J., 53, 1535–1555,
1974.
• [Cheng 1989] W. T. Cheng and M. L. Yu, Differential fault simulation: A fast method
using minimal memory, in Proc. Des. Automat. Conf., June 1989, pp. 424–428.
• [Jain 1985] S. K. Jain and V. D. Agrawal, Statistical fault analysis, IEEE Des. Test
Comput., 2(1), 38–44, 1985.
• [Seshu 1965] S. Sesuh and D. N. Freeman, On improved diagnosis program, IEEE
Trans. Electron. Comput., EC-14(1), 76–79, 1965.
• [Ulrich 1974] E. G. Ulrich and T. Baker, Concurrent simulation of nearly identical
digital networks, IEEE Trans. Comput., 7(4), 39–44, 1974.
• [Waicukauski 1985] J. A. Waicukauski, E. B. Eichelberger, D. O. Forlenza, E.
Lindbloom, and T. McCarthy, Fault simulation for structured VLSI, Proc. VLSI Syst.
Des., 6(12), 20–32, 1985.

39

VLSI Test 5.7 © National Taiwan University

COMPARISON OF TECHNIQUES

Items Serial PPSFP Deductive Concurrent

unknown logic ☺ ☺  ☺
value
Delay model ☺   ☺

Run time  ☺ ☺ ☺

Sequential ☺  ☺ ☺
circuits
Memory ☺ ☺  

40

VLSI Test 5.7 © National Taiwan University

 CONCLUSION
• Usage of fault simulation
 ATPG, fault grading, diagnosis
• Techniques
 Serial, parallel, PPSFP, deductive, concurrent
• Most popular technique in industry now
 PPSFP is simple for comb. ckt (or seq. ckt with full scan)
 Concurrent is good for both comb./seq. ckt

41

VLSI Test 5.7 © National Taiwan University