第08講-自動測試生成超大規(guī)模集成電路測試技術(shù)課件

Lecture8AutomaticTestPatternGeneration第八講自動測試生成Lecture8AutomaticTestPatte1Contents

內(nèi)容目錄TestabilityMeasures/可測試性測度CombinationalCircuitATPG/組合電路ATPGSequentialCircuitATPG/

時序電路ATPGSummary/小結(jié)Contents

內(nèi)容目錄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

可控制性規(guī)則1.4.2ControllabilityRules

可控91.4.2ControllabilityRules(Cont.)

可控制性規(guī)則（續(xù)）1.4.2ControllabilityRules(C101.4.3ObservabilityRules

可觀察性規(guī)則Toobserveagateinput:Observeoutputandmakeotherinputvaluesnon-controlling1.4.3ObservabilityRules

可觀察性111.4.3ObservabilityRules(Cont.)

可觀察性規(guī)則Toobserveafanoutstem:Observeitthroughbranchwithbestobservability1.4.3ObservabilityRules(Con121.4.4DFlip-FlopRules

D觸發(fā)器規(guī)則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觸發(fā)器規(guī)則131.4.4DFlip-FlopRules(Cont.)

D觸發(fā)器規(guī)則（續(xù)）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

功能和結(jié)構(gòu)測試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

算法代數(shù)：5值和9值邏輯代數(shù)SymbolDD01XG0G1F0F1Meaning1/00/10/01/1X/X0/X1/XX/0X/1FailingMachine0101XXX01GoodMachine1001X01XXRoth’sAlgebraMuth’sAdditions2.3Algebras:5-Valuedand9-V212.3.1Higher-OrderAlgebras

高階代數(shù)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.)

電路實例（續(xù)）Trysimultaneouspathsf–h–k–Land

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

電路實例（續(xù)）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

測試生成系統(tǒng)CircuitDescriptionTestPatternsUndetectedFaultsRedundantFaultsAbortedFaultsBacktrackDistributionFaultListCompacterSOCRATESWithfaultsimulator2.8TestGenerationSystems

測試392.9TestCompaction

測試壓縮FaultsimulatetestpatternsinreverseorderofgenerationATPGpatternsgofirstRandomly-generatedpatternsgolast(becausetheymayhavelesscoverage)Whencoveragereaches100%,dropremainingpatterns(whicharetheuselessrandomones)Significantlyshortenstestsequence–economiccostreduction2.9TestCompaction

測試壓縮Fault402.9.1StaticandDynamicCompaction

靜態(tài)和動態(tài)壓縮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實現(xiàn)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

無環(huán)電路Characterizedbyabsenceofcyclesamongflip-flopsandasequentialdepth,dseq.dseqisthemaximumnumberofflip-flopsonanypathbetweenPIandPO.Bothgoodandfaultycircuitsareinitializable.Testsequencelengthforafaultisboundedbydseq+.1Cycle-FreeCircuits

無環(huán)50Cycle-FreeExample

無環(huán)電路實例F1F2F3Level=12F1F2F3Level=1233dseq=3s-graphCircuitAllfaultsaretestable.SeeExample.3.2Cycle-FreeExample

無環(huán)電5Cycliccircuit

循環(huán)電路

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

循環(huán)電路Cy5CyclicCircuitExample

循環(huán)電路實例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

小結(jié)Testabilityapproximatelymeasures:Difficultyofsettingcircuitlinesto0or1DifficultyofobservinginternalcircuitlinesUses:AnalysisofdifficultyoftestinginternalcircuitpartsRedesigncircuithardwareoraddspecialtesthardwarewheremeasuresshowbadcontrollabilityorobservabilityGuidanceforalgorithmscomputingtestpatterns–avoidusinghard-to-controllinesEstimationoffaultcoverage–3-5%errorEstimationoftestvectorlength4Summary

小結(jié)Testabilityapprox684Summary(Cont.)

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

小結(jié)（續(xù)）TestB694Summary(Cont.)

小結(jié)（續(xù)）CombinationalATPGalgorithmsareextended:Time-frameexpansionunrollstimeascombinationalarrayNine-valuedlogicsystemJustificationviabackwardtimeCycle-freecircuits:Requireatmostdseqtime-framesAlwaysinitializableCycliccircuits:Mayneed9Nfftime-framesCircuitmustbeinitializablePartialscancanmakecircuitcycle-free(Chapter14)Asynchronouscircuits:HighcomplexityLowcoverageandunreliabletestsSimulation-basedmethodsaremoreuseful(Section8.3)4Summary(Cont.)

小結(jié)（續(xù)）Combin704Summary(Cont.)

小結(jié)（續(xù)）FaultsimulationisaneffectivetoolforsequentialcircuitATPG.Testscanbege