ECE 269 VLSI System Testing Krish Chakrabarty Lecture 9 Test Generation Part 1 ECE 269 Krish Chakrabarty 1 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 ECE 269 Krish Chakrabarty 2 1 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 Krish Chakrabarty ECE 269 3 Fault Table Analysis Fault 2 input OR gate a b z a 0 a 1 b 0 b 1 z 0 z 1 ab 00 Test 01 10 11 x x x x x x x x Determine fault table via simulation and solve covering problem Covering problems are NP complete Computationally infeasible ECE 269 Krish Chakrabarty 4 2 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 269 Krish Chakrabarty 5 Boolean Difference The Boolean difference of F x1 x2 x3 xn with respect to xi is given by F F x1 x2 1 x3 xn F x1 x2 0 x3 xn xi Cofactor w r t xi Cofactor w r t xi Boolean difference provides input combination for sensitized path A test pattern for xi 0 is an input combination that makes xi F 1 xi F A test pattern for xi 1 is an input combination that makes xi 1 xi ECE 269 Krish Chakrabarty 6 3 Boolean Difference f a b c j g h i z d k e To find a test for a 0 or a 1 determine the Boolean difference of output z with respect to a z a How to handle internal faults e g j 0 ECE 269 Krish Chakrabarty 7 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 ECE 269 Krish Chakrabarty 8 4 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 Krish Chakrabarty ECE 269 9 Testing Fanout Free Circuits 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 end ECE 269 Krish Chakrabarty 1 l err 1 err 10 5 Testing Fanout Free Circuits 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 Line Justification 1 1 1 0 l X 0 X 1 l Krish Chakrabarty ECE 269 11 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 ECE 269 Krish Chakrabarty 12 6 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 Krish Chakrabarty ECE 269 13 D Algorithm b a C B c d A e b B 1 H G E z F Decision Implication Comment B D b 1 F 0 H 0 c 0 1 E D A 0 a 0 C D z D e 0 Activate fault Propagate via C End of D drive Justify F Justify A ECE 269 Test abce 0100 Krish Chakrabarty 14 7 D Algorithm b a C B c d B 1 A e b G E z F H Decision Implication Comment B D H 1 C 0 b 0 c 0 or e 0 E D A 0 a 0 F D z D e 0 Activate fault Propagate via F End of D drive Justify C Justify A Test abce 0000 Krish Chakrabarty ECE 269 15 D Algorithm Fault e 0 h f c a b i e z j Single path sensitization does not always work d g k Decision Implication Action E D c 0 j k 0 d 1 b 1 c 0 d 0 i D f 1 h 0 z D Contradiction g 0 e 0 i j D Activate fault propagate via i End of D drive Justify j 0 k 0 Backtrack propagate through i and j ECE 269 Krish Chakrabarty 16 8 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 269 Krish Chakrabarty 17 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 all 2k 1 combinations of paths 9 V enumerates only k ways of propagation ECE 269 Krish Chakrabarty 18 9 Path Sensitization 1 Fault Sensitization 2 Fault Propagation 3 Line Justification Krish Chakrabarty ECE 269 19 Path Sensitization Try path f h k L blocked at j since there is no way to justify the 1 on i 1 1 D D D D 1 0 D 1 ECE 269 Krish Chakrabarty 20 10 Path Sensitization Try simultaneous paths f h k L and g i j k L blocked at k because D frontier chain of D or D disappears 1 D D 1 1 D D D 1 Krish Chakrabarty ECE 269 21 Path Sensitization …