第08讲-自动测试生成超大规模集成电路测试技术课件

Lecture8AutomaticTestPatternGeneration第八讲自动测试生成Lecture8AutomaticTestPatte1Contents

内容目录TestabilityMeasures/可测试性测度CombinationalCircuitATPG/组合电路ATPGSequentialCircuitATPG/

时序电路ATPGSummary/小结Contents

内容目录TestabilityMeasu21TestabilityMeasures

可测试性测度Needapproximatemeasureof:Controllability--Difficultyofsettinginternalcircuitlinesto0or1bysettingprimarycircuitinputsObservability--Difficultyofobservinginternalcircuitlinesbyobservingprimaryoutputs1TestabilityMeasures

可测试性测度N31.1Purpose

目的Uses:Analysisofdifficultyoftestinginternalcircuitparts–redesignoraddspecialtesthardwareGuidanceforalgorithmscomputingtestpatterns–avoidusinghard-to-controllinesEstimationoffaultcoverageEstimationoftestvectorlength1.1Purpose

目的Uses:41.2Origins

起源ControltheoryRutman1972--FirstdefinitionofcontrollabilityGoldstein1979--SCOAPFirstdefinitionofobservabilityFirstelegantformulationFirstefficientalgorithmtocomputecontrollabilityandobservabilityParker&McCluskey1975DefinitionofProbabilisticControllabilityBrglez1984--COP1stprobabilisticmeasuresSeth,Pan&Agrawal1985–PREDICT1stexactprobabilisticmeasures1.2Origins

起源Controltheory51.3TestabilityAnalysis

可测试性分析InvolvesCircuitTopologicalanalysis,butnotestvectorsandnosearchalgorithm.StaticanalysisLinearcomputationalcomplexity,Otherwise,ispointless–mightaswelluseautomatictest-patterngenerationandcalculate:ExactfaultcoverageExacttestvectors1.3TestabilityAnalysis

可测试性分61.4SCOAPmeasures

SCOAP测度SCOAP–SandiaControllabilityandObservabilityAnalysisProgramCombinationalmeasures:CC0–Difficultyofsettingcircuitlinetologic0CC1–Difficultyofsettingcircuitlinetologic1CO–DifficultyofobservingacircuitlineSequentialmeasures–analogous:SC0SC1SO1.4SCOAPmeasures

SCOAP测度SCOA71.4.1RangeofSCOAPMeasures

SCOAP测度范围Controllabilities–1(easiest)toinfinity(hardest)Observabilities–0(easiest)toinfinity(hardest)Combinationalmeasures:Roughlyproportionalto#circuitlinesthatmustbesettocontrolorobservegivenlineSequentialmeasures:Roughlyproportionalto#timesaflip-flopmustbeclockedtocontrolorobservegivenline1.4.1RangeofSCOAPMeasures81.4.2ControllabilityRules

可控制性规则1.4.2ControllabilityRules

可控91.4.2ControllabilityRules(Cont.)

可控制性规则（续）1.4.2ControllabilityRules(C101.4.3ObservabilityRules

可观察性规则Toobserveagateinput:Observeoutputandmakeotherinputvaluesnon-controlling1.4.3ObservabilityRules

可观察性111.4.3ObservabilityRules(Cont.)

可观察性规则Toobserveafanoutstem:Observeitthroughbranchwithbestobservability1.4.3ObservabilityRules(Con121.4.4DFlip-FlopRules

D触发器规则AssumeasynchronousRESETline.CC1(Q)=CC1(D)+CC1(C)+CC0(C)+CC0

(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)isanalogousCO(D)=CO(Q)+CC1(C)+CC0(C)+CC0(RESET)SO(D)isanalogous1.4.4DFlip-FlopRules

D触发器规则131.4.4DFlip-FlopRules(Cont.)

D触发器规则（续）CO(RESET)=CO(Q)+CC1(Q)+CC1(RESET)+CC1(C)+CC0(C)SO(RESET)isanalogousThreewaystoobservetheclockline:SetQto1andclockina0fromDSettheflip-flopandthenresetitResettheflip-flopandclockina1fromDCO(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)isanalogous1.4.4DFlip-FlopRules(Cont.141.4.5LevelizationAlgorithm6.1

分级算法Labeleachgatewithmax#oflogiclevelsfromprimaryinputsorwithmax#oflogiclevelsfromprimaryoutputAssignlevel#0toallprimaryinputs(PIs)ForeachPIfanout:LabelthatlinewiththePIlevelnumber,&QueuelogicgatedrivenbythatfanoutWhilequeueisnotempty:DequeuenextlogicgateIfallgateinputshavelevel#’s,labelthegatewiththemaximumofthem+1;Else,requeuethegate1.4.5LevelizationAlgorithm6151.4.6TestabilityAlgorithm6.2

可测试性算法ForallPIs,CC0=CC1=1andSC0=SC1=0Forallothernodes,CC0=CC1=SC0=SC1=GofromPIstoPOS,usingCCandSCequationstogetcontrollabilities--IterateonloopsuntilSCstabilizes--convergenceguaranteedForallPOs,setCO=SO=

0Forallothernodes,

CO=SO=WorkfromPOstoPIs,UseCO,SO,andcontrollabilitiestogetobservabilitiesFanoutstem(CO,SO)=minbranch(CO,SO)IfaCCorSC(COorSO)is,thatnodeisuncontrollable(unobservable)8881.4.6TestabilityAlgorithm6.162CombinationalCircuitATPG

组合电路ATPGElectron-beam(E-beam)testobservesinternalsignals–“picture”ofnodeschargedto0and1indifferentcolorsTooexpensiveTheATPGproblem:Givenalogicalfaultmodel,andacircuit,determineasmallsetoftestvectorsthatdetectallfaultsinthecircuit.2CombinationalCircuitATPG

172.1Functionalvs.StructuralATPG

功能和结构测试2.1Functionalvs.Structural182.1.1Compare

比较FunctionalATPG–generatecompletesetoftestsforcircuitinput-outputcombinations129inputs,65outputs:2129=680,564,733,841,876,926,926,749,214,863,536,422,912patternsUsing1GHzATE,wouldtake2.15x1022yearsStructuraltest:Noredundantadderhardware,64bitslicesEachwith27faults(usingfaultequivalence)Atmost64x27=1728faults(tests)Takes0.000001728son1GHzATEDesignergivessmallsetoffunctionaltests–augmentwithstructuralteststoboostcoverageto98+%2.1.1Compare

比较FunctionalATP192.2AlgorithmCompleteness

算法完备性Definition:Algorithmiscompleteifitultimatelycansearchentirebinarydecisiontree,asneeded,togenerateatestUntestablefault–notestforitevenafterentiretreesearchedCombinationalcircuitsonly–untestablefaultsareredundant,showingthepresenceofunnecessaryhardware2.2AlgorithmCompleteness

算法完202.3Algebras:5-Valuedand9-Valued

算法代数：5值和9值逻辑代数SymbolDD01XG0G1F0F1Meaning1/00/10/01/1X/X0/X1/XX/0X/1FailingMachine0101XXX01GoodMachine1001X01XXRoth’sAlgebraMuth’sAdditions2.3Algebras:5-Valuedand9-V212.3.1Higher-OrderAlgebras

高阶代数Representtwomachines,whicharesimulatedsimultaneouslybyacomputerprogram:Goodcircuitmachine(1stvalue)Badcircuitmachine(2ndvalue)Bettertorepresentbothinthealgebra:Needonly1passofATPGtosolvebothGoodmachinevaluesthatprecludebadmachinevaluesbecomeobvioussooner&viceversaNeededforcompleteATPG:Combinational:Multi-pathsensitization,RothAlgebraSequential:MuthAlgebra--goodandbadmachinesmayhavedifferentinitialvaluesduetofault2.3.1Higher-OrderAlgebras

高阶222.4TypesofAlgorithms

算法类型Exhaustive/穷举算法Random-PatternGeneration/随机码生成BooleanDifferenceSymbolicMethod/布尔差分符号方法PathSensitizationMethod/路径敏化方法BooleanSatisfiability/布尔可满足性2.4TypesofAlgorithms

算法类型E232.4.1Exhaustive

穷举算法Forn-inputcircuit,generateall2ninputpatternsInfeasible,unlesscircuitispartitionedintoconesoflogic,with15inputsPerformexhaustiveATPGforeachconeMissesfaultsthatrequirespecificactivationpatternsformultipleconestobetested

2.4.1Exhaustive

穷举算法Forn-in242.4.2Random-PatternGeneration

随机码生成FlowchartformethodUsetogettestsfor60-80%offaults,thenswitchtoD-algorithmorotherATPGforrest2.4.2Random-PatternGeneratio252.4.3BooleanDifferenceSymbolicMethod

布尔差分符号方法g=G(X1,X2,…,Xn)forthefaultsitefj=Fj(g,X1,X2,…,Xn)1j

mXi=0or1for1i

n

2.4.3BooleanDifferenceSymbo26Shannon’sExpansionTheorem:

F(X1,X2,…,Xn)=X2

F(X1,1,…,Xn)+X2

F(X1,0,…,Xn)BooleanDifference(partialderivative):

FjgFaultDetectionRequirements:

G(X1,X2,…,Xn)=1FjgBooleanDifference(Sellers,Hsiao,Bearnson)=Fj(1,X1,X2,…,Xn)Fj(0,X1,…,Xn)=Fj(1,X1,X2,…,Xn)Fj(0,X1,…,Xn)=1

Shannon’sExpansionTheorem:272.4.4PathSensitizationMethod

路径敏化方法FaultSensitization/故障敏化FaultPropagation/故障传播LineJustification/线验证2.4.4PathSensitizationMetho2CircuitExample

电路实例Trypathf–h–k–L

blockedat

j,sincethereisnowaytojustifythe1on

i10DD111DDDCircuitExample

电路实例Tr2CircuitExample(Cont.)

电路实例（续）Trysimultaneouspathsf–h–k–Land

g–i–j–k–LblockedatkbecauseD-frontier(chainofDorD)disappears1DDDDD1CircuitExample(Cont.30CircuitExample(Cont.)

电路实例（续）Finaltry:path

g–i–j–k–L–testfound!0DDD1DD10CircuitExample(Cont.312.4.5BooleanSatisfiability

布尔可满足性2SAT:xixj+xjxk+xlxm…=0

xpxy+xrxs+xtxu…=03SAT:xixjxk+xjxkxl+xlxmxn…=0

xpxy+xrxsxt+xtxuxv…=0......2.4.5BooleanSatisfiability

3SatisfiabilityExampleforANDGateS

akbkck=0(non-tautology)or

P(ak+bk+ck)=1(satisfiability)ANDgatesignalrelationships:Cube:Ifa=0,thenz=0azIfb=0,thenz=0bzIfz=1,thena=1ANDb=1zabIfa=1ANDb=1,thenz=1abzSumtoget:az+bz+abz=0(thirdrelationshipisredundantwith1sttwo)SatisfiabilityExample3Pseudo-BooleanandBooleanFalseFunctionsPseudo-Booleanfunction:useordinary+-integerarithmeticoperatorsComplementationofxrepresentedby1–xFpseudo—Bool

=2z+ab–az–bz–abz=0Energyfunctionrepresentation:letanyvariablebeintherange(0,1)inpseudo-BooleanfunctionBooleanfalseexpression:

fAND

(a,b,z)=z(ab)=az+bz+abz

Pseudo-BooleanandBoo3ANDGateImplicationGraph

隐含图ReallyefficientEachvariablehas2nodes,oneforeachliteralIf…thenclauserepresentedbyedgefromifliteraltothenliteralTransformintotransitiveclosuregraph

Whennodetrue,allreachablestatesaretrueANDingoperatorusedfor3SATrelations

ANDGateImplicationG352.5ComputationalComplexity

计算复杂性IbarraandSahnianalysis–NP-Complete(nopolynomialexpressionfoundforcomputetime,presumedtobeexponential)Worstcase:

no_piinputs,2no_piinputcombinations

no_ffflip-flops,4no_ffinitialflip-flopstates(goodmachine0or1badmachine0or1)worktoforwardorreversesimulatenlogicgatesa

nComplexity:O(nx2no_pix4no_ff)

2.5ComputationalComplexity

计362.6HistoryofAlgorithmSpeedups

算法历史AlgorithmD-ALGPODEMFANTOPSSOCRATESWaicukauskietal.ESTTRANRecursivelearningTafertshoferetal.Est.speedupoverD-ALG(normalizedtoD-ALGtimeTPGSystem2189ATPGSystem8765ATPGSystem3005ATPGSystem48525057Year1966198119831987198819901991199319951997

2.6HistoryofAlgorithmSpeed372.7FaultCoverageandEfficiency

故障覆盖率和效率Faultcoverage=Faultefficiency

#ofdetectedfaultsTotal#faults#ofdetectedfaultsTotal#faults--#undetectablefaults=2.7FaultCoverageandEfficie382.8TestGenerationSystems

测试生成系统CircuitDescriptionTestPatternsUndetectedFaultsRedundantFaultsAbortedFaultsBacktrackDistributionFaultListCompacterSOCRATESWithfaultsimulator2.8TestGenerationSystems

测试392.9TestCompaction

测试压缩FaultsimulatetestpatternsinreverseorderofgenerationATPGpatternsgofirstRandomly-generatedpatternsgolast(becausetheymayhavelesscoverage)Whencoveragereaches100%,dropremainingpatterns(whicharetheuselessrandomones)Significantlyshortenstestsequence–economiccostreduction2.9TestCompaction

测试压缩Fault402.9.1StaticandDynamicCompaction

静态和动态压缩StaticcompactionATPGshouldleaveunassignedinputsasXTwopatternscompatible–ifnoconflictingvaluesforanyPICombinetwoteststaandtbintoonetesttab

=

tatbusingD-intersectionDetectsunionoffaultsdetectedbyta&tbDynamiccompactionProcesseverypartially-doneATPGvectorimmediatelyAssign0or1toPIstotestadditionalfaults

2.9.1StaticandDynamicCompa412.9.2CompactionExample

压缩实例t1

=01Xt2=0X1t3=0X0t4=X01Combine

t1andt3,then

t2andt4Obtain:t13

=010t24=001TestLengthshortenedfrom4to22.9.2CompactionExample

压缩实例t423SequentialCircuitsATPG

时序电路ATPGAsequentialcircuithasmemoryinadditiontocombinationallogic.Testforafaultinasequentialcircuitisasequenceofvectors,whichInitializesthecircuittoaknownstateActivatesthefault,andPropagatesthefaulteffecttoaprimaryoutputMethodsofsequentialcircuitATPGTime-frameexpansionmethodsSimulation-basedmethods3SequentialCircuitsATPG

时序电433.1Time-FramesExpansionIfthetestsequenceforasinglestuck-atfaultcontainsnvectors,ReplicatecombinationallogicblockntimesPlacefaultineachblockGenerateatestforthemultiplestuck-atfaultusingcombinationalATPGwith9-valuedlogicComb.blockFaultTime-frame0Time-frame-1Time-frame-n+1UnknownorgivenInit.stateVector0Vector-1Vector-n+1PO0PO-1PO-n+1StatevariablesNextstate3.1Time-FramesExpansionIfth443.1.1ExampleforLogicSystems

实例FF2

FF1ABs-a-13.1.1ExampleforLogicSystem4Five-ValuedLogic(Roth)

0,1,D,D,X

A

BXXX0s-a-1DA

BXXX0s-a-1DFF1FF1FF2FF2DDTime-frame-1Time-frame0Five-ValuedLogic(Rot4Nine-ValuedLogic(Muth)

0,1,1/0,0/1,

1/X,0/X,X/0,X/1,XA

BXXX0s-a-10/1A

B0/X0/X0/1

Xs-a-1X/1

FF1FF1FF2FF20/1X/1Time-frame-1Time-frame0Nine-ValuedLogic(Mut473.1.2ImplementationofATPG

ATPG实现SelectaPOforfaultdetectionbasedondrivabilityanalysis.Placealogicvalue,1/0or0/1,dependingonfaulttypeandnumberofinversions.JustifytheoutputvaluefromPIs,consideringallnecessarypathsandaddingbackwardtime-frames.Ifjustificationisimpossible,thenusedrivabilitytoselectanotherPOandrepeatjustification.IftheprocedurefailsforallreachablePOs,thenthefaultisuntestable.If1/0or0/1cannotbejustifiedatanyPO,but1/Xor0/Xcanbejustified,thethefaultispotentiallydetectable.3.1.2ImplementationofATPG

A483.1.3ComplexityofATPG

计算复杂性Synchronouscircuit--Allflip-flopscontrolledbyclocks;PIandPOsynchronizedwithclock:Cycle-freecircuit–Nofeedbackamongflip-flops:Testgenerationforafaultneedsnomorethandseq+1time-frames,wheredseqisthesequentialdepth.Cycliccircuit–Containsfeedbackamongflip-flops:Mayneed9Nfftime-frames,whereNffisthenumberofflip-flops.Asynchronouscircuit–Highercomplexity!Time-Frame0Time-Framemax-1Time-Framemax-2Time-Frame-2Time-Frame-1S0S1S2S3Smaxmax=Numberofdistinctvectorswith9-valuedelements

=9Nff3.1.3ComplexityofATPG

计算复杂性4Cycle-FreeCircuits

无环电路Characterizedbyabsenceofcyclesamongflip-flopsandasequentialdepth,dseq.dseqisthemaximumnumberofflip-flopsonanypathbetweenPIandPO.Bothgoodandfaultycircuitsareinitializable.Testsequencelengthforafaultisboundedbydseq+.1Cycle-FreeCircuits

无环50Cycle-FreeExample

无环电路实例F1F2F3Level=12F1F2F3Level=1233dseq=3s-graphCircuitAllfaultsaretestable.SeeExample.3.2Cycle-FreeExample

无环电5Cycliccircuit

循环电路

Cyclicstructure–Sequentialdepthisundefined.Circuitisnotinitializable.Notestscanbegeneratedforanystuck-atfault.Afterexpandingthecircuitto9Nff=81,orfewer,time-framesATPGprogramcallsanygiventargetfaultuntestable.Circuitcanonlybefunctionallytestedbymultipleobservations.Functionaltests,whensimulated,givenofaultcoverage.Cycliccircuit

循环电路Cy5CyclicCircuitExample

循环电路实例F1F2CNTZModulo-3counters-graphF1FCyclicCircuitExample5BenchmarkCircuitsCircuitPIPOFFGatesStructureSeq.depthTotalfaultsDetectedfaultsPotentiallydetectedfaultsUntestablefaultsAbandonedfaultsFaultcoverage(%)Faultefficiency(%)Max.sequencelengthTotaltestvectorsGentestCPUs(Sparc2)s1196141418529Cycle-free412421239

03099.8100.0

331310s1238141418508Cycle-free413551283

072094.7100.0

330815yclic--14861384

2267693.194.8

2452519941yclic--15061379

2309791.693.4

285591918BenchmarkCircuitsCirc5AsynchronousCircuit

异步电路Anasynchronouscircuitcontainsunclockedmemoryoftenrealizedbycombinationalfeedback.Almostimpossibletobuild,letalonetest,alargeasynchronouscircuit.Clockgenerators,signalsynchronizers,flip-flopsaretypicalasynchronouscircuits.Manylargesynchronoussystemscontainsmallportionsoflocalizedasynchronouscircuitry.SequentialcircuitATPGshouldbeabletogeneratetestsforcircuitswithlimitedasynchronousparts,evenifitdoesnotdetectfaultsinthoseparts.AsynchronousCircuit

异5AsynchronousModel

异步电路模型ClockedFlip-flopsFeedbackdelaysSynchronousPIsSynchronousPOsSystemClock,CKFastmodelClock,FMCKCKCKFeedback-freeCombinationalLogicCCombinationalFeedbackPaths:FeedbacksetModelingcircuitisShowninorange.PPOPPIAsynchronousModel

异步电5Time-FrameExpansion

异步电路时帧扩展Time-framekTime-frame-k+1Time-frame-k-1CFMCKCFMCKCFMCKCCKAsynchronousfeedbackstabilizationPIPOFeedbacksetPPIPPOFeedbacksetVectorkTime-FrameExpansion

异573.2simulation-basedmethods

基于模拟的方法Difficultieswithtime-framemethod:LonginitializationsequenceImpossibleinitializationwiththree-valuedlogicCircuitmodelinglimitationsTimingproblems–testscancauseraces/hazardsHighcomplexityInadequacyforasynchronouscircuitsAdvantagesofsimulation-basedmethodsAdvancedfaultsimulationtechnologyAccuratesimulationmodelexistsforverificationVarietyoftests–functional,heuristic,randomUsedsinceearly1960s3.2simulation-basedmethods

基583.2.1UsingFaultSimulator

使用故障模拟器FaultsimulatorVectorsource:Functional(test-bench),Heuristic(walking1,etc.),Weightedrandom,randomFaultlistTestvectorsNewfaultsdetected?Stoppingcriteria(faultcoverage,CPUtimelimit,etc.)satisfied?StopUpdatefaultlistAppendvectorsRestorecircuitstateGeneratenewtrialvectorsYesNoYesNoTrialvectors3.2.1UsingFaultSimulator

使用593.2.2ContestAConcurrenttestgeneratorforsequentialcircuittesting(Contest).Searchfortestsisguidedbycost-functions.Three-phasetestgeneration:Initialization–nofaultstargeted;cost-functioncomputedbytrue-valuesimulator.Concurrentphase–allfaultstargeted;costfunctioncomputedbyaconcurrentfaultsimulator.Singlefaultphase–faultstargetedoneatatime;costfunctioncomputedbytrue-valuesimulationanddynamictestabilityanalysis.Ref.:Agrawal,etal.,IEEE-TCAD,19ContestAConcurrenttest60ContestResult:s537835PIs,49POs,179FFs,4,603faults.Synchronous,singleclock.Contest75.5%01,72257,5323min.*9min.*Randomvectors67.6%057,532--09min.Gentest**72.6%122490--4.5hrs.10sec.FaultcoverageUntestablefaultsTestvectorsTrialvectorsusedTestgen.CPUtime#Faultsim.CPUtime##SunUltraII,200MHzCPU*Estimatedtime**Time-frameexpansion(highercoveragepossiblewithmoreCPUtime)ContestResult:s53783613.2.3GeneticAlgorithms(GAs)

遗传算法Theoryofevolutionbynaturalselection(Darwin,1809-82.)C.R.Darwin,OntheOriginofSpeciesbyMeansofNaturalSelection,London:JohnMurray,1859.J.H.Holland,AdaptationinNaturalandArtificialSystems,AnnArbor:UniversityofMichiganPress,1975.D.E.Goldberg,GeneticAlgorithmsinSearch,Optimization,andMachineLearning,Reading,Massachusetts:Addison-Wesley,1989.P.MazumderandE.M.Rudnick,GeneticAlgorithmsforVLSIDesign,LayoutandTestAutomation,UpperSaddleRiver,NewJersey,PrenticeHallPTR,1999.BasicIdea:Populationimproveswitheachgeneration.PopulationFitnesscriteriaRegenerationrules3.2.3GeneticAlgorithms(GAs)6GAsforTestGenerationPopulation:Asetofinputvectorsorvectorsequences.Fitnessfunction:Quantitativemeasuresofpopulationsucceedingintaskslikeinitializationandfaultdetection(reciprocaltocostfunctions.)Regenerationrules(heuristics):Memberswithhigherfitnessfunctionvaluesareselectedtoproducenewmembersviatransformationslikemutationandcrossover.GAsforTestGeneratio6StrategateResultss1423s5378s35932Totalfaults1,5154,60339,094Detectedfaults1,4143,63935,100Faultcoverage93.3%79.1%89.8%Testvectors3,94311,571257CPUtime1.3hrs.37.8hrs.10.2hrs.HPJ200256MBRef.:M.S.Hsiao,E.M.RudnickandJ.H.Patel,“DynamicStateTraversalforSequentialCircuitTestGeneration,”ACMTrans.

onDesignAutomationofElectronicSystems(TODAES),vol.5,no.3,July200.2StrategateResults643.2.4SpectralMethods

光谱方法ReplacewithcompactedvectorsTestvectors(initiallyrandomvectors)Faultsimulation-basedvectorcompactionStoppingcriteria(coverage,CPUtime,vectors)satisfied?Extractspectralcharacteristics(e.g.,Hadamardcoefficients)andgeneratevectorsStopAppendnewvectorsCompactedvectorsNoYes3.2.4SpectralMethods

光谱方法Rep6SpectralInformation

光谱信息Randominputsresemblenoiseandhavelowcoverageoffaults.Sequentialcircuittestsarenotrandom:SomePIsarecorrelated.SomePIsareperiodic.Correlationandperiodicitycanberepresentedbyspectralcomponents,e.g.,Hadamardcoefficients.Vectorcompactionremovesunnecessaryvectorswithoutreducingfaultcoverage:Reversesimulationforcombinationalcircuits(Example5.5.)Vectorrestorationforsequentialcircuits.Compactionissimilartonoiseremoval(filtering)andenhancesspectralcharacteristics.SpectralInformation

光6SpectralMethod:s5378Simulation-basedmethodsTime-frameexpansionSpectral-method*StrategateContestHitecGentestFaultcov.79.14%79.06%75.54%70.19%72.58%Vectors73411,5711,722912490CPUtime43.5min.37.8hrs.12.0min.18.4hrs.5.0hrs.PlatformUltraSparc10UltraSparc1UltraIIHP9000/J200UltraII*A.Giani,S.Sheng,M.S.HsiaoandV.D.Agrawal,“EfficientSpectralTechniquesforSequentialATPG,”Proc.IEEEDesignandTestinEurope(DATE)Conf.,March200.2SpectralMethod:s5378674Summary

小结Testabilityapproximatelymeasures:Difficultyofsettingcircuitlinesto0or1DifficultyofobservinginternalcircuitlinesUses:AnalysisofdifficultyoftestinginternalcircuitpartsRedesigncircuithardwareoraddspecialtesthardwarewheremeasuresshowbadcontrollabilityorobservabilityGuidanceforalgorithmscomputingtestpatterns–avoidusinghard-to-controllinesEstimationoffaultcoverage–3-5%errorEstimationoftestvectorlength4Summary

小结Testabilityapprox684Summary(Cont.)

小结（续）TestBridging,Stuck-at,Delay,&TransistorFaultsMusthandlenon-Booleantri-statedevices,buses,&bidirectionaldevices(passtransistors)HierarchicalATPG--9Timesspeedup(Min)Handlesadders,comparators,MUXesComputepropagationD-cubesPropagateandjustifyfaulteffectswiththeseUseinternallogicdescriptionforinternalfaultsResultsof40yearsresearch–mature–methods:PathsensitizationSimulation-basedBooleansatisfiabilityandneuralnetworks4Summary(Cont.)

小结（续）TestB694Summary(Cont.)

小结（续）CombinationalATPGalgorithmsareextended:Time-frameexpansionunrollstimeascombinationalarrayNine-valuedlogicsystemJustificationviabackwardtimeCycle-freecircuits:Requireatmostdseqtime-framesAlwaysinitializableCycliccircuits:Mayneed9Nfftime-framesCircuitmustbeinitializablePartialscancanmakecircuitcycle-free(Chapter14)Asynchronouscircuits:HighcomplexityLowcoverageandunreliabletestsSimulation-basedmethodsaremoreuseful(Section8.3)4Summary(Cont.)

小结（续）Combin704Summary(Cont.)

小结（续）FaultsimulationisaneffectivetoolforsequentialcircuitATPG.Testscanbege