1ECE 269Krish Chakrabarty1ECE 269VLSI System TestingKrish ChakrabartyTest Generation: 2ECE 269Krish Chakrabarty2Outline• Problem with D-Algorithm•PODEM•FAN• Fault-independent ATPG– Critical path tracing• Random test generation• Redundancy identification2ECE 269Krish Chakrabarty3• Step 1 – D-Drive –SetA = 1D1DECE 269Krish Chakrabarty4D10D• Step 2 – D-Drive –Setf = 0D3ECE 269Krish Chakrabarty5D10D• Step 3 – D-Drive –Setk = 1D1DECE 269Krish Chakrabarty6D10D• Step 4 – Consistency –Setg = 1D1D14ECE 269Krish Chakrabarty7D10D• Step 5 – Consistency – f = 0 Already setD1D1ECE 269Krish Chakrabarty8D10D• Step 6 – Consistency –Setc = 0, Set e = 0D1D1005ECE 269Krish Chakrabarty9D10XD• Step 7 – Consistency –SetB = 0D1D1000ECE 269Krish Chakrabarty10Example 7.3 – Fault s sa11Dsa16ECE 269Krish Chakrabarty11Example 7.3 – Step 2 s sa11D0sa1D1DECE 269Krish Chakrabarty12Example 7.3 – Step 2 s sa1• Forward & Backward Implications1Dsa10DD110117ECE 269Krish Chakrabarty13Example 7.3 – Step 3 s sa1• Test found!1Dsa10DD110111DECE 269Krish Chakrabarty14Example 7.3 – Fault u sa11D0sa18ECE 269Krish Chakrabarty15Example 7.3 – Step 2 u sa11D0sa1D0ECE 269Krish Chakrabarty16Example 7.3 – Step 2 u sa1• Forward and backward implications1D0sa1D0010109ECE 269Krish Chakrabarty17Inconsistent• d = 0 and m = 1 cannot justify r = 1 (equivalence)– Backtrack– Remove B = 0 assignmentECE 269Krish Chakrabarty18Example 7.3 – Backtrack• Need alternate propagation1sa1D010ECE 269Krish Chakrabarty19Example 7.3 – Step 3 u sa11sa1D01DECE 269Krish Chakrabarty20Example 7.3 – Step 4 u sa1D1sa1D01D1111ECE 269Krish Chakrabarty21Example 7.3 – Step 4 u sa1D1sa1D01D1100011ECE 269Krish Chakrabarty22Problem with D-Algorithm12n-1justifying valuesExcessive backtracking occurs in certain types of circuitsCauses “ripple effect” in many circuits, e.g. adders, parity circuits, error correcting circuits12ECE 269Krish Chakrabarty23PODEM: “Path-Oriented Decision Making”• Similarity with D-algorithm: circuit-based, fault-oriented• 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 inputECE 269Krish Chakrabarty24Branch 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 heuristics13ECE 269Krish Chakrabarty25PODEM ExamplebacdezbABCEFGHB/1Decision Implication Commenta = 1 Contradiction at faultBacktracka = 0b = 1c = 1e = 1 A = 1, B = 1 Contradiction, backtracke = 0 A = 0, B = D, E = D,H = 0, F = 0, C = D, z = D Test found!Sequential inputselection, applying 1before 0ECE 269Krish Chakrabarty26PODEM Decision TreeStartAll primary inputs are at XPI1PI2P31P31PI4PI4Untriedalternatives1011Contradiction,back up00Remove node14ECE 269Krish Chakrabarty27PODEM 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 selectedECE 269Krish Chakrabarty28PODEM Steps• Primary inputs selection:– INITIAL OBJECTIVE: A series of “initial” objectives of the form IOj= (l,v) are determined. The first IO0is 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 heuristics15ECE 269Krish Chakrabarty29PODEM ProceduresProcedure Backtrace(k,vk)/* Map objective into PI assignment */beginv = vk;while k is a gate inputbegini = inversion value of k;select an input (j) of k with value x;v = v ⊕i;k = j;end/* k is a PI */return (k,v);endProcedure Objective()begin/* the target is l/v */if (value of l is X) then return (l,v);select a gate (G) from the D-frontier;select an input (j) of G with value X;c = controlling value of G;return (j,c);endECE 269Krish Chakrabarty30PODEM ProceduresPODEM()beginif (error at PO) then return SUCCESSif (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 FAILURE16ECE 269Krish Chakrabarty31FAN: “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 lineszABCFGHBound lineHead lineECE 269Krish Chakrabarty32Selection Criteria• Controllability (CC0 and CC1) and observabilitymeasures (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)17ECE 269Krish Chakrabarty33Critical Path Test Generation• Recursively determine critical paths01101000011111110ECE 269Krish Chakrabarty34Critical Path Test Generation1110100011101111018ECE 269Krish Chakrabarty35Redundancy Removal Using ATPG• Redundancy identification• Redundancy removalECE 269Krish Chakrabarty36Irredundant Faults• Combinational ATPG can find redundant (unnecessary) hardware• Fault Testa sa1, b sa0 A = 1a sa0, b sa1 A = 0• Therefore, these faults are not redundant19ECE 269Krish Chakrabarty37Redundant Hardware and SimplificationECE 269Krish Chakrabarty38Redundant Fault Example20ECE 269Krish Chakrabarty39Multiple Fault Masking• f sa0 tested when fault q sa1 not thereECE 269Krish Chakrabarty40Multiple Fault Masking• f sa0 masked when fault q sa1 also present21ECE 269Krish Chakrabarty41Intentional Redundant Implicant BC• Eliminates hazards in circuit outputECE 269Krish Chakrabarty42Fault Cone and D-Frontier• Fault Cone -- Set of hardware affected by fault• D-frontier – Set of gates closest to POs with fault effect(s) at input(s)Fault ConeD-frontier22ECE 269Krish