您的当前位置：首页 Studies on integrating SAT-based ATPG in an industrial environment

Studies on integrating SAT-based ATPG in an industrial environment

来源：微智科技网

StudiesonIntegratingSAT-basedATPG

inanIndustrialEnvironment

DanielTille

StephanEggersgluG¨orschwinFey¨ß

InstituteofComputerScience,UniversityofBremen

28359Bremen,Germany

{tille,segg,fey,drechsle}@informatik.uni-bremen.de

RolfDrechsler

AndreasGlowatzFriedrichHapkeJuoﬀel¨rgenSchl¨

NXPSemiconductorsGmbH21147Hamburg,Germany

{andreas.glowatz,friedrich.hapke,juegen.schloeﬀel}@nxp.comAbstract

Duetoeverincreasingdesignsizes,moreeﬃcienttoolsforAutomaticTestPatternGeneration(ATPG)areneeded.Recently,SAT-basedapproachesfortestpatterngenerationhavebeenshowntobeveryeﬃcientevenonlargeindustrialcircuits.ButtheseSAT-basedtechniquesarenotalwayssuperiortoclassicalATPGapproaches.AnintegrationofSAT-basedenginesintotheclassicalATPGﬂowcanimprovetheoverallper-formance.

InthispaperwepresentaﬁrstapproachtointegrateaSAT-basedengineintotheindustrialATPGenviron-mentofNXPSemiconductors.Experimentalresultsforlargeindustrialbenchmarkcircuitsarepresentedthatshowtheimprovementsachievedbytheintegration.

1Introduction

Thecomplexityofcircuitsincreasesrapidly.Ac-cordingtoMoore’slawthenumberofgatesdoublesevery18monthsandthistrendisgoingtolastforatleastanotherdecade.AsaresultthesizeofprobleminstancesthathavetobehandledbyComputerAidedDesign(CAD)toolsalsoincreases.Oneparticularstepinthedesignﬂowisthepostproductiontest.Thistestensuresthefunctionalcorrectnessofachipandisthere-foreanimportantstepinensuringhighqualityprod-ucts.Inpracticethepost-productiontestiscarriedoutbyapplyinginputstimuli–socalled“testpatterns”–tothecircuitandcontrollingtheoutputresponsewithrespecttoitscorrectness.ThetestpatternsarecomputedduringAutomaticTestPatternGeneration(ATPG).ThereforeATPGtoolsalsohavetocopewiththeincreasingsizeofprobleminstances.

AnumberofsophisticatedalgorithmsforATPGhavebeenproposedinthepast.Usually,afaultmodelisusedtomodelphysicaldefectsatthefunctionallevel

inaBooleanrepresentationofthecircuit.Then,thespaceofinputstimuliissearchedtoﬁndatestpat-ternforaparticularfault.AmongthefaultmodelstheStuck-AtFaultModel(SAFM)ismostfrequentlyusedinpractice.TheD-algorithm[10]wastheﬁrstATPGalgorithmtocarryoutaneﬃcientbacktracksearchsteeredbystructuralinformationfromthecir-cuit.ThealgorithmsPODEM[4]andFAN[3]im-provedthebranchingheuristicstomakethesearchmoreeﬃcient.Usingstructuralinformationtoapplyglobalimplicationsduringthesearchhasbeenpro-posedforSOCRATES[12].Themorepowerfulre-cursivelearning[7]andtheintegrationwiththeFAN-algorithmhavebeenproposedbythetoolHANNIBAL[6].Allofthesealgorithmsdirectlyworkonthecircuitstructure.

IncontrasttherealsoexistapproachesbasedonBooleanSatisﬁability(SAT)[8,15,16,13].TheseworkonarepresentationoftheprobleminstanceinCon-junctiveNormalForm(CNF).EarlySAT-basedap-proacheswerenotabletohandleindustrialinstances.ButtherecentadvancesinalgorithmsforSATsolv-ing[9,1]madetheapplicationtoATPGfeasible.Thecombinationoftheseadvancesandstructuralknowl-edgeintoanATPGtoolprovideaneﬃcientandro-bustATPGenginewhichhasbeenshownbythetoolPASSAT[13,14].

Ofcourse,itcannotbeexpectedthatasingleSAT-basedengineisfasteronallATPGinstancesthanthesophisticatedclassicalapproaches.Inindustrialtoolsthecombinationofdiﬀerenttechniqueslikerandomsimulation,learning,andothersiscrucialtoachievero-bustness.TobeneﬁtfromapowerfulSAT-basedengineinsuchanenvironment,thecombinationwithotherATPGapproacheshastobeconsidered.ButsofarnotightintegrationofaSAT-basedengineintoanindus-trialframeworkhasbeenproposed.

Here,wepresenttheintegrationofaSAT-baseden-gineintothepre-identiﬁcationphaseoftheindustrialATPGenvironmentfromNXPSemiconductors.The

CircuitFault modelPre-identificationRandom detectionFast deterministic detectionDeterministic detectionaborted testableredundantCompactionCompact TPGFault simulationTest setFigure2.ATPGﬂow

ered.ThiscanbeeﬃcientlyhandledbyaSAT-basedATPGtool[13].

3IndustrialEnvironment

Inprincipleitissuﬃcienttoiterateoverallfaultswithrespecttothegivenfaultmodelandgenerateatestpatternforeachofthem.Butinanindustrialen-vironmentlikethatofNXPSemiconductorsthisisnotsuﬃcienttoretrievearobustsystem.Inthefollowingonlytheoverallﬂowinthesystemwillbebrieﬂyre-viewedtoexplaintheproblemsthatoccurduringtheintegrationofaSAT-basedengine.Theparticularim-provementsinthehighlyoptimizedtestingtoolAM-SALthatwasusedfortheexperimentscannotbeex-plainedindetail.ForamoredetailedpresentationonATPGsystemsingeneralwerefertoe.g.[5].

ThemajorstepsoftheATPGﬂowareshowninFig-ure2.Theinputsforthesystemarethecircuitandthefaultmodeltobeconsidered.Here,theSAFMisassumed.Twomainstepsarecarriedout:thepre-identiﬁcationphasetoclassifyfaultsandthecom-pactionphasetogenerateasmalltestset.Thegoalduringpre-identiﬁcationistheclassiﬁcationoffaults.Here,threeenginesareused.First,randomfaultde-tectionisappliedtoﬁlterouteasy-to-detectfaults.Fortheremainingfaultsafastdeterministicfaultdetectionisdone.Finally,deterministicfaultdetectionwithin-creadedresourcesisappliedtoclassifyhard-to-detectfaults.Asaresultfourclassesoffaultsaregenerated:untestablefaults,easilytestablefaults,hardtestablefaultsandnon-classiﬁedabortedfaults.Untestableandeasy-to-detectfaultsarenotfurtherconsidered.Onlytheremainingtestablefaultsarefurthertreatedinthecompactionstep.Inthecompactionsteptestpatternsthatdetectasmanyfaultsaspossiblearegenerated.Thisisnecessarybecauseasmalltestsetresultsinshortertesttimesduringthepost-productiontest.

Deterministic generationFAN-based enginetestDeterministic generationnextredun-dantabortFAN-based enginefaultSAT-based enginenextredundant/testfaultabortred./ab.testFault simulationFault simulation(a)Normal

(b)SAT-based

Figure3.Deterministicfaultdetection

Themainstepconsideredhereisthedeterministicfaultdetectionappliedinthepre-identiﬁcationphase.Inthisphaseitisimportanttoclassifyasmanyfaultsaspossible.Onlyfaultsclassiﬁedastestablearecon-sideredduringthecompacttestpatterngeneration.Abortedfaultsareconsideredduringfaultsimulationaswell.Thereforeuntestablefaultsthatwerenotclas-siﬁed,i.e.aborted,areanoverheadinthecompactionstep.TestablefaultsthatwerenotclassiﬁedmaynotbedetectedbycompactTPG.

ThedetailsofthedeterministicfaultdetectionareshowninFigure3(a).Usually,ahighlyoptimizedFAN-basedATPGengineincludinglearningtechniquesandafaultsimulatorareappliedfordeterministictestpat-terngeneration.First,theFAN-basedengineisusedtoclassifyagivenfault.Ifatestpatternisproducedbythisengine,additionalfaultsmaybedetectedbythepatternbesidesthefaulttargetedintheﬁrstplace.Thereforeafaultsimulatorisusedtocalculateallfaultsdetectedbythetestpattern.Thisconsumesadditionalcomputationtime,butoftenspeedsuptheoverallpro-cessbecauseotherpatternscanberemovedfromthefaultlist.

4Integration

WhenintegratingaSAT-basedATPGengineintoanindustrialenvironment,thegoalistoimprovetheoverallperformanceofthesystem.Forimprovingtheperformance,twoaspectshavetobeconsidered:theruntimeandthenumberofclassiﬁedfaults.Theruntimeshouldbedecreased.Thenumberoffaultsthatareclassiﬁedbythesystemshouldbeincreased,i.e.thenumberofabortedfaultclassiﬁcationsduetoresourcelimitsshouldbedecreased.Inthefollowingwecon-centrateonintegratingtheSAT-basedengineintothepre-identiﬁcationphasebecausereducingthenumberofabortedfaultsinthisstepisbeneﬁcialforthesuc-ceedingcompactionstepasexplainedintheprevioussection.

Theunderlyingproblemistodeterminehowtoin-terlacetheengines.Theintegrationofrandomsimula-tionanddeterministicalgorithmsisdonebyapplyingsimulationinafastpre-processingstep.Thisorder-ingisalsofeasiblewhenanadditionalSAT-baseden-gineisavailable.SimilartoaFAN-basedapproachtheSAT-basedengineneedstimetogeneratetheprobleminstancebeforesolvingcanbestarted.Thisoverhead

ismuchsmallerwhenrandomsimulationisapplied.ThereforetheintegrationintothedeterministictestpatterngenerationbetweentheFAN-basedengineandfaultsimulationhasbeenaddressed.

Anumberofobservationshelpstosetuptheframe-workfortheintegration:

•TherearefaultsthatareeasilyclassiﬁedbyFANwhileSATneedsalongruntimeandviceversa.Thisbehaviorisnotpredictablefromthefaultit-self.•AlargenumberoffaultscanbeclassiﬁedeﬃcientlyusingFAN.•OftentheSAT-basedengineeﬃcientlyclassiﬁesuntestablefaultsandfaultsthatarehardforFAN,i.e.thosefaultswhereFANneedslongruntimesorabortsduetopre-deﬁnedresourcelimits.•ASATsolverdeterminesvaluesforallinputsthatarecontainedinthetransitivefan-inofthoseoutputswherethefaultmaybeobserved.Thismakesmergingofmultipletest-patternsduringcompactiondiﬃcult.•TheFAN-basedalgorithmdirectlyrunsonthecir-cuitstructurewhichisavailableinthesystemal-ready.•TheSAT-basedalgorithmconvertstheproblemintoaCNFbeforestartingtheSATsolver.There-forealargeroverheadperfaultisneededcomparedtoFAN.TheseobservationsleadtotheconclusionthattheSAT-basedengineshouldbeusedtotargetthosefaultsthatcannotbeclassiﬁedbytheFAN-algorithmwithinashorttimeout.Thisreducestheoverheadforinitial-izingtheSAT-basedengineonfaultsthatareeasytoclassifybyFANalready.Then,theSAT-basedTPGmayclassifyadditionalfaultswhich,inturn,helpstoremoveotherfaultsfromthefaultlistaswell.

ThisleadstotheframeworkshowninFigure3(b)whenaparticularfaultistargeted.TheFAN-basedengineisstartedatﬁrstwiththedefaultparameterset.Ifatestpatternisgenerated,faultsimulationiscarriedoutasusualandmayidentifyadditionalfaultsasbeingtestablebythesametestpattern.Otherwise,theSAT-basedengineisappliedtoclassifythefaultinasecondstep.

TheexperimentsshowthatthiscombinedapproachclassiﬁesmorefaultswithalmostnooverheadfortheadditionalrunsoftheSAT-basedengine.

5ExperimentalResults

Experimentalresultsarereportedinthissection.

TheproposedintegrationofaSAT-basedengineintotheindustrialenvironmentwasappliedtotheNXPSemiconductorsATPGtoolAMSAL.AsSATsolverweusedMiniSat[1].AMSALprovidesverycompact

Table1.Pre-identiﬁcationFresultsCircuitp44kTargetsab.FAN(de)ab.AN(long)SATFAN+SATp77k12time07:46mtimeab.03:44htimeab.timep80k163310105p88k19783414774221807:44m43:04m0:24m7900:24m00:36m007:57m0:45mp177kp99k162019139819512:21m9:04m6155144:06m13:56m016:27m01:03h043:23m015:55m13:28m0012:44m11:56mp462k268176138327021:40m9286022:01mp1330k

p565k10268516739491516144

13981:53haborted2:35h1541:58h80810:43h927:27maborted2:43h13604:49h12:38h15:21haborted01:57h2:40hproductionandﬁeldtestpatternstoraisethequalityoflargeandcomplexdigitalcircuits.Since1986AM-SALhasbeencontinuouslydevelopedandcoversfaultslikestuck-at,bridges,gate-andpath-delaytransitionsaswellasIddqfaults.Togetherwiththepossibilitiesofarootcauseanalysis,layoutbasedpatterngenera-tionandtestpointinsertionwithextremelyhightestcompactionisperformed,resultinginaminimumsetoftestpatterns.AsinSOCRATES[11]andHAN-NIBAL[6],themainATPGengineofAMSALisahighlyoptimizedFAN-algorithm.TheSAT-baseden-gineisintegratedintothesysteminaprototypicman-nerasexplainedinSection4.TheresourcelimitsoftheFAN-basedalgorithmweresettothedefaultset-tingsofAMSALsincetheseparametershavebeende-terminedonalargerangeofcircuits.ThetimeoutfortheSAT-basedenginewassetto20secondsperfault.Thisisaquitehighruntimelimit,buttheex-perimentalresultsshowthatthisisusefultoclassifyveryhardfaults[13].Thissavesruntimeafterwards.Asaresult,aloosecouplingbetweentheenginesisachieved.AllfaultsthatwouldnotbeclassiﬁedintheclassicalﬂowaretargetedbytheSAT-baseden-gineafterwards.Thereby,morefaultscanbeclassi-ﬁedintotal.TheSAT-basedenginerunsintwosteps:FirsttheCNFisgenerated,then,thefaultisclassi-ﬁed;afterwardstheCNFiscompletelydropped.Thisapproachisacceptableinthepresentsetting,becausetheSAT-basedengineisonlyappliedtoabortedclas-siﬁcationsthatare“randomly”distributed.ThereforeidentifyingstructuraloverlappingofCNFinstancesisdiﬃcult.Forallothersettingsintheﬂow,e.g.thenum-berofrandompatternstobesimulated,thedefaultparametersofAMSALwereused.AllofthefollowingexperimentswererunonanAMDAthlonXP3500+(2.2GHz,1GByte,GNU/Linux).

Asetofindustrialcircuits(providedbyNXP)wasconsideredasbenchmarks.ThesecircuitshavebeenfoundtobediﬃcultcasesforATPG.Thenameofthecircuitalsogivesinformationaboutthenumberofgatescontainedinthecircuit,e.g.p88kmeansthatthecir-cuitsconsistsofabout88,000gates.Thelargestcircuitp1330kcontainsmorethan1.3milliongates.Thenum-beroffaultsthathavetobeconsideredforacircuitisevenlargerthanthenumberofgatesascanbeseeninTable1;Column‘Targets’givesthenumberoffaultsafterthefaultcollapsingstep.

Fourdiﬀerentapproachesarecomparedinthefol-lowing:

•“FAN(de)”:UsingtheFAN-basedenginewithde-faultparametersasexplainedabove.

•“FAN(long)”:UsingtheFAN-basedenginewithdrasticallyincreasedresources,i.e.thebacktracklimitsetto1024andupto5secondsperfault.•“SAT”:UsingonlytheSAT-basedengine,i.e.re-placingtheFAN-basedenginebytheSAT-basedengineintheﬂow.•“FAN+SAT”:UsingthecombinedapproachasexplainedinSection4.Table1showstheresultsofthepre-identiﬁcationphase.Foreachapproachthenumberofabortedfaultclassiﬁcations(column‘ab.’)andtheruntime(col-umn‘time’)aregiven.MostcriticalareabortedfaultsbecausethesemaynotbetargetedadequatelyinthecompactionstepasexplainedinSection3.

Thenumberoffaultsabortedbythedefaultap-proachFAN(de)isquitelarge.ThisnumbercanbereducedbyusingFAN(long),wheretheresourcesareincreased.However,therearestilltoomanyabortedfaults.Oncircuitp1330k,theclassiﬁcationusingFANevenabortsduetomemoryexplosion,i.e.thecircuitrepresentationdoesnotﬁtintotheavailablemainmemoryandthetestpatterngenerationprocessaborts.UsingtheSAT-basedengine,manycircuits,whereabortsoccurattheFANapproach,arenowfullytestable.

However,regardingtheruntime,theusageoftheSAT-basedengineasastandalonealgorithmcausestoomuchoverhead(aCNFformulahastobecreatedforeachfault).OnlythreecircuitsarenotfullytestablewiththeSAT-basedapproach:Whileinp462kthenumberofabortsdecreasesdrastically,inp177kmoreabortsoccur.Actually,therepresentationofp1330kasSATinstanceiscompactenoughtoﬁtintothemainmemory,i.e.theentiretestpatterngenerationprocesscanbeperformed.

RegardingtheFAN+SATapproach,theruntimeissimilartothatofFAN(de).However,onceagain,thenumberofabortsdecreasesinthiscombinedap-proach.Thisispossiblebecausemanyeasy-to-detectfaultarequicklyclassiﬁedbyFANwhilediﬃcultfaultsareclassiﬁedbytheSAT-basedengine.

Insummary,thecombinedapproachisabletofullyclassify6outof9benchmarkswhiletheresourcesneededremainsimilartothatofaclassicalapproach.

6ConclusionsandFutureWork

TheintegrationofaSAT-basedATPGengineintoanindustrialenvironmenthasbeenshown.ThereasonforapplyingtheSAT-basedengineasaseconddeter-ministicATPGsteptoabortedfaultswasexplainedindetail.Experimentalresultsshowtheimprovedrobust-nessachievedbythecombinationofclassicalATPGal-gorithmswithaSAT-basedapproach.Evenonlargeindustrialcircuitsthatarehardtotesttheproposedcombinedapproachperformsbetterthanclassicalen-ginesalone.

Furtherresearchisgoingtoaddressthereuseoflearnedinformationasapromisingimprovement[2].

AnothermainfocuswillbetheintegrationofaSAT-basedapproachintothecompactionstep.

Acknowledgements

PartsofthisresearchworkweresupportedbytheGermanFederalMinistryofEducationandResearch(BMBF)intheProjectMAYAunderthecontractnum-ber01M3172B.Furthermore,theauthorswouldliketothankJunhaoShiforhelpfuldiscussions.

References

[1]N.E´enandN.S¨orensson.AnextensibleSATsolver.

InSAT2003,volume2919ofLNCS,pages502–518,[2]2004.

G.Fey,T.Warode,andR.Drechsler.Usingstructural

learningtechniquesinSAT-basedATPG.InVLSIDe-[3]signH.FujiwaraConf.,pagesandT.69–74,Shimono.2007.

Ontheaccelerationof

testgenerationalgorithms.IEEETrans.onComp.,[4]32:1137–1144,P.Goel.Animplicit1983.

enumerationalgorithmtogen-eratetestsforcombinationallogic.IEEETrans.on[5]Comp.N.Jha,and30:215–222,S.Gupta.1981.

TestingofDigitalSystems.Cam-[6]bridgeW.Kunz.UniversityHANNIBAL:Press,An2003.

eﬃcienttoolforlogicver-iﬁcationbasedonrecursivelearning.InInt’lConf.on[7]CADW.Kunz,pagesand538–543,D.Pradhan.1993.

Recursivelearning:Anew

implicationtechniqueforeﬃcientsolutionsofCADproblems:Test,veriﬁcationandoptimization.IEEE[8]Trans.T.Larrabee.onCADTest,13(9):1143–1158,patterngeneration1994.

usingBoolean

[9]satisﬁability.M.Moskewicz,IEEEC.Madigan,Trans.onY.CADZhao,,11:4–15,L.Zhang,1992.and

S.Malik.Chaﬀ:EngineeringaneﬃcientSATsolver.[10]InJ.DesignRoth.DiagnosisAutomationofConf.automata,pagesfailures:530–535,A2001.calculus

[11]andM.Schulz,amethod.E.Trischler,IBMJ.Res.andDev.T.Sarfert.,10:278–281,SOCRATES:

1966.Ahighlyeﬃcientautomatictestpatterngeneration[12]system.M.H.InSchulz,Int’lTestE.Trischler,Conf.,pagesand1016–1026,T.M.1987.Sarfert.

SOCRATES:Ahighlyeﬃcientautomatictestpatterngenerationsystem.IEEETrans.onCAD,7(1):126–[13]137,J.Shi,1988.

G.Fey,R.Drechsler,A.Glowatz,F.Hapke,

andJ.Schlo¨ﬀel.PASSAT:EﬀcientSAT-basedtestpatterngenerationforindustrialcircuits.InIEEEAn-[14]nualJ.Shi,SymposiumG.Fey,R.onDrechsler,VLSI,pagesA.Glowatz,212–217,J.2005.SchlandF.Hapke.ExperimentalstudiesonSAT-based¨oﬀel,

testpatterngenerationforindustrialcircuits.InInt’l[15]Conf.P.Stephan,onASIC,R.pagesBrayton,967–970,and2005.

A.Sangiovanni-Vincentelli.Combinationaltestgenerationusingsat-[16]isﬁability.P.Tafertshofer,IEEEA.Trans.Ganz,onandCADK.,15:1167–1176,Antreich.Igraine1996.-animplicationgraphbasedengineforfastimplication,justiﬁcation,andpropagation.IEEETrans.onCAD,19(8):907–927,2000.

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文