中科院研究生院课程VLSI测试与可测试性设计.ppt

1,中科院研究生院课程：VLSI测试与可测试性设计,第5讲 测试生成(1) 李晓维 中科院计算技术研究所 Email: ,2,Chapter 4,Test Generation,3,What is this chapter about?,Introduce the basic concepts of ATPG Focus on a number of combinational and sequential ATPG techniques Deterministic ATPG and simulation-based ATPG Fast untestable fault identification ATPG for various fault models,4,Test Generation,Introduction Random Test Generation Theoretical Foundations Deterministic Combinational ATPG Deterministic Sequential ATPG Untestable Fault Identification Simulation-based ATPG ATPG for Delay and Bridge Faults Other Topics in Test Generation Concluding Remarks,5,Introduction,Test generation is the bread-and-butter in VLSI Testing Efficient and powerful ATPG can alleviate high costs of DFT Goal: generation of a small set of effective vectors at a low computational cost ATPG is a very challenging task Exponential complexity Circuit sizes continue to increase (Moores Law) Aggravate the complexity problem further Higher clock frequencies Need to test for both structural and delay defects,6,Conceptual View of ATPG,Generate an input vector that can distinguish the defect-free circuit from the hypothetically defective one,7,Fault Models,Instead of targeting specific defects, fault models are used to capture the logical effect of the underlying defect Fault models considered in this chapter: Stuck-at fault Bridging fault Transition fault Path-delay fault,8,Simple illustration of ATPG,Consider the fault d/1 in the defective circuit Need to distinguish the output of the defective circuit from the defect-free circuit Need: set d=0 in the defect-free circuit Need: propagate effect of fault to output Vector: abc=001 (output = 0/1),9,Example 1,10,A Typical ATPG System,Given a circuit and a fault model Repeat Generate a test for each undetected fault Drop all other faults detected by the test using a fault simulator Until all faults have been considered Note 1: a fault may be untestable, in which no test would be generated Note 2: an ATPG may abort on a fault if the resources needed exceed a preset limit,11,Category of ATPG,Simulation-based Exhaustive Random-pattern generation Pseudo-random-pattern generation Path sensitization D-algorithm, 9-V algorithm PODEM, FAN TOPS, SOCRATES Boolean satisfiability & Neural network Boolean difference Boolean satisfiability (2-SAT, 3-SAT) Neural network,12,Random Test Generation,Simplest form of test generation N tests are randomly generated Level of confidence on random test set T The probability that T can detect all stuck-at faults in the given circuit Quality of a random test set highly depends on the underlying circuit Some circuits have many random-resistant faults,13,Weighted Random Test Generation,Bias input probabilities to target random resistant faults Consider an 8-input AND gate Without biasing input probabilities, the prob of generating a logic 1 at the gate output = (0.5)8 = 0.004 If we bias the inputs to 0.75, then the prob of generating a logic 1 at the gate output = (0.75)8 = 0.100 Obtaining an optimal set of input probabilities a difficult task Goal: increase the signal probabilities of hard-to-test regions,14,Exhaustive Test Generation,Exhaustive Testing Apply 2n patterns to an n-input combinational circuit under test (CUT) Guarantees all detectable faults in the combinational circuits are detected Test time maybe be prohibitively long if the number of inputs is large Feasible only for small circuits Pseudo-exhaustive Testing Partition circuit into respective cones Apply exhaustive testing only to each cone Still guarantees to detect every detectable fault based on Lemma 1,15,Path Sensitization Method Circuit Example,Fault Sensitization Fault Propagation Line Justification,16,Path Sensitization Method Circuit Example,Try path f h k L blocked at j, since there is no way to justify the 1 on i,1,0,D,D,1,1,1,D,D,D,17,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,D,D,D,1,1,Path Sensitization Method Circuit Example,18,Final try: path g i j k L test found!,0,D,D,D,1,D,D,1,0,1,Path Sensitization Method Circuit Example,19,History of Algorithm Speedups,20,Roths 5-Valued and Muths 9-Valued,1,1,0,0,21,Forward Implication,Results in logic gate inputs that are significantly labeled so that output is uniquely determined AND gate forward implication table:,22,Backward Implication,Unique determination of all gate inputs when the gate output and some of the inputs are given,23,Example 2 Fault A sa0,Step 1 D-Drive Set A = 1,24,Step 2 - Example 2,Step 2 D-Drive Set f = 0,25,Step 3 - Example 2,Step 3 D-Drive Set k = 1,26,Step 4 - Example 2,Step 4 Consistency Set g = 1,27,Step 5 - Example 2,Step 5 Consistency Set f = 0,28,Step 6 - Example 2,Step 6 Consistency Set c = 0, Set e = 0,29,Test found - Example 2,Step 7 Consistency Set B = 0,Test cube: A, B, C, D, e, f, g, h, k, L,30,Example 3 Fault s sa1,Primitive D-cube of Failure,1,D,sa1,31,Example 3 Step 3 s sa1,Propagation D-cube for v,1,D,0,sa1,D,1,D,32,Example 3 Step 4 s sa1,Propagation D-cube for Z,1,D,sa1,0,D,D,1,1,1,D,33,Example 3 Step 5 s sa1,Singular cover of m,1,D,sa1,0,D,D,1,1,1,D,1,34,Test Found Step 6 s sa1,Singular cover of d,1,D,sa1,0,D,D,1,1,1,D,1,1,35,Example 3 Fault u sa1,Primitive D-cube of Failure,1,D,0,sa1,36,Example 3 Step 2 u sa1,Propagation D-cube for v and implications,1,D,0,sa1,D,0,0,1,0,1,0,37,Example 3 Step 3 u sa1,Propagation D-cube for Z,1,sa1,D,0,D,0,1,D,0,1,0,1,0,38,Example 3 Step 4 u sa1,Singular cover for r f = 0 and n = 1 cannot justify r = 1,1,sa1,D,0,D,0,1,D,0,1,0,1,0,39,Example 3 Backtrack,Remove C = 1 and B = 0 assignments,1,sa1,D,0,40,Example 3 Backtrack,Need alternate propagation D-cube for v,1,sa1,D,0,41,Example 3 Step 5 u sa1,Propagation D-cube for v,1,sa1,D,0,1,D,42,Example 3 Step 6 u sa1,Propagation D-cube for Z and implications,D,1,sa1,D,0,1,D,1,1,0,0,43,Example 3 Step 7 u sa1,Singular cover for r,sa1,D,1,D,0,1,D,1,1,1,0,0,0,44,Test Found Step 8 u sa1,Singular cover for d set A = 1,sa1,D,1,D,0,1,D,1,1,1,0,0,1,0,45,D-Algorithm Top Level,Number all circuit lines in increasing level order from PIs to POs; 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; D-drive (); Consistency (); return ();,46,D-frontier,Fault Cone - Set of hardware affected by fault D-frontier Set of gates closest to POs with fault effect(s) at in