1 ECE 538 Krish Chakrabarty 1 ECE 538 VLSI System Testing Krish Chakrabarty Test Generation: Part 1 ECE 538 Krish Chakrabarty 2 Introduction • Classification of test generation methods • Fault table analysis • Boolean difference method • Propagation, implication and justification procedures • D-algorithm • 9-V algorithm (multiple path sensitization)2 ECE 538 Krish Chakrabarty 3 General Approaches • Systematic (algorithmic) – Fault table analysis – Boolean difference method – Fault-oriented methods (D-algorithm, PODEM) – Fault-independent methods (critical path tracing) • Exhaustive/pseudoexhaustive • Random/pseudorandom ECE 538 Krish Chakrabarty 4 Fault Table Analysis • Determine fault table via simulation and solve covering problem • Covering problems are NP-complete • Computationally infeasible 2-input OR gate ab 00 x x x 01 x x 10 x x 11 x a/0 a/1 b/0 b/1 z/0 z/1 Fault a z b Test3 ECE 538 Krish Chakrabarty 5 Fault-Oriented ATPG Procedure Generate_Tests() begin repeat begin Select uncovered fault f Generate test for f Evaluate current fault coverage end until fault coverage > limit, or time runs out end ECE 538 Krish Chakrabarty 6 Boolean Difference The Boolean difference of F(x1, x2 , x3,…, xn) with respect to xi is given by ∂F ∂xi = F(x1, x2 ,…,1, x3,…, xn) ⊕ F(x1, x2 ,…,0, x3,…, xn) A test pattern for xi/0 is an input combination that makes ∂F ∂xi = 1 A test pattern for xi/1 is an input combination that makes ∂F ∂xi = 1 Cofactor w.r.t. xi Cofactor w.r.t. xi xi xi Boolean difference provides input combination for sensitized path4 ECE 538 Krish Chakrabarty 7 Boolean Difference b a c d e f g h i j k To find a test for a/0 or a/1, determine the Boolean difference of output z with respect to a: z ∂z ∂a = ? How to handle internal faults, e.g. j/0? ECE 538 Krish Chakrabarty 8 Key Terminology • Backtrace: move a goal value backwards in a circuit to a primary input • Backtrack: return to a previous decision point in an algorithm and make an alternative decision • D-frontier: Set of gates closest to primary output with D or D on some input • Implication: Determine unique signal values that are forced by signal values already assigned • Justification: Determine values to unspecified inputs of gates whose outputs are specified (backward) • Propagation (D-drive): Determine path values needed to propagate an error signal to a primary output (forward)5 ECE 538 Krish Chakrabarty 9 Testing Fanout-Free Circuits • No (reconvergent) fanout – Propagation path from any line is unique – Each line justification problem is independent of all others Test generation for line l/v in a fanout-free circuit begin set all values to X (unknown) Justify(l,v) if v = 0 then Propagate(l,D) else Propagate(l,D) end ECE 538 Krish Chakrabarty 10 Testing Fanout-Free Circuits err err 1 1 l Error propagation: Propagate(l,err) /* err is D or D */ begin set l to err if l is PO then return k = the fanout gate of l c = controlling value of k i = inversion of k for every input j of k other than l Justify(j,c) Propagate(k,err⊕ i) end6 ECE 538 Krish Chakrabarty 11 Testing Fanout-Free Circuits 1 1 l Line Justification Justify(l,val) begin set l to val if l is PI then return /* l is a gate (output) */ c = controlling value of l i = inversion of l inval = val ⊕ i if(inval = c) then for every input j of l Justify(j,inval) else begin Select one input (j) of l Justify(j,inval) end 1 0 1 l X X 0 ECE 538 Krish Chakrabarty 12 Functional vs Structural Testing • Functional ATPG – generate complete set of tests for circuit input-output combinations – 129 inputs, 65 outputs: – 2129 patterns – Using 1 GHz ATE, would take 2.15 x 1022 years • Structural test: – No redundant adder hardware, 64 bit slices – Each with 27 faults (using fault equivalence) – At most 64 x 27 = 1728 faults (tests) – Takes 0.000001728 s on 1 GHz ATE • Designer gives small set of functional tests – augment with structural tests to boost coverage to 98+ %7 ECE 538 Krish Chakrabarty 13 Algorithm Completeness • Definition: Algorithm is complete if it ultimately can search entire binary decision tree, as needed, to generate a test • Untestable fault – no test for it even after entire tree searched • Combinational circuits only – untestable faults are redundant, showing the presence of unnecessary hardware ECE 538 Krish Chakrabarty 14 D-Algorithm b a c d e z b A B C E F GHB/1 Decision Implication Comment B = D E = D, A = 0, a = 0 Activate fault b = 1 C = D Propagate via C F = 0 z = D End of D-drive H = 0 e = 0 Justify F c = 0 (1) Justify A Test: abce = 01008 ECE 538 Krish Chakrabarty 15 D-Algorithm b a c d e z b A B C E F GHB/1 Decision Implication Comment B = D E = D, A = 0, a = 0 Activate fault H = 1 F = D Propagate via F C = 0 z = D End of D-drive b = 0 e = 0 Justify C c = 0 or e = 0 Justify A Test: abce = 0000 ECE 538 Krish Chakrabarty 16 D-Algorithm b a c d e z Decision Implication Action e = D, c = 0 i = D, f =1, h = 0 Activate fault, propagate via i j = k = 0 z = D End of D-drive d = 1, b = 1 g = 0, e = 0 Justify j = 0, k = 0 c = 0, d = 0 i = j = D propagate through i and j Single path sensitization does not always work! Fault e/0 f g h i j k Contradiction (Backtrack)9 ECE 538 Krish Chakrabarty 17 Comments on the D-Algorithm • Based on propagation (primary procedure), justification and implication • In complete form, guarantees test generation but may require multiple path sensitization (computationally expensive) • Practical restrictions: – Single path sensitization only – Limits placed on backtracking time (aborted faults) ECE 538 Krish Chakrabarty 18 9-V Algorithm • Nine logic values, specified as good/bad pairs: 1/1, 0/0, 1/0, 0/1, u/u, 1/u, 0/u, u/0, u/1 • Example of logic operations: D.X = 1/0.u/u = u/0, i.e. provides more information than the X outcome for 5-valued algebra • Reduces backtracking – When there are k possible paths for error propagation, D-algorithm may try