Combinational ATPG
Overview Major ATPG algorithms
Definitions D-Algorithm (Roth) -- 1966
D-cubes Bridging faults Logic gate function change faults
PODEM (Goel) -- 1981
X-Path-Check Backtracing
Summary
2/10/2012 2
Forward Implication
Results in logic gate inputs that are significantly labeled so that output is uniquely determined AND gate forward implication table:
2/10/2012
Backward Implication
Unique determination of all gate inputs when the gate output and some of the inputs are given
2/10/2012
Implication Stack, Decision Tree, and Backtrack Stack Tree
Unexplored Present Assignment Searched and I f S h d d Infeasible ibl
E
1
1 0
0 0
2/10/2012
B
1 0
1
5
Objectives and Backtracing in ATPG
Objective desired signal value goal for ATPG
Guides it away from infeasible/hard solutions Uses heuristics
Backtrace Determines which primary input and value to set to achieve objective
U h i ti such as nearest PI Use heuristics h t
Forward trace Determines gate through which the fault effect should be sensitized
Use heuristics such as output that is closest to the present fault effect
2/10/2012 6
Branch and Bound Branch-and-Bound Search
Efficiently searches binary search tree Branching At each tree level selects which input level, variable to set to what value Bounding Avoids exploring large tree portions by artificially restricting search decision choices ifi i ll i i hd i i h i
Complete exploration is impractical Uses heuristics
Backtracking Search fails, therefore undo some of the work completed and start searching from a location where search options still exist p
2/10/2012
D Algorithm D-Algorithm Roth (1966)
Fundamental concepts invented:
First complete ATPG algorithm D-Cube DC b D-Calculus Implications forward and backward Implication stack Backtrack Test Search Space
2/10/2012
Singular Cover Example g p
Minimal set of logic signal assignments to represent a function show prime implicants and prime implicates of Karnaugh p p p p g map (with explicitly showing the outputs too)
2/10/2012
Gate AND 1 2 3
Inputs Output Gate B A d NOR X 0 0 1 0 X 0 2 1 1 1 3
Inputs Output X 1 0
1 X 0
F
0 0 1
Primitive D-Cube of Failure D Cube
Models circuit faults:
Stuck-at-0 Stuck-at-1 Other f lt Oth faults, such as B id i fault ( h t circuit) h Bridging f lt (short i it) Arbitrary change in logic function
AND Output sa0: 1 1 D 1 D AND Output sa1: 0 X D X 0 D Wire sa0: D p g Propagation D-cube models conditions under
which fault effect propagates through gate
2/10/2012 10
Construction of Primitive D-Cubes of Failure
1. 1 Make cube set 1 when good machine output
is 1 and set 0 when good machine output is 0 2. Make cube set 1 when failing machine output is 1 and 0 when it is 0 3. Change 1 outputs to 0 and D-intersect each cube with every 0. If intersection works, change output of cube to D 4. 4 Change 0 outputs to 1 and D intersect each D-intersect cube with every 1. If intersection works, change output of cube to D g p
2/10/2012 11
Gate Function Change D-Cube of Failure Fail re
Cube-set a b c 0 0 1 0 1
2/10/2012
Cube-set
a b
0 1 1 0
c
D D
0 X 1 0 1 X
X 0 1 0 X 1
0 0 PDFs for 1 AND changing g g 0 to OR 1 1
12
Propagation D Cube D-Cube
Collapsed truth table entry to characterize logic Use Roths 5-valued algebra AND gate: use the rules given earlier using and but in thi b t i this case work with good circuit only k ith d i it l
Write all primitive Cubes of AND gate and then create propagation cubes
D 1 D D 1 D
B
1 D D D D 1
D D D D D D
13
2/10/2012
D-Cube Operation of D-Intersection DC b O i f DI i
undefined (same as ) or requires inversion of D and D D-intersection: 0 0 = 0 X = X 0 = 0 1 1 = 1 X = X 1 = 1 X X = X D-containment 0 1 X D D
Cube a contains Cube b if b is a subset of a
2/10/2012
0 1 X D D
0 0
1 1
0 1 X D D
14
Implication Procedure
1. 1 Model fault with appropriate primitive D D2. 2 3.
cube of failure (PDF) Select propagation D-cubes to propagate fault effect to a circuit output (D-drive procedure) Select singular cover cubes to justify internal circuit signals (Consistency procedure) Put signal assignments in test cube g g Regrettably, cubes are selected very arbitrarily by D-ALG y y
15
2/10/2012
D Algorithm D-Algorithm Top Level
1. Number all circuit lines in increasing level order from PIs to POs; 2. Select a primitive D-cube of the fault to be the test cube; Put logic outputs with inputs labeled as D (D) onto
the D-frontier;
3. D-drive (); 4. Consistency (); 5. return ();
2/10/2012 16
D-Algorithm D-drive
while (untried fault effects on D-frontier)
select next untried D-frontier gate for propagation; while (untried fault effect fanouts exist)
select next untried fault effect fanout; generate next untried propagation D-cube; D-intersect selected cube with test cube; if (intersection fails or is undefined) continue; if (all propagation D-cubes t i d & f il d) break; ( ll ti D b tried failed) b k if (intersection succeeded) add propagation D-cube to test cube -- recreate D-frontier; Find all forward & backward implications of assignment; save D-frontier, algorithm state, test cube, fanouts, fault; break; else if (intersection fails & D and D in test cube) Backtrack (); 2/10/2012 if (intersection fails) break; else
17
if (all fault effects unpropagatable) Backtrack ();
D-Algorithm -- Consistency
g = coordinates of test cube with 1 & 0 di t f t t b ith 1s 0s; if (g is only PIs) fault testable & stop; for (each unjustified signal in g)
Select highest # unjustified signal z in g, not a PI; if (inputs to gate z are both D and D) break; while (untried singular covers of gate z)
select next untried singular cover; if (no more singular covers) If (no more stack choices) fault untestable & stop; ( ) p; else if (untried alternatives in Consistency) pop implication stack -- try alternate assignment; else Backtrack (); D-drive ();
If (singular cover D-intersects with z) delete z from g, add inputs to singular cover to g, fi d all forward and backward implications of i l t find ll f d db k d i li ti f new assignment, and break; 2/10/2012 18 If (intersection fails) mark singular cover as failed;
Backtrack
if (PO exists with fault effect) Consistency (); else pop prior implication stack setting to try alternate assignment; if (no untried choices in implication stack)
fault untestable & stop; f
else return;
2/10/2012
19
Circuit Example 7.1 and Truth Table
a
0 0 0 0 1 1 1 1
2/10/2012
Inputs
b
0 0 1 1 0 0 1 1
c
0 1 0 1 0 1 0 1
Output
0 0 0 1 0 0 0 0
20
Singular Cover & Propagation D-Cubes
A
1 0
B
1 0 1 0
C
1 0
d
1 0 0
e
0 1 1 1 0 D D D 0 D D
Singular cover
Used for justifying lines
D 1 D
1 D D D 1 D
1 D D
1 0 D D D D 0 D
0 0 1
Propagation D-cubes Conditions under
which difference between good/failing b t d/f ili machines propagates
D D D
2/10/2012
21
Steps for Fault d sa0 Fa lt
Step A B C d e F 1 1 1 D 2 3 Cube type PDF of AND gate
D 0 D Prop. D-cube for NOR D cube 1 1 0 Sing. Cover of NAND
2/10/2012
22
Example 7.3 Fault u sa1
Primitive D-cube of Failure
1
0 sa1 D
2/10/2012
23
Example 7.3 Step 2 u sa1
Propagation D-cube for v
1 0
0 sa1 D
2/10/2012
24
Example 7.3 Step 2 u sa1
Forward and backward implications
1 0 0 1 0 D sa1 D 1
2/10/2012
25
Inconsistent
d = 0 and m = 1 cannot justify r = 1 (equivalence)
Backtrack Remove B = 0 assignment
2/10/2012
26
Example 7.3 Backtrack
Need alternate propagation D-cube for v
1
0 sa1 D
2/10/2012
27
Example 7.3 Step 3 u sa1
Propagation D-cube for v
1
0 sa1 D D
2/10/2012
28
Example 7.3 Step 4 u sa1
Propagation D-cube for Z
1
0 sa1 D D
D 1
2/10/2012
29
Example 7.3 Step 4 u sa1
Propagation D-cube for Z and implications
1 1 1 1 1 0 D 1
2/10/2012
0 sa1
30
PODEM -- G l Goel (1981)
New concepts introduced:
Expand binary decision tree only around primary inputs Use X-PATH-CHECK to test whether DA C C frontier still there Objectives -- bring ATPG closer to propagating D (D) to PO Backtracing
2/10/2012 31
Motivation
IBM i t d d semiconductor DRAM introduced i d t memory into its mainframes late 1970s Memory had error correction and translation circuits improved reliability
D-ALG unable to test these circuits D ALG Search too undirected Large XOR-gate trees g g Must set all external inputs to define output Needed a better ATPG tool
2/10/2012 32
PODEM High Level Flow High-Level
1. 2. 3. 4.
Assign binary value to unassigned PI Determine implications of all PIs Test Generated? If so, done. Test possible with more assigned PIs? If maybe, go t St 1 b to Step 5. Is there untried combination of values on assigned PIs? If not, exit: untestable fault not 6. Set untried combination of values on assigned PIs using objectives and backtrace. Then, g g j , go to Step 2
2/10/2012 33
Example 7.3 Again
Select path s Y for fault propagation
sa1
2/10/2012
34
Example 7.3 -- Step 2 s sa1
Initial objective: Set r to 1 to excite fault
1
sa1
2/10/2012
35
Example 7.3 -- Step 3 s sa1
Backtrace from r
1
sa1
2/10/2012
36
Example 7.3 -- Step 4 s sa1
Set A = 0 in implication stack
1
0 sa1
2/10/2012
37
Example 7.3 -- Step 5 s sa1
Forward implications: d = 0, X = 1
1
0 0 sa1 1
2/10/2012
38
Example 7.3 -- Step 6 s sa1
Initial objective: set r to 1
1
0 0 sa1 1
2/10/2012
39
Example 7.3 -- Step 7 s sa1
Backtrace from r again
1
0 0 sa1 1
2/10/2012
40
Example 7.3 -- Step 8 s sa1
Set B to 1. Implications in stack: A = 0, B = 1
1
0 1 0 sa1 1
2/10/2012
41
Example 7.3 -- Step 9 s sa1
Forward implications: k = 1 m = 0 r = 1 q = 1 Y = 1, 0, 1, 1, 1, s = D, u = D, v = D, Z = 1
0 1 1 1 0 0 sa1 1 D D D 1 1
2/10/2012
42
Backtrack -- Step 10 s sa1
X PATH CHECK shows paths s Y and X-PATH-CHECK u v Z blocked (D-frontier disappeared)
1
0 0 sa1
2/10/2012
43
Step 11 -- s sa1
Set B = 0 (alternate assignment)
1
0 0 sa1
2/10/2012
44
Backtrack -- s sa1
Forward implications: d = 0 X = 1 m = 1 r = 0 0, 1, 1, 0, s = 1, q = 0, Y = 1, v = 0, Z = 1. Fault not sensitized.
0 0 0 0 1 sa1 1 0 1 1 0 1 1
2/10/2012
45
Step 13 -- s sa1
Set A = 1 (alternate assignment)
1
1 sa1
2/10/2012
46
Step 14 -- s sa1
Backtrace from r again
1
1 sa1
2/10/2012
47
Step 15 -- s sa1
Set B = 0. Implications in stack: A = 1, B = 0
1
1 0 sa1
2/10/2012
48
Backtrack -- s sa1
F Forward i li ti d implications: d = 0 X = 1 m = 1 r = 0 0, 1, 1, 0. Conflict: fault not sensitized. Backtrack
0 1 0 0 1 sa1 1 0 1 1 0 1 1
2/10/2012
49
Step 17 -- s sa1
Set B = 1 (alternate assignment)
1
1 1 sa1
2/10/2012
50
Fault Tested -- Step 18 s sa1
Forward implications: d = 1 m = 1 r = 1 q = 0 s = 1, 1, 1, 0, D, v = D, X = 0, Y = D
1 1 1 1 1 sa1 0 D X
2/10/2012 51
Backtrace (s, vs) Pseudo-Code
v = vs; while (s is a gate output)
if (s is NAND or INVERTER or NOR) v = v; if (objective requires setting all inputs) select unassigned input a of s with hardest controllability to value v; else select unassigned input a of s with easiest controllability to value v; s = a;
return (s, v) /* Gate and value to be assigned */;
2/10/2012 52
Objective Selection Code
if (gate g is unassigned) return (g, v); select a gate P from the D-frontier; select an unassigned input l of P; if (gate g has controlling value)
c = controlling input value of g;
else if (0 value easier to get at input of XOR/EQUIV gate)
c = 1;
else c = 0; ; return (l, c ); 2/10/2012
53
PODEM Algorithm
while (no fault effect at POs)
if (xpathcheck (D-frontier) (l, vl) = Objective (fault, vf lt); fault (pi, vpi) = Backtrace (l, vl); Imply (pi, vpi); if (PODEM (fault vfault) == SUCCESS) return (SUCCESS); (fault, (pi, vpi) = Backtrack (); Imply (pi, vpi); p if (PODEM (fault, vfault) == SUCCESS) return (SUCCESS); Imply (pi, X); return (FAILURE); else if (implication stack exhausted) return (FAILURE); else Backtrack ();
return (SUCCESS);
2/10/2012 54
Summary y
D-ALG First complete ATPG algorithm
D Cube D-Cube D-Calculus Implications forward and backward Implication stack Backup
PODEM
Expand decision tree only around PIs Use X-PATH-CHECK to see if D-frontier exists f Objectives -- bring ATPG closer to getting D (D) to PO Backtracing
2/10/2012 55
Appendices A di
2/10/2012
56
Push-down stack. Records:
Implication Stack
Each signal set in circuit by ATPG Whether alternate signal value already tried Portion of binary search tree already searched
2/10/2012
57
Objectives and Backtracing in ATPG
Objective desired signal value goal for ATPG
Guides it away from infeasible/hard solutions y Uses heuristics
Backtrace Determines which primary input and value to set to achieve objective l t tt hi bj ti
Use testability measures
2/10/2012
58
Bridging Fault Circuit B id i F lt Ci it
2/10/2012
59
Bridging Fault D-Cubes of Failure
Cube-set a 0 0 X 1 1 X 0 0 X 1 1 X 0 X 1 0 1 X
a* b*
0 X 1 X 0 1 1
X 0 1 0 1 D X PDFs for 1 Bridging fault 0 1 D 1 0 1 1
Cube-set
a b a* b*
2/10/2012
60
Example 7.2 Fault E ample 7 2 Fa lt A sa0
Step 1 D-Drive Set A = 1
2/10/2012
61
Step 2 -- E ample 7 2 Example 7.2
Step 2 D-Drive Set f = 0
0 1 D D
2/10/2012
62
Step 3 -- E ample 7 2 Example 7.2
Step 3 D-Drive Set k = 1
1 0 1 D D D D
2/10/2012
63
Step 4 -- E ample 7 2 Example 7.2
Step 4 Consistency Set g = 1
1 0 1 D D 1 D D
2/10/2012
64
Step 5 -- E ample 7 2 Example 7.2
Step 5 Consistency f = 0 Already set
1 0 1 D D 1 D D
2/10/2012
65
Step 6 -- E ample 7 2 Example 7.2
St 6 C i t Step Consistency S t c = 0 S t e = 0 Set 0, Set
1 0 D 0 0 D D 1 D
2/10/2012
66
D-Chain D Chain Dies -- E ample 7 2 Example 7.2
Step 7 Consistency Set B = 0 p y D-Chain dies
X 0 0 1 D 1 0 0 D 1 D D
Test cube: A B, C, D, e, f, g h k L A, B C D e f g, h, k,
2/10/2012 67
Example 7.3 Fault s sa1
Primitive D-cube of Failure
1 D
sa1
2/10/2012
68
Example 7.3 Step 2 s sa1
Propagation D-cube for v
1 D
sa1 0
2/10/2012
69
Example 7.3 Step 2 s sa1
Forward & Backward Implications
1 1 1 1 1 D 0
sa1 0
2/10/2012
70
Example 7.3 Step 3 s sa1
Propagation D-cube for Z test found!
1 1 1 1 1 D 0
sa1 0
D 1
2/10/2012
71
