Module 3
Logic & Fault Simulation
Leon Li and Alex Orailoglu
CSE 244A, UC San Diego
1
Section 1 Simulation for Verification
Specification
Synthesis
Response Design Design Critical or “risky”
analysis changes (netlist) parts of the spec
are checked
Computed True-value
Input stimuli
responses simulation
2
Simulation
• Simulation refers to modeling of a design, its function and performance.
• A software simulator is a computer program; an emulator is a hardware
simulator.
• Simulation is used for design verification:
• Validate assumptions
• Verify logic
• Verify performance (timing)
• Types of simulation:
• Logic or switch level
• Timing
• Circuit
• Fault
3
Modeling for Simulation
• Modules, blocks or components described by
• Input/output (I/O) function
• Delays associated with I/O signals
• Examples: binary adder, Boolean gates, FET, resistors and capacitors
• Interconnects represent
• ideal signal carriers, or
• ideal electrical conductors
• Netlist: a format (or language) that describes a design as an interconnection
of modules. Netlist may use hierarchy.
4
Example: 32-bit Adder
32-bit adder block-level diagram
1-bit full adder 𝐴𝐵 + (𝐴 ⊕ 𝐵) ⋅ 𝐶
𝐴⊕𝐵⊕𝐶
𝐴 + 𝐵 𝐴’ + 𝐵’ = 𝐴 ⊕ 𝐵
5
Verification Heuristics
• A heuristic to verify a regular component like an adder:
• Apply all possible inputs to each full-adder block
1 0 1 0 1 0 1 0
e.g., The all 0 pattern applies
0 0 0 0 0 0 0 0
𝐶!"# 𝐴! 𝐵! = 000 to all FAs
0 0 0 0
0 0 0 0
e.g., The 001010101 pattern
applies 𝐶!"# 𝐴! 𝐵! = 001 to all FAs
6
Verification Vectors
for adders (or arbitrary width)
1 1 0 0 1 1 0 0
Sometimes, alternating
0 1 0 1 between two patterns to
optimize for vector count
7
Fault Coverage of Verification Vectors?
• They offer full SSA fault coverage (as
long as they are testable), regardless of
the specific FA implementation!
What about faults affecting 𝐶!"# ?
Faults affecting 𝐶!"# can always
propagate to the next 𝑆𝑢𝑚 output
(since the 𝑆𝑢𝑚 logic is XORs which
always propagate)
Faults affecting 𝑆$ can always be observed
All 8 combinations are applied
8
Exercise: Counting Faults 32-bit adder block-level diagram
1-bit full adder
7 two-input gates + 2 inverters + 6 fanout locations (stems) + 2 POs
à 14 + 2 + 6 + 2 = 24 fault sites
But let’s ignore 𝐶$%& since it’s already counted as 𝐶!' at the next FA (except for the final FA31)
à(23 * 2 * 32 ) + 2 = 1474 single stuck-at faults
SA0 and SA1 32 blocks
Faults at the final 𝐶%&
Fault site within each FA block
9
Exercise: Counting Faults 32-bit adder block-level diagram
1-bit full adder
We can get rid of 2 faults for each gate (two-input gate or inverter):
Total faults = 1474 – (9*2) * 32 = 898
Equivalence-removed faults within each FA
Faults before collapsing
10
Forward/Backward Simulation
• We know all 8 patterns deliver full SSA fault coverage, but can we do better?
Followed by
Forward Simulation Results Backward Simulation Results
Vectors 3-6 together offer 100% coverage
11
Timing Verification Vectors
• Timing verification requires two vectors with a 1-bit difference.
• e.g., Vector 2 à Vector 6
(2) Set to “propagating” conditions
1 0 1 0 1 0 1 0
0 0 0
0à1 0à1
à1 à1 à1
(3) Trickle a bit-flip
(1) Find critical path through the critical path
12
Modeling Levels
Modeling Circuit Signal Timing Application
level description values
Clock Architectural
Function, Programming 0, 1 and functional
behavior, RTL language-like HDL boundary verification
Logic Connectivity of 0, 1, X Zero-delay Logic
Boolean gates, unit-delay, verification
and Z multiple-
flip-flops and and test
transistors delay
Switch Transistor size 0, 1 Zero-delay Logic
and connectivity, and X verification
node capacitances
Timing Transistor technology Analog Fine-grain Timing
data, connectivity, voltage timing verification
node capacitances
Circuit Analog Continuous Digital timing
Tech. Data, active/
voltage, time and analog
passive component
circuit
connectivity current
verification
13
Section 2
True-Value
Simulation
14
Compiled Code Simulation
• The circuit is described in a language that can be compiled and executed on
a computer.
Netlist Code Representation
Simulate () {
long A,B,C,D,E;
long X1,X2,X3,Q1,Q2;
Read values for A, B, C, D, and E;
X1 = B And C;
X2 = D And E;
X3 = X1 Or X2;
Q1 = Not X3
Q2 = A And X3;
}
Example Source: [Link]
15
Levelization
• A gate should not be simulated until all of its input values are available.
• Levelization is the process of determining the correct gate-simulation order.
• Assign a level number to each gate (and each net) in the circuit.
• Primary inputs and constant signals are assigned a level number of zero.
• The maximum gate input level is incremented by one to obtain the gate level number.
Netlist Levelization
16
Compiled Code Simulation
• A compiled code simulator does not model timing problems - glitches, race
conditions, etc.
• Detailed timing (such as multiple-delay or minmax-delay) is almost impossible to
simulate in the compiled-code.
• Efficient for highly active circuits, but inefficient for low-activity circuits.
• Requires the evaluation of the entire code for any new input value.
• In digital circuits, generally only 1-10% of signals are found to change at any time.
17
Event-Driven Simulation
• Event: a signal change
• Only gates or modules with input events are evaluated
• Delays can be accurately simulated for timing verification
a=1 e=1 0 Time 𝒕𝟎
c=1 0 2
Time 𝒕𝟐
g=1 0 1
2 Time 𝒕𝟒
2
d=0 1 Time 𝒕𝟔
Time 𝒕𝟖
4 f=0 1
b=1
18
Event-Driven Simulation
• Activity list contains gates whose inputs
currently have events
• Event scheduling is the procedure of Time Scheduled Activity
distributing the activity caused by events 𝑡 Events List
over time according to the specified delays 0 𝒄=𝟎 𝒅, 𝒆
1
2 𝒅 = 𝟏, 𝒆 = 𝟎 𝒇, 𝒈
a=1 e=1 0 3
c=1 0 2
4 𝒈=𝟎
g=1 0 1
2 5
2 6 𝒇=𝟏 𝒈
d=0 1
7
4 f=0 1 8 𝒈=𝟏
b=1
19
Time Wheel
• Events are scheduled relative to the current time on a circular stack.
• 𝑚𝑎𝑥 is the largest delay experienced by any event, representing the farthest
time one can schedule ahead.
• Advancing the time by moving the time pointer to the next time slot.
Evaluate
𝑚𝑎𝑥
Current 𝑚𝑎𝑥 this cycle
𝒕=𝟎 𝑚𝑎𝑥 + 1
time
1 𝒕=𝟏
pointer
2 2
Advancing
3 Time +1 3
4 Event link-list 4
5 5 Newly
6 6 Scheduled
7 7 Events
20
Efficiency of Event-Driven Simulator
• Simulates events (value changes) only.
• Speed up over compiled-code can be ten times or more; in large logic circuits
about 1 to 10% of gates become active for an input change.
Steady 0
Steady 0 Large logic
block without
(no event)
0 → 1 event activity
21
Section 3 Fault Simulation
22
Fault Simulation
• Fault simulation Problem:
Given
§ A circuit
§ A sequence of test vectors
§ A fault model
Determine
§ Fault coverage - fraction (or percentage) of modeled faults detected by test vectors
§ Set of undetected faults
• Motivation
§ Determine test quality and in turn product quality
§ Find undetected fault targets to improve tests
23
ATPG System
• Combine the ATPG with a fault simulator into an ATPG system.
• ATPG is the “core solution” to generate test patterns.
• Fault simulator evaluates how a circuit behaves in the presence of faults.
ATPG
Fault Abdullah, Ayub Chin, and Chia Yee
Ooi. "Study on Test compaction in
Simulator high-Level automatic test pattern
generation (ATPG) platform." (2013).
24
Serial Fault Simulation
• Algorithm: Simulate fault-free circuit and save responses. Repeat the
following steps for each fault in the fault list:
• Modify the netlist by injecting one fault
• Simulate modified netlist, vector by vector, comparing responses with saved responses
• If response differs, report fault detection and suspend simulation of remaining vectors
Fault-free netlist on 111 Fault Injected (𝑒 − 𝑆𝐴0) netlist on 111
a=1 e=1 a=1 e=0 Fault
2 Detected!
c=1 c=1
g=1 g=0
2 2
2 2
d=0 d=0
4 f=0 4 f=0
b=1 b=1
25
Serial Fault Simulation
• Advantages:
• Easy to implement; needs only a true-value simulator, less memory
• Most faults, including analog faults, can be simulated
• Disadvantages:
• Much repeated computation; CPU time prohibitive for VLSI circuits
Test vectors Fault-free circuit Comparator f1 detected?
Circuit with fault f1
Comparator f2 detected?
Circuit with fault f2
Comparator fn detected?
Circuit with fault fn
26
Fault Dropping
• Halt simulation of the detected fault, i.e., stop on the first detection.
• Suppose we are to simulate three vectors 𝑉# , 𝑉( , 𝑉) in order
• Fault 𝑓 is detected by 𝑉#
• Do not simulate 𝑓 for 𝑉( and 𝑉)
Simulation result with fault dropping:
Simulation without fault dropping: full records first detection pattern only
1st detection 2nd detection 3rd detection 1st detection
Fault ... Fault
vector vector vector vector
f1 Vector 5 Vector 12 Vector 19 ... f1 Vector 5
f2 Vector 7 Vector 8 ... f2 Vector 7
.... ....
fn Vector 35 Vector 102 ... fn Vector 35
27
Parallel Fault Simulation
• Exploits inherent bit-parallelism of logic operations on computer words to
simulate 𝒘 − 𝟏 faults in each pass, where 𝒘 is the machine word width.
Bit 0: fault-free circuit
Bit 1: circuit with c s-a-0
Bit 2: circuit with f s-a-1
3-bit word 1 1 1
c s-a-0 detected
example a 1 0 1
1 1 1 1 0 1
(1 bit for fault-free and e
b 1 0 1
2 bits for two different c s-a-0
SA faults) g
0 0 0
d f s-a-1 0 0 1
28
Parallel Fault Simulation
• Exploits inherent bit-parallelism of logic operations on computer words to
simulate 𝒘−𝟏 faults in each pass, where 𝒘 is the machine word width.
• If no fault-dropping is used, a parallel fault simulator will run about 𝒘−𝟏 times
faster than a serial fault simulator.
• In parallel fault simulator, all 𝒘−𝟏 faults must be detected before a pass can be
terminated. Therefore, the serial fault simulator gains more by fault dropping.
29
Fault Injection for Parallel Simulation
SA1 Fault SA1 fault Injection with MUX SA1 fault Injection with OR
SA1
𝐴 𝐴 0 𝑆𝑒𝑙 # 𝐴 + 𝑆𝑒𝑙 ⋅ 1 𝐴
= 𝑆𝑒𝑙 + 𝐴
1 1
• Any logical fault 𝑆𝑒𝑙 𝑆𝑒𝑙
behavior can be
modeled by some 0 1 0 1
circuit updates.
Fault-free Fault-free
• SA1: OR
• SA0: AND SA1 Fault SA1 Fault
• Other: MUX & more
30
Fault Injection Example
1 0 1
Source: [Link] 31
Deductive Fault Simulation
• One-pass simulation for each vector.
• Each line 𝑘 contains a list 𝐿$ of faults detectable on it.
• Following true-value simulation of each vector, fault lists of all gate output lines
are updated using set-theoretic rules, signal values, and gate input fault lists.
𝐿. = {𝐴/ } 𝐿2 = {𝐴/ , 𝐶/ }
A Singular AND 𝐴=0
Gate Example 𝐶=0
𝐵=1
𝐿0 = {𝐵1 }
32
Propagation Rules - Simplified
• Suppose AND gate input fault lists have no overlap: 𝑳𝑨 ∩ 𝑳𝑩 = 𝝓.
𝑳𝑪 = {𝑪𝟏} 𝑳𝑪 = 𝑳𝑨 ∪ {𝑪𝟏}
𝐿' 𝐿'
𝐴=0 𝐴=0
𝐶=0 𝐶=0
𝐵=0 𝐵=1
𝐿( 𝐿(
𝑳𝑪 = 𝑳𝑩 ∪ {𝑪𝟏} 𝑳𝑪 = 𝑳𝑨 ∪ 𝑳𝑩 ∪ {𝑪𝟎}
𝐿' 𝐿'
𝐴=1 𝐴=1
𝐶=0 𝐶=1
𝐵=0 𝐵=1
𝐿( 𝐿(
33
Propagation Rules - Simplified
• Suppose OR gate input fault lists have no overlap: 𝑳𝑨 ∩ 𝑳𝑩 = 𝝓.
𝑳𝑪 = 𝑳𝑨 ∪ 𝑳𝑩 ∪ {𝑪𝟏} 𝑳𝑪 = 𝑳𝑩 ∪ {𝑪𝟎}
𝐿' 𝐿'
𝐴=0 𝐴=0
𝐶=0 𝐶=1
𝐵=0 𝐵=1
𝐿( 𝐿(
𝑳𝑪 = 𝑳𝑨 ∪ {𝑪𝟎} 𝑳𝑪 = {𝑪𝟎}
𝐿' 𝐿'
𝐴=1 𝐴=1
𝐶=1 𝐶=1
𝐵=0 𝐵=1
𝐿( 𝐿(
34
Tree Circuit Example
{𝑎0}
𝑎=1 𝑒=0 {𝑏1, 𝑒1}
𝑏=0
{𝑏1}
𝑔=0
{𝑑1} {𝑏1, 𝑒1, 𝑑1, 𝑓1, 𝑔1}
𝑑=0
𝑐=1 𝑓=0 {𝑑1, 𝑓1}
{𝑐0}
35
Circuit with Reconvergence
Detectable at 𝑔
• What if a fault appears at both gate inputs? G
𝐷 w/ 𝑏1 G
𝐷
G
𝐷 fault
{𝑎0}
𝑏𝑡 (𝑏,-. ) 𝑎=1 𝑒=0 { 𝑏1 , 𝑏𝑡1, 𝑒1}
{𝑏1} {𝑏1, 𝑏𝑡1}
𝑏=0 𝑔=0
{𝑏1, 𝑏𝑏1} { 𝑏1 , 𝑏𝑡1, 𝑏𝑏1, 𝑒1, 𝑓1, 𝑔1}
𝑏𝑏 (𝑏/-,,-0 ) 𝑐=1 𝑓=0 { 𝑏1 , 𝑏𝑏1, 𝑓1}
{𝑐0}
36
Circuit with Reconvergence
Detectable at 𝑔
• Let’s try a different pattern of 𝑎𝑏𝑐 = 111 𝐷 w/ 𝑏0
fault
𝐷
𝐷
{𝑎0}
𝑏𝑡 (𝑏,-. ) 𝑎=1 𝑒=1 {𝑎0, 𝑏0 , 𝑏𝑡0, 𝑒0}
{𝑏0} {𝑏0, 𝑏𝑡0}
𝑏=1 𝑔=1
{𝑏0, 𝑏𝑏0}
{ 𝑏0 , 𝑔0}
𝑏𝑏 (𝑏/-,,-0 ) 𝑐=1 𝑓=1 {𝑐0, 𝑏0 , 𝑏𝑏0, 𝑓0}
{𝑐0}
37
Circuit with Reconvergence
Undetectable at 𝑒
• Example where multiple fault 𝐷 w/ 𝑏0
effects kill each other. G fault
1
𝐷
{𝑎0}
𝑎=1 𝑐=1 {𝑎0, 𝑏0 , 𝑏𝑡0, 𝑐0}
{𝑏0} 𝑏𝑡 (𝑏,-. )
𝑏=1 𝑒=1
{𝑏0, 𝑏𝑡0}
{𝑎0, 𝑏𝑡0, 𝑐0, 𝑒0}
𝑏𝑏 (𝑏/-,,-0 ) 𝑑 = 0 { 𝑏0 , 𝑏𝑏0, 𝑑1}
{𝑏0, 𝑏𝑏0}
38
Propagation Rules - Complete
𝐿1
𝑳𝒄
𝐿/
𝐿1
𝑳𝒄
𝐿/
𝐿1 𝑳𝒄
39
Revisit the Example
• Input 𝑎𝑏 = 11
𝑎0 ∪ 𝑏0, 𝑏𝑡0 ∪ 𝑐0
{𝑎0} = {𝑎0, 𝑏0, 𝑏𝑡0, 𝑐0} “In the top list but
𝑎=1 𝑐=1 not in the bottom.”
{𝑏0} 𝑏𝑡 (𝑏,-. )
𝑏=1 𝑒=1
{𝑏0, 𝑏𝑡0}
( 𝑎0, 𝑏0, 𝑏𝑡0, 𝑐0 ∩ 𝑏0, 𝑏𝑏0, 𝑑1 ) ∪ {𝑒0}
= {𝑎0, 𝑏𝑡0, 𝑐0, 𝑒0}
𝑏𝑏 (𝑏/-,,-0 ) 𝑑=0 𝑏0, 𝑏𝑏0 ∪ 𝑑1
{𝑏0, 𝑏𝑏0} {𝑏0, 𝑏𝑏0, 𝑑1}
40
Revisit the Example
• Input 𝑎𝑏 = 01 --> Combine with
even-driven simulation to only
update actively switching paths.
{𝑎1} ( 𝑎1 ∩ 𝑏0, 𝑏𝑡0 ) ∪ 𝑐1 Updated as a result
𝑎=0 𝑐=0 = {𝑎1, 𝑐1} of the input event
{𝑏0} 𝑏𝑡 (𝑏,-. )
𝑏=1 𝑒=0
{𝑏0, 𝑏𝑡0}
{𝑎1, 𝑐1} ∪ {𝑏0, 𝑏𝑏0, 𝑑1} ∪{e1}
= {𝑎1, 𝑐1, 𝑏0, 𝑏𝑏0, 𝑑1, 𝑒1}
𝑏𝑏 (𝑏/-,,-0 ) 𝑑=0 𝑏0, 𝑏𝑏0 ∪ 𝑑1
{𝑏0, 𝑏𝑏0} {𝑏0, 𝑏𝑏0, 𝑑1}
41
Section 4 Testability Measures
Testability
Controllability Observability
42
Purpose of Testability Measures
• Need approximate measure of:
• Difficulty of setting internal circuit lines to 0 or 1 by setting primary circuit inputs
• Difficulty of observing internal circuit lines by observing primary outputs
• Uses:
• Analysis of difficulty of testing internal circuit parts – redesign or add special test
hardware
• Guidance for algorithms computing test patterns – avoid using hard-to-control lines
• Estimation of fault coverage
• Estimation of test vector length
• Analysis method:
• It involves Circuit Topological analysis but no test vectors and no search algorithm.
• Static analysis & Linear computational complexity
• Otherwise, is pointless – might as well use automatic test-pattern generation and
calculate the exact fault coverage and exact test vectors
43
Measure Types
§ SCOAP – Sandia Controllability and Observability Analysis Program
§ Combinational measures:
• CC0 – Difficulty of setting circuit line to logic 0
• CC1 – Difficulty of setting circuit line to logic 1
• CO – Difficulty of observing a circuit line
• Roughly proportional to # circuit lines that must be set to control or observe given line
• Range:
• Controllability CC – 1 (easiest) to infinity (hardest)
• Observability CO – 0 (easiest) to infinity (hardest)
§ (Sequential measures – analogous)
• (SC0, SC1, SO: Roughly proportional to # times a flip-flop must be clocked to control or
observe given line)
44
Controllability Propagation Rules
Set any input to 0
Set all inputs to 1
Set all inputs to 0
Set any input to 1
Take min of input sets
45
More Propagation Examples
46
Observability Propagation Rules
To see 𝑎, we need to
see 𝑧 and set b to 1
To see 𝑎, we need
to see 𝑧 and set b to
whatever
47
More Observability Examples
Observe the stem
from the easiest-to-
observe branch
48
SCOAP Example
Annotation:
CC0, CC1 (CO)
49
SCOAP is Not Perfect with Reconvergence
• SCOAP measures wrongly assume that controlling or observing x, y, z are
independent events, but in reality:
• CC0 (x), CC0 (y), CC0 (z) correlate
• CC1 (x), CC1 (y), CC1 (z) correlate SCOAP: CC0, CC1 (CO)
• CO (x), CO (y), CO (z) correlate Truth: CC0, CC1 (CO for 0, CO for 1)
[Link] 50