中科院研究生院课程VLSI测试与可测试性设计(精)ppt课件

1,中科院研究生院课程：VLSI测试与可测试性设计,第4讲逻辑与故障模拟李晓维中科院计算技术研究所Email:lxw,2,Chapter3,LogicandFaultSimulation,3,AbouttheChapter,CircuitsimulationmodelsLogicsimulationtechniquesFaultsimulationtechniques,4,LogicandFaultSimulation,IntroductionSimulationmodelsLogicsimulationFaultsimulationConcludingremarks,5,PredictthebehaviorofadesignpriortoitsphysicalrealizationDesignverification,LogicSimulation,6,FaultSimulation,PredictsthebehavioroffaultycircuitsAsaconsequenceofinevitablefabricationprocessimperfectionsAnimportanttoolfortestanddiagnosisEstimatefaultcoverageFaultsimulatorTestcompactionFaultdiagnosis,7,LogicandFaultSimulation,IntroductionSimulationmodelsLogicsimulationFaultsimulationConcludingremarks,8,Gate-LevelNetwork,Theinterconnectionsoflogicgates,9,SequentialCircuits,Theoutputsdependonboththecurrentandpastinputvalues,xi:primaryinput(PI)zi:primaryoutput(PO)yi:pseudoprimaryinput(PPI)Yi:pseudoprimaryoutput(PPO),10,APositiveEdge-TriggeredD-FF,11,Example:AFull-Adder,12,LogicSymbols,Themostcommonlyusedare0,1,uandZ1and0trueandfalseofthetwo-valueBooleanalgebrauUnknownlogicstate(maybe1or0)ZHigh-impedancestateNotconnectedtoVddorground,13,TernaryLogic,Threelogicsymbols:0,1,andu,14,InformationLossofTernaryLogic,SimulationbasedonternarylogicispessimisticAsignalmaybereportedasunknownwhenitsvaluecanbeuniquelydeterminedas0or1,15,High-ImpedanceStateZ,Tri-stategatespermitseveralgatestotime-shareacommonwire,calledbusAsignalisinhigh-impedancestateifitisconnectedtoneitherVddnorground,16,LogicElementEvaluationMethods,ChoiceofevaluationtechniquedependsonConsideredlogicsymbolsTypesandmodelsoflogicelementsCommonlyusedapproachesTruthtablebasedInputscanningInputcountingParallelgateevaluation,17,TruthTableBasedGateEvaluation,ThemoststraightforwardandeasytoimplementForbinarylogic,2nentriesforn-inputlogicelementMayusetheinputvalueastableindexTablesizeincreasesexponentiallywiththenumberofinputsCouldbeinefficientformulti-valuedlogicAk-symbollogicsystemrequiresatableof2mnentriesforann-inputlogicelementm=log2kTableindexedbymn-bitwords,18,ParallelGateEvaluation,ExploittheinherentconcurrencyinthehostcomputerA32-bitcomputercanperform32logicoperationsinparallel,19,TimingModels,TransportdelayInertialdelayWiredelayFunctionelementdelaymodel,20,TransportDelay,Thetimedurationittakesfortheeffectofgateinputchangestoappearatgateoutputs,21,InertialDelay,Theminimuminputpulsedurationnecessaryfortheoutputtoswitchstates,22,WireDelay,WiresareinherentlyresistiveandcapacitiveIttakesfinitetimeforasignaltopropagatealongawire,23,FunctionalElementDelayModel,Formorecomplicatedfunctionalelementslikeflip-flops,24,ModelingLevels,25,LogicandFaultSimulation,IntroductionSimulationmodelsLogicsimulationFaultsimulationConcludingremarks,26,CompiledCodeSimulation,Translatethelogicnetworkintoaseriesofmachineinstructionsthatmodelthegatefunctionsandinterconnections,27,LogicOptimization,Enhancethesimulationefficiency,28,Event-DrivenSimulation,Event:theswitchingofasignalsvalueAnevent-drivensimulatormonitorstheoccurrencesofeventstodeterminewhichgatestoevaluate,29,Zero-DelayEvent-DrivenSimulation,GateswitheventsattheirinputsareplacesintheeventqueueQ,30,Nominal-DelayEvent-DrivenSimulation,NeedasmarterschedulerthantheeventqueueNotonlywhichgatesbutalsowhentoevaluate,31,Two-PassEvent-DrivenSimulation,32,Event-DrivenAlgorithm(Example),33,Example,34,Compiled-Codevs.Event-DrivenSimulation,Compiled-codeCycle-basedsimulationHighswitchingactivitycircuitsParallelsimulationLimitedbycompilationtimesEvent-drivenImplementinggatedelaysanddetectinghazardsLowswitchingactivitycircuitsMorecomplicatedmemorymanagement,35,LogicandFaultSimulation,IntroductionSimulationmodelsLogicsimulationFaultsimulationConcludingremarks,36,FaultSimulation,IntroductionSerialFaultSimulationParallelFaultSimulationDeductiveFaultSimulationConcurrentFaultSimulationDifferentialFaultSimulationFaultDetectionComparisonofFaultSimulationTechniquesAlternativetoFaultSimulationConclusion,37,Introduction,Whatisfaultsimulation?GivenAcircuitAsetoftestpatternsAfaultmodelDetermineFaultyoutputsUndetectedfaultsFaultcoverage,38,TimeComplexity,Proportionalton:Circuitsize,numberoflogicgatesp:Numberoftestpatternsf:NumberofmodeledfaultsSincefisroughlyproportionalton,theoveralltimecomplexityisO(pn2),39,SerialFaultSimulation,First,performfault-freelogicsimulationontheoriginalcircuitGood(fault-free)responseForeachfault,performfaultinjectionandlogicsimulationFaultycircuitresponse,40,SerialFaultSimulation,41,AlgorithmFlow,42,Example,43,FaultDropping,HaltingsimulationofthedetectedfaultExampleSupposewearetosimulateP1,P2,P3inorderFaultfisdetectedbyP1DonotsimulatefforP2,P3ForfaultgradingMostfaultsaredetectedafterrelativelyfewtestpatternshavebeenappliedForfaultdiagnosisAvoidedtoobtaintheentirefaultsimulationresults,44,ProandCon,AdvantagesEasytoimplementAbilitytohandleawiderangeoffaultmodels(stuck-at,delay,Br,)DisadvantagesVeryslow,45,ParallelFaultSimulation,ExploittheinherentparallelismofbitwiseoperationsParallelfaultsimulationSeshu1965ParallelinfaultsParallelpatternfaultsimulationWaicukauski1986Parallelinpatterns,46,ParallelFaultSimulation,AssumptionUsebinarylogic:onebitisenoughtostorelogicsignalUsew-bitwidedatawordParallelsimulationw-1bitforfaultycircuits1bitforfault-freecircuitProcessfaultyandfault-freecircuitinparallelusingbitwiselogicoperations,47,ParallelFaultSimulation,48,FaultInjection,49,Example,50,ProandCon,AdvantagesAlargenumberoffaultsaredetectedbyeachpatternwhensimulatingthebeginningoftestsequenceDisadvantagesOnlyapplicabletotheunitorzerodelaymodelsFaultscannotbedroppedunlessall(w-1)faultsaredetected,51,ParallelPatternFaultSimulation,Parallelpatternsinglefaultpropagation(PPSFP)ParallelpatternWithaw-bitdatawidth,wtestpatternsarepackedintoawordandsimulatedforthefault-freeorfaultycircuitSinglefaultFirst,fault-freesimulationNext,foreachfault,faultinjectionandfaultycircuitsimulation,52,AlgorithmFlow,53,Example,54,ProandCon,AdvantagesFaultisdroppedassoonasdetectedBestforsimulatingtestpatternsthatcomelater,wherefaultdroppingrateperpatternislowerDisadvantagesNotsuitableforsequentialcircuits,55,DeductiveFaultSimulation,Armstrong1972BasedonlogicreasoningratherthansimulationFaultlistattachedwithsignalxdenotedasLxSetoffaultscausingxtodifferfromitsfault-freevalueFaultlistpropagationDerivethefaultlistofagateoutputfromthoseofthegateinputsbasedonlogicreasoning,56,FaultListPropagationRules,Allgateinputsholdnon-controllingvalueAtleastoneinputholdscontrollingvalue,c:controllingvaluei:inversionvalueI:setofgateinputsz:gateoutputS:inputsholdingcontrollingvalue,(3.1),(3.2),57,AlgorithmFlow,58,Example,P1,byEq.(3.1),59,Example(contd),P2,A,B,C,E,F,J,L,H,K,0,0,1,LB=B/1,LC=C/0,1,1,0,0,1,C/0,1,C/0,C/0,C/0,C/0,60,Example(contd),P3,byEq.(3.2),LC=C/1,61,ProandCon,AdvantagesVeryefficientSimulateallfaultsinonepassDisadvantagesNoteasytohandleunknownsOnlyforzero-delaytimingmodelPotentialmemorymanagementproblem,62,ConcurrentFaultSimulation,Ulrich1974SimulateonlydifferentialpartsofwholecircuitEvent-drivensimulationwithfault-freeandfaultycircuitssimulatedaltogetherConcurrentfaultlistforeachgateConsistofasetofbadgatesFaultindex&associatedgateI/OvaluesInitiallyonlycontainslocalfaultsFaultpropagatefrompreviousstage,63,GoodEventandBadEvent,GoodeventEventsthathappeningoodcircuitAffectbothgoodgatesandbadgatesBadeventEventsthatoccurinthefaultycircuitofcorrespondingfaultAffectonlybadgatesDivergeAdditionofnewbadgatesConvergeRemovalofbadgateswhoseI/Osignalsarethesameascorrespondinggoodgates,64,AlgorithmFlow,65,Example,P1,66,Example(contd),P2,67,Example(contd),P3,68,ProandCon,AdvantagesEfficientDisadvantagesPotentialmemoryproblemSizeoftheconcurrentfaultlistchangesatruntime,69,FaultDetection,HarddetectedfaultOutputsoffault-freeandfaultycircuitaredifferent1/0or0/1Nounknowns,noZPotentiallydetectedfaultWhetherthefaultisdetectedisunclearExample:stuck-at-0onenablesignaloftri-statebuffer,70,FaultDetection(contd),OscillationfaultsCausecircuittooscillateImpossibletopredictfaultycircuitoutputsHyperactivefaultsCatastrophicfaulteffectFaultsimulationistimeandmemoryconsumingExample:stuck-atfaultonclockUsuallycountedasdetectedSavefaultsimulationtime,71,ComparisonofFaultSimulationTechniques(1),SpeedSerialfaultsimulation:slowestParallelfaultsimulation:O(n3),n:numofgatesDeductivefaultsimulation:O(n2)ConcurrentfaultisfasterthandeductivefaultsimulationDifferentialfaultsimulation:evenfasterthanconcurrentfaultsimulationandPPSFPMemoryusageSerialfaultsimulation,parallelfaultsimulation:noproblemDeductivefaultsimulation:dynamicallocatememoryandhardtopredictsizeConcurrentfaultsimulation:moreseverethandeductivefaultsimulationDifferentialfaultsimulation:lessmemoryproblemthanconcurrentfaultsimulation,72,ComparisonofFaultSimulationTechniques(2),Multi-valuedfaultsimulationtohandleunknown(X)and/orhigh-impedance(Z)Serialfaultsimulation,concurrentfaultsimulation,differentialfaultsimulation:easytohandleParallelfaultsimulation:difficultDelayandfunctionalmodelingcapabilitySerialfaultsimulation:noproblemParallelfaultsimulation,deductivefaultsimulation:notcapableConcurrentfaultsimulation:capableDifferentialfaultsimulation:capable,73,ComparisonofFaultSimulationTechniques(3),SequentialcircuitSerialfaultsimulation,parallelfaultsimulation,concurrentfaultsimulation,differentialfaultsimulation:noproblemPPSFP:difficultDeductivef