ECE 269 VLSI System Testing Krish Chakrabarty Test Generation 2 Krish Chakrabarty ECE 269 1 Outline Problem with D Algorithm PODEM FAN Fault independent ATPG Critical path tracing Random test generation Redundancy identification ECE 269 Krish Chakrabarty 2 1 Step 1 D Drive Set A 1 1 D D Krish Chakrabarty ECE 269 3 Step 2 D Drive Set f 0 0 1 D ECE 269 D D Krish Chakrabarty 4 2 Step 3 D Drive Set k 1 1 D 0 1 D ECE 269 D D Krish Chakrabarty 5 Step 4 Consistency Set g 1 1 0 1 D ECE 269 1 D D D Krish Chakrabarty 6 3 Step 5 Consistency f 0 Already set 1 D 0 1 D 1 D D Krish Chakrabarty ECE 269 7 Step 6 Consistency Set c 0 Set e 0 1 1 0 1 D ECE 269 0 0 D D D Krish Chakrabarty 8 4 Step 7 Consistency Set B 0 X 1 0 0 1 D ECE 269 0 1 D 0 D D Krish Chakrabarty 9 Example 7 3 Fault s sa1 1 sa1 ECE 269 Krish Chakrabarty D 10 5 Example 7 3 Step 2 s sa1 1 sa1 1 D 0 D D Krish Chakrabarty ECE 269 11 Example 7 3 Step 2 s sa1 Forward Backward Implications 0 1 1 1 1 1 sa1 0 D D D ECE 269 Krish Chakrabarty 12 6 Example 7 3 Step 3 s sa1 Test found 0 1 1 1 1 1 D sa1 0 D D 1 ECE 269 Krish Chakrabarty D 13 Example 7 3 Fault u sa1 1 0 sa1 ECE 269 Krish Chakrabarty D 14 7 Example 7 3 Step 2 u sa1 1 0 0 D sa1 D Krish Chakrabarty ECE 269 15 Example 7 3 Step 2 u sa1 Forward and backward implications 1 1 0 0 1 0 D ECE 269 Krish Chakrabarty 0 sa1 0 D 16 8 Inconsistent d 0 and m 1 cannot justify r 1 equivalence Backtrack Remove B 0 assignment ECE 269 Krish Chakrabarty 17 Example 7 3 Backtrack Need alternate propagation 1 0 sa1 ECE 269 Krish Chakrabarty D 18 9 Example 7 3 Step 3 u sa1 1 1 0 D sa1 D ECE 269 Krish Chakrabarty 19 Example 7 3 Step 4 u sa1 1 1 1 0 D 1 ECE 269 Krish Chakrabarty sa1 D D 20 10 Example 7 3 Step 4 u sa1 0 1 1 1 1 1 0 0 sa1 D D 1 ECE 269 0 D Krish Chakrabarty 21 Problem with D Algorithm Excessive backtracking occurs in certain types of circuits 2n 1 justifying values 1 Causes ripple effect in many circuits e g adders parity circuits error correcting circuits ECE 269 Krish Chakrabarty 22 11 PODEM Path Oriented Decision Making Similarity with D algorithm circuit based faultoriented Difference Signal values explicitly assigned only at primary outputs others computed by implication Justification not needed Backtracking means reassigning primary inputs when contradiction occurs implicit enumeration Simple backtrace heuristic used to select primary input ECE 269 Krish Chakrabarty 23 Branch and Bound Search Efficiently searches binary search tree Branching At each tree level selects which input variable to set to what value Bounding Avoids exploring large tree portions by artificially restricting search decision choices Complete exploration is impractical Uses heuristics ECE 269 Krish Chakrabarty 24 12 PODEM Example b a B c d B 1 A e b G E Implication a 0 b 1 c 1 e 1 e 0 z F H Decision a 1 Sequential input selection applying 1 before 0 C Comment Contradiction at fault Backtrack A 1 B 1 Contradiction backtrack A 0 B D E D H 0 F 0 C D z D Test found Krish Chakrabarty ECE 269 25 PODEM Decision Tree All primary inputs are at X Start 1 1 Untried alternatives 0 P31 P31 1 ECE 269 0 PI2 Remove node Contradiction back up PI1 PI4 0 PI4 Krish Chakrabarty 26 13 PODEM Steps Input Assignment Unassigned PIs are selected and assigned new values systematically All implications of each assignment are determined If D D is implied on a primary output a test has been found otherwise a new assignment or a new primary input line is selected ECE 269 Krish Chakrabarty 27 PODEM Steps Primary inputs selection INITIAL OBJECTIVE A series of initial objectives of the form IOj l v are determined The first IO0 is to apply v D D to the fault site BACKTRACING For each initial objective IOj a path is traced backwards through the circuit to a primary input via a series of current objectives Current objectives are selected by heuristics ECE 269 Krish Chakrabarty 28 14 PODEM Procedures Procedure Backtrace k vk Map objective into PI assignment Procedure Objective begin begin v vk the target is l v while k is a gate input if value of l is X then return l v begin select a gate G from the D frontier i inversion value of k select an input j of G with value X select an input j of k with value x c controlling value of G v v i return j c k j end end k is a PI return k v end ECE 269 Krish Chakrabarty 29 PODEM Procedures PODEM begin if error at PO then return SUCCESS if test not possible then return FAILURE k vk Objective j vj Backtrace k vk Imply j vj if PODEM SUCCESS then return SUCCESS reverse decision Imply j vj if PODEM SUCCESS then return SUCCESS Imply j X return FAILURE ECE 269 Krish Chakrabarty 30 15 FAN Fanout Oriented Test Generation Two major extensions to PODEM Backtracing may stop at internal lines Multiple backtrace procedures attempts to simultaneously satisfy a set of objectives Backtracing can stop at head lines B Bound line Head line A H ECE 269 C G z F Krish Chakrabarty 31 Selection Criteria Controllability CC0 and CC1 and observability measures CO Exact values can only be determined by exhaustive simulation Estimates are useful for guiding test generation more controllable low values more observable low values ECE 269 Krish Chakrabarty 32 16 Critical Path Test Generation Recursively determine critical paths 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 0 1 Krish Chakrabarty ECE 269 33 Critical Path Test Generation 0 1 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 ECE 269 Krish Chakrabarty 34 17 Redundancy Removal Using ATPG Redundancy identification Redundancy removal ECE 269 Krish Chakrabarty 35 Irredundant Faults Combinational ATPG can find redundant unnecessary hardware Fault Test a sa1 b sa0 A 1 a sa0 b sa1 A 0 Therefore these faults are not redundant ECE 269 Krish Chakrabarty 36 18 Redundant Hardware and Simplification ECE 269 Krish Chakrabarty 37 Redundant Fault Example ECE 269 Krish Chakrabarty 38 19 Multiple Fault Masking f sa0 tested when fault q sa1 not there ECE 269 Krish Chakrabarty 39 Multiple Fault Masking f sa0 masked when fault q sa1 also present ECE 269 Krish Chakrabarty 40 20 Intentional Redundant Implicant BC …