《第08讲——自动测试生成-超大规模集成电路测试技术ppt课件.ppt》由会员分享，可在线阅读，更多相关《第08讲——自动测试生成-超大规模集成电路测试技术ppt课件.ppt（71页珍藏版）》请在三一办公上搜索。
1、Lecture 8 Automatic Test Pattern Generation,第八讲 自动测试生成,Contents内容目录,Testability Measures/可测试性测度Combinational Circuit ATPG/组合电路ATPGSequential Circuit ATPG/时序电路ATPGSummary/小结,1 Testability Measures可测试性测度,Need approximate measure of:Controllability-Difficulty of setting internal circuit lines to 0 or 1
2、 by setting primary circuit inputsObservability-Difficulty of observing internal circuit lines by observing primary outputs,1.1 Purpose目的,Uses:Analysis of difficulty of testing internal circuit parts redesign or add special test hardwareGuidance for algorithms computing test patterns avoid using har
3、d-to-control linesEstimation of fault coverageEstimation of test vector length,1.2 Origins起源,Control theoryRutman 1972-First definition of controllabilityGoldstein 1979-SCOAPFirst definition of observabilityFirst elegant formulationFirst efficient algorithm to compute controllability and observabili
4、tyParker&McCluskey 1975Definition of Probabilistic ControllabilityBrglez 1984-COP1st probabilistic measuresSeth,Pan&Agrawal 1985 PREDICT1st exact probabilistic measures,1.3 Testability Analysis可测试性分析,Involves Circuit Topological analysis,but no test vectors and no search algorithm.Static analysisLin
5、ear computational complexity,Otherwise,is pointless might as well use automatic test-pattern generation and calculate:Exact fault coverageExact test vectors,1.4 SCOAP measuresSCOAP测度,SCOAP Sandia Controllability and Observability Analysis ProgramCombinational measures:CC0 Difficulty of setting circu
6、it line to logic 0CC1 Difficulty of setting circuit line to logic 1CO Difficulty of observing a circuit lineSequential measures analogous:SC0SC1SO,1.4.1 Range of SCOAP MeasuresSCOAP测度范围,Controllabilities 1(easiest)to infinity(hardest)Observabilities 0(easiest)to infinity(hardest)Combinational measur
7、es:Roughly proportional to#circuit lines that must be set to control or observe given lineSequential measures:Roughly proportional to#times a flip-flop must be clocked to control or observe given line,1.4.2 Controllability Rules可控制性规则,1.4.2 Controllability Rules(Cont.)可控制性规则（续）,1.4.3 Observability R
8、ules可观察性规则,To observe a gate input:Observe output and make other input values non-controlling,1.4.3 Observability Rules(Cont.)可观察性规则,To observe a fanout stem:Observe it through branch with best observability,1.4.4 D Flip-Flop RulesD触发器规则,Assume a synchronous RESET line.CC1(Q)=CC1(D)+CC1(C)+CC0(C)+CC
9、0(RESET)SC1(Q)=SC1(D)+SC1(C)+SC0(C)+SC0(RESET)+1CC0(Q)=min CC1(RESET)+CC1(C)+CC0(C),CC0(D)+CC1(C)+CC0(C)SC0(Q)is analogousCO(D)=CO(Q)+CC1(C)+CC0(C)+CC0(RESET)SO(D)is analogous,1.4.4 D Flip-Flop Rules(Cont.)D触发器规则（续）,CO(RESET)=CO(Q)+CC1(Q)+CC1(RESET)+CC1(C)+CC0(C)SO(RESET)is analogousThree ways to ob
10、serve the clock line:Set Q to 1 and clock in a 0 from DSet the flip-flop and then reset itReset the flip-flop and clock in a 1 from DCO(C)=min CO(Q)+CC1(Q)+CC0(D)+CC1(C)+CC0(C),CO(Q)+CC1(Q)+CC1(RESET)+CC1(C)+CC0(C),CO(Q)+CC0(Q)+CC0(RESET)+CC1(D)+CC1(C)+CC0(C)SO(C)is analogous,1.4.5 Levelization Algo
11、rithm 6.1分级算法,Label each gate with max#of logic levels from primary inputs or with max#of logic levels from primary outputAssign level#0 to all primary inputs(PIs)For each PI fanout:Label that line with the PI level number,Else,requeue the gate,1.4.6 Testability Algorithm 6.2可测试性算法,For all PIs,CC0=C
12、C1=1 and SC0=SC1=0For all other nodes,CC0=CC1=SC0=SC1=Go from PIs to POS,using CC and SC equations to get controllabilities-Iterate on loops until SC stabilizes-convergence guaranteedFor all POs,set CO=SO=0For all other nodes,CO=SO=Work from POs to PIs,Use CO,SO,and controllabilities to get observab
13、ilitiesFanout stem(CO,SO)=min branch(CO,SO)If a CC or SC(CO or SO)is,that node is uncontrollable(unobservable),8,8,8,2 Combinational Circuit ATPG 组合电路ATPG,Electron-beam(E-beam)test observes internal signals“picture”of nodes charged to 0 and 1 in different colorsToo expensiveThe ATPG problem:Given a
14、logical fault model,and a circuit,determine a small set of test vectors that detect all faults in the circuit.,2.1 Functional vs.Structural ATPG功能和结构测试,2.1.1 Compare比较,Functional ATPG generate complete set of tests for circuit input-output combinations129 inputs,65 outputs:2129=680,564,733,841,876,9
15、26,926,749,214,863,536,422,912 patternsUsing 1 GHz ATE,would take 2.15 x 1022 yearsStructural test:No redundant adder hardware,64 bit slicesEach with 27 faults(using fault equivalence)At most 64 x 27=1728 faults(tests)Takes 0.000001728 s on 1 GHz ATEDesigner gives small set of functional tests augme
16、nt with structural tests to boost coverage to 98+%,2.2 Algorithm Completeness算法完备性,Definition:Algorithm is complete if it ultimately can search entire binary decision tree,as needed,to generate a testUntestable fault no test for it even after entire tree searchedCombinational circuits only untestabl
17、e faults are redundant,showing the presence of unnecessary hardware,2.3 Algebras:5-Valued and 9-Valued算法代数：5值和9值逻辑代数,SymbolDD01XG0G1F0F1,Meaning1/00/10/01/1X/X0/X1/XX/0X/1,FailingMachine0101XXX01,GoodMachine 1001X01XX,RothsAlgebraMuthsAdditions,2.3.1 Higher-Order Algebras高阶代数,Represent two machines,
18、which are simulated simultaneously by a computer program:Good circuit machine(1st value)Bad circuit machine(2nd value)Better to represent both in the algebra:Need only 1 pass of ATPG to solve bothGood machine values that preclude bad machine values become obvious sooner&vice versaNeeded for complete
19、 ATPG:Combinational:Multi-path sensitization,Roth AlgebraSequential:Muth Algebra-good and bad machines may have different initial values due to fault,2.4 Types of Algorithms 算法类型,Exhaustive/穷举算法Random-Pattern Generation/随机码生成Boolean Difference Symbolic Method/布尔差分符号方法Path Sensitization Method/路径敏化方法
20、Boolean Satisfiability/布尔可满足性,2.4.1 Exhaustive 穷举算法,For n-input circuit,generate all 2n input patternsInfeasible,unless circuit is partitioned into cones of logic,with 15 inputsPerform exhaustive ATPG for each coneMisses faults that require specific activation patterns for multiple cones to be teste
21、d,2.4.2 Random-Pattern Generation随机码生成,Flow chart for methodUse to get tests for 60-80%of faults,then switch to D-algorithm or other ATPG for rest,2.4.3 Boolean Difference Symbolic Method布尔差分符号方法,g=G(X1,X2,Xn)for the fault sitefj=Fj(g,X1,X2,Xn)1 j mXi=0 or 1 for 1 i n,Shannons Expansion Theorem:F(X1
22、,X2,Xn)=X2 F(X1,1,Xn)+X2 F(X1,0,Xn)Boolean Difference(partial derivative):Fj gFault Detection Requirements:G(X1,X2,Xn)=1 Fj g,2.4.3.1 Boolean Difference(Sellers,Hsiao,Bearnson),=Fj(1,X1,X2,Xn)Fj(0,X1,Xn),=Fj(1,X1,X2,Xn)Fj(0,X1,Xn)=1,2.4.4 Path Sensitization Method路径敏化方法,Fault Sensitization/故障敏化Fault
23、 Propagation/故障传播Line Justification/线验证,2.4.4.1 Circuit Example电路实例,Try path f h k L blocked at j,since there is no way to justify the 1 on i,2.4.4.1 Circuit Example(Cont.)电路实例（续）,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,2.4.4.1 Circuit
24、Example(Cont.)电路实例（续）,Final try:path g i j k L test found!,2.4.5 Boolean Satisfiability布尔可满足性,2SAT:xi xj+xj xk+xl xm=0 xp xy+xr xs+xt xu=03SAT:xi xj xk+xj xk xl+xl xm xn=0 xp xy+xr xs xt+xt xu xv=0,.,.,2.4.5.1 Satisfiability Example for AND Gate,S ak bk ck=0(non-tautology)or P(ak+bk+ck)=1(satisfiabi
25、lity)AND gate signal relationships:Cube:If a=0,then z=0 a zIf b=0,then z=0 b zIf z=1,then a=1 AND b=1 z abIf a=1 AND b=1,then z=1 a b zSum to get:a z+b z+a b z=0(third relationship is redundant with 1st two),2.4.5.2 Pseudo-Boolean and Boolean False Functions,Pseudo-Boolean function:use ordinary+-int
26、eger arithmetic operatorsComplementation of x represented by 1 xFpseudoBool=2 z+a b a z b z a b z=0Energy function representation:let any variable be in the range(0,1)in pseudo-Boolean functionBoolean false expression:fAND(a,b,z)=z(ab)=a z+b z+a b z,2.4.5.3 AND Gate Implication Graph隐含图,Really effic
27、ientEach variable has 2 nodes,one for each literalIf then clause represented by edge from if literal to then literalTransform into transitive closure graph When node true,all reachable states are trueANDing operator used for 3SAT relations,2.5 Computational Complexity计算复杂性,Ibarra and Sahni analysis
28、NP-Complete(no polynomial expression found for compute time,presumed to be exponential)Worst case:no_pi inputs,2 no_pi input combinations no_ff flip-flops,4 no_ff initial flip-flop states(good machine 0 or 1 bad machine 0 or 1)work to forward or reverse simulate n logic gates a nComplexity:O(n x 2 n
29、o_pi x 4 no_ff),2.6 History of Algorithm Speedups算法历史,AlgorithmD-ALGPODEMFANTOPSSOCRATESWaicukauski et al.ESTTRANRecursive learningTafertshofer et al.,Est.speedup over D-ALG(normalized to D-ALG time)17232921574 ATPG System2189 ATPG System8765 ATPG System3005 ATPG System48525057,Year19661981198319871
30、98819901991199319951997,2.7 Fault Coverage and Efficiency故障覆盖率和效率,Fault coverage=Fault efficiency,2.8 Test Generation Systems测试生成系统,2.9 Test Compaction测试压缩,Fault simulate test patterns in reverse order of generationATPG patterns go firstRandomly-generated patterns go last(because they may have less
31、coverage)When coverage reaches 100%,drop remaining patterns(which are the useless random ones)Significantly shortens test sequence economic cost reduction,2.9.1 Static and Dynamic Compaction静态和动态压缩,Static compactionATPG should leave unassigned inputs as XTwo patterns compatible if no conflicting val
32、ues for any PICombine two tests ta and tb into one test tab=ta tb using D-intersection Detects union of faults detected by ta&tbDynamic compactionProcess every partially-done ATPG vector immediatelyAssign 0 or 1 to PIs to test additional faults,2.9.2 Compaction Example压缩实例,t1=0 1 X t2=0 X 1 t3=0 X 0
33、 t4=X 0 1Combine t1 and t3,then t2 and t4 Obtain:t13=0 1 0 t24=0 0 1Test Length shortened from 4 to 2,3 Sequential Circuits ATPG时序电路ATPG,A sequential circuit has memory in addition to combinational logic.Test for a fault in a sequential circuit is a sequence of vectors,whichInitializes the circuit t
34、o a known stateActivates the fault,andPropagates the fault effect to a primary outputMethods of sequential circuit ATPGTime-frame expansion methodsSimulation-based methods,3.1 Time-Frames Expansion,If the test sequence for a single stuck-at fault contains n vectors,Replicate combinational logic bloc
35、k n timesPlace fault in each blockGenerate a test for the multiple stuck-at fault using combinational ATPG with 9-valued logic,3.1.1 Example for Logic Systems实例,3.1.1.1 Five-Valued Logic(Roth)0,1,D,D,X,3.1.1.2 Nine-Valued Logic(Muth)0,1,1/0,0/1,1/X,0/X,X/0,X/1,X,3.1.2 Implementation of ATPGATPG实现,Se
36、lect a PO for fault detection based on drivability analysis.Place a logic value,1/0 or 0/1,depending on fault type and number of inversions.Justify the output value from PIs,considering all necessary paths and adding backward time-frames.If justification is impossible,then use drivability to select
37、another PO and repeat justification.If the procedure fails for all reachable POs,then the fault is untestable.If 1/0 or 0/1 cannot be justified at any PO,but 1/X or 0/X can be justified,the the fault is potentially detectable.,3.1.3 Complexity of ATPG计算复杂性,Synchronous circuit-All flip-flops controll
38、ed by clocks;PI and PO synchronized with clock:Cycle-free circuit No feedback among flip-flops:Test generation for a fault needs no more than dseq+1 time-frames,where dseq is the sequential depth.Cyclic circuit Contains feedback among flip-flops:May need 9Nff time-frames,where Nff is the number of f
39、lip-flops.Asynchronous circuit Higher complexity!,3.1.3.1 Cycle-Free Circuits无环电路,Characterized by absence of cycles among flip-flops and a sequential depth,dseq.dseq is the maximum number of flip-flops on any path between PI and PO.Both good and faulty circuits are initializable.Test sequence lengt
40、h for a fault is bounded by dseq+1.,3.1.3.2 Cycle-Free Example无环电路实例,3.1.3.3 Cyclic circuit循环电路,Cyclic structure Sequential depth is undefined.Circuit is not initializable.No tests can be generated for any stuck-at fault.After expanding the circuit to 9Nff=81,or fewer,time-frames ATPG program calls
41、any given target fault untestable.Circuit can only be functionally tested by multiple observations.Functional tests,when simulated,give no fault coverage.,3.1.3.4 Cyclic Circuit Example循环电路实例,3.1.3.5 Benchmark Circuits,CircuitPIPOFFGatesStructureSeq.depthTotal faultsDetected faultsPotentially detect
42、ed faultsUntestable faultsAbandoned faultsFault coverage(%)Fault efficiency(%)Max.sequence lengthTotal test vectorsGentest CPU s(Sparc 2),s1196 14 14 18 529Cycle-free 412421239 0 3 0 99.8 100.0 3 313 10,s1238 14 14 18 508Cycle-free 413551283 0 72 0 94.7 100.0 3 308 15,s1488 8 19 6 653Cyclic-14861384
43、 2 26 76 93.1 94.8 24 52519941,s1494 8 19 6 647Cyclic-15061379 2 30 97 91.6 93.4 28 55919183,3.1.3.6 Asynchronous Circuit异步电路,An asynchronous circuit contains unclocked memory often realized by combinational feedback.Almost impossible to build,let alone test,a large asynchronous circuit.Clock genera
44、tors,signal synchronizers,flip-flops are typical asynchronous circuits.Many large synchronous systems contain small portions of localized asynchronous circuitry.Sequential circuit ATPG should be able to generate tests for circuits with limited asynchronous parts,even if it does not detect faults in
45、those parts.,3.1.3.7 Asynchronous Model异步电路模型,3.1.3.8 Time-Frame Expansion异步电路时帧扩展,3.2 simulation-based methods基于模拟的方法,Difficulties with time-frame method:Long initialization sequenceImpossible initialization with three-valued logicCircuit modeling limitationsTiming problems tests can cause races/ha
46、zardsHigh complexityInadequacy for asynchronous circuitsAdvantages of simulation-based methodsAdvanced fault simulation technologyAccurate simulation model exists for verificationVariety of tests functional,heuristic,randomUsed since early 1960s,3.2.1 Using Fault Simulator使用故障模拟器,3.2.2 Contest,A Con
47、current test generator for sequential circuit testing(Contest).Search for tests is guided by cost-functions.Three-phase test generation:Initialization no faults targeted;cost-function computed by true-value simulator.Concurrent phase all faults targeted;cost function computed by a concurrent fault s
48、imulator.Single fault phase faults targeted one at a time;cost function computed by true-value simulation and dynamic testability analysis.Ref.:Agrawal,et al.,IEEE-TCAD,1989.,3.2.2.1 Contest Result:s5378,35 PIs,49 POs,179 FFs,4,603 faults.Synchronous,single clock.,3.2.3 Genetic Algorithms(GAs)遗传算法,T
49、heory of evolution by natural selection(Darwin,1809-82.)C.R.Darwin,On the Origin of Species by Means of Natural Selection,London:John Murray,1859.J.H.Holland,Adaptation in Natural and Artificial Systems,Ann Arbor:University of Michigan Press,1975.D.E.Goldberg,Genetic Algorithms in Search,Optimizatio
50、n,and Machine Learning,Reading,Massachusetts:Addison-Wesley,1989.P.Mazumder and E.M.Rudnick,Genetic Algorithms for VLSI Design,Layout and Test Automation,Upper Saddle River,New Jersey,Prentice Hall PTR,1999.Basic Idea:Population improves with each generation.PopulationFitness criteriaRegeneration ru
