probabilistic simulation for reliability analysis of cmos vlsi circuits

《probabilistic simulation for reliability analysis of cmos vlsi circuits》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

ProbabilisticSimulationforReliabilityAnalysisofCMOSVLSICircuitsbyyzzyFaridN.Najm,RichardBurch,PingYang,andIbrahimN.HajjyzCoordinatedScienceLaboratoryVLSIDesignLaboratoryUniversityofIllinoisatUrbana-ChampaignTexasInstrumentsInc.Urbana,Illinois61801Dallas,Texas75265AbstractAnovelcurrent-estimationapproachisdevelopedtosupporttheanalysisofelectromi-grationfailuresinpowersupplyandgroundbussesofCMOSVLSIcircuits.Itusestheoriginalconceptofprobabilisticsimulationtoecientlygenerateaccurateestimatesoftheexpectedcurrentwaveformrequiredforelectromigrationanalysis.Assuch,theapproachispattern-independentandrelievesthedesignerofthetedioustaskofspecifyinglogicalinputwaveforms.ThisapproachhasbeenimplementedintheprogramCRESTwhichhasshownexcellentaccuracyanddramaticspeedupscomparedtotraditionalapproaches.Wedescribetheapproachanditsimplementation,andpresenttheresultsofnumerousCRESTrunsonrealcircuits.F.NajmisnowwiththeVLSIDesignLaboratory,TexasInstrumentsInc.,Dallas,Texas75265ThisworkwassupportedbyTexasInstrumentsIncorporated,andtheUSAirForceRomeAirDevelopmentCenter. 1IntroductionThereliabilityofintegratedcircuitsisamajorconcernfortheelectronicsindustry.Ashigherlevelsofintegrationareused,theminimumlinewidthandlineseparationwilldecrease,therebyincreasingthechipfailurerate.Thisindicatesthattheimportanceofreliabilitycanonlyincreaseinthefuture.Itis,therefore,imperativethatcircuitsaredesignedwithreliabilityinmind.Thisworkaddresseselectromigration[1,2](EM),whichisamajorreliabilityproblemcausedbythetransportofatomsinametallineduetotheelectron ow.Underpersistentcurrentstress,thiscancausedeformationsofthemetalleadingtoeithershortoropencircuits.ThefailurerateduetoEMdependsonthecurrentdensityinthemetallinesandisusuallyexpressedasamediantime-to-failure(MTF).ThereisadeniteneedforCADtoolsthatpredictthesusceptibilityofagivendesigntoEMfailures.Asimulationtool,SPIDER[3],hasbeendevelopedtoestimatetheMTFforeachsectionofametalbuscorrespondingtoanyuser-selectedinterconnectsignal.Itrequirestheusertospecifycurrentsourcestoloadthemetalbusatspeciedcontactpoints.Usingthesecurrentsources,SPIDERextractsanequivalentresistancenetworktorepresentthebus,simulatesthenetworkusingSPICE[4]todeterminethecurrentdensityineachsection,andthenestimatestheMTFofeachsectionusingmodelsdevelopedin[5].Theuseris,however,leftwiththeproblemofspecifyingcurrentsources.Thiscanbeveryhardtodoforabigchip,especiallyforCMOScircuits,becausetheydrawcurrentonlyduringswitchingtransients.HencethereisaneedforaCADtoolthatderivesthesecurrents.WepresentanewtechniqueforsolvingthiscurrentestimationproblemforCMOScir-cuits.ThishasbeenimplementedintheprogramCREST(CuRrentESTimator)andhasproventobeveryeectivebothintermsofaccuracyandspeed.Wefocusourattentiononthepowerandgroundbusses,andderiveloadingcurrentsforthemtobeusedforMTFestimation.Thesebussesaretheusual,althoughnotonly,locationsofsevereEMfailures.Preliminaryresultsofthisworkshavebeenpresentedin[6,7].ItisimportanttounderstandexactlywhatinformationaboutthecurrentisneededforEManalysis.CMOScircuits,aspointedoutabove,drawcurrentonlyduringswitching,and,therefore,produceanon-dccurrentwaveform.Itiswellknown[5]that,inthepresence1 ofsuchwaveforms,theMTFduetoelectromigrationisdependentontheshapeofthewaveformandnotsimplyonitstime-average(iearea).Soasimpleaveragingapproachisunacceptable.Ontheotherhand,theMTFisthecombinedeectofalargenumberofcurrentwaveforms,correspondingtothevarietyoflogicalwaveformsthatcanbeappliedatthecircuitinputsduringtypicaloperation.Itwouldbeinsucient,therefore,touseastandardtimingsimulatortoderivethecurrentcorrespondingtoasinglesetoflogicalinputtransitions.Itisalsoobviousthatredoingasuchasimulationforeverypossibleinputtransitionisimpractical,sinceforacircuitwithninputs,thenumberofpossibletransitions2nattheinputsis2.CRESTovercomesthisproblembyderivinganexpectedcurrentwaveform;thisisawaveformwhosevalueatagiventimeistheweightedaverageofallpossiblecurrentvaluesatthattime,asshowninFig.1.Suchawaveformisagoodcompromisebetweenanunacceptabletime-averageandaninsucientsingle-transitionestimateofthecurrent,andprovidesanappropriatecurrentestimateforelectromigrationanalysis.Toderivethiswaveform,CRESTconsidersauser-speciedrange(orset)ofpossiblein-putvaluesand/ortransitionsandcalculatestheexpectedcurrentwaveformoverthisrange.Ratherthanenumeratingthesetofinputsandaveragingthecorrespondingcurrentresults(whichwouldbeimpractical),CRESTusesstatisticalinformationabouttheinputstodi-rectlyderivetherequiredexpectedcurrentwaveform.Theresultingmethodologyiswhatwecallaprobabilisticsimulationofthecircuit.Ingeneral,itcanbeslightlymoretimeconsumingthanstandardtimingsimulation,butitneedstobeappliedonlyonce,resultinginsignicantspeedup.Severalsimplifyingassumptionsand/orapproximationswillbemadeinthefollowingsectionstomaketheproblemcomputationallytractable.Wheneverpossible,wewillattempttojustifytheseassumptions.However,forlackofspace,thiswillnotalwaysbepossible,andthereaderwillbereferredtoappropriatereferences.Nevertheless,wewilloeravericationoftheoverallapproachonaglobalscale,bycomparingtheendresultofthesimulation(expectedwaveform)fromCRESTwiththatderivedusingSPICE.Therestofthispaperisorganizedasfollows.Thenextsectiongivesasystemoverviewtointroducesomebasicconceptsandtheoverallsimulationstrategy.Section3explainsthebasiccurrentestimationalgorithmaspartofthesimulationofstandardCMOSgates.2 Pass-transistorcircuitsarehandledinsection4.Section5discussessupergates,requiredtohandlesignaldependence.Section6presentsimplementationissuesandresults,andthelastsectiondrawssomeconclusionsandindicatesthedirectionoffutureresearch.Theappendixdiscussesabasicgraphreductionoperationthatwillbefrequentlyused.2SystemOverviewWehavedevelopedanewcurrentestimationapproachthatderivestheexpectedcurrentwaveformdirectlyfromprobabilisticinformationabouttheinputs.Asingleevent-drivensimulation,similarinsomeaspectstotimingsimulation,isthebasisofthetechnique.Be-foregoingintothedetails,weintroducesomebasicconceptsandprovidethetheoreticalgroundwork.Consideraset,eachelementofwhichrepresentsacombinationoflogicalwaveformsto1beappliedatthecircuitinputs;thisistherangeofinputsoverwhichtheexpectedcurrentwaveformistobederived.Ifcertainprobabilitiesareassignedtotheelementsof,thenwecanthinkofitasaprobabilityspace[8].Associatedwitheachelementofisanactualcurrentwaveformthatthecircuitwoulddrawifsubjectedtothatcombinationofinputs.Thisassociation(ormapping)denesastochasticprocessi(t)whosemeanE[i(t)]istheexpectedcurrentwaveformtobederived.Likewise,everyinputnodeNhasassociatedwithiitastochasticprocessx(t)thatembodiesthedierentpossiblelogicwaveformsallowedNiatN.Theseinturndeneotherprocessesattheinternalnodesofthecircuit.iThetechniquetobepresentedtakestheuser'sinputspecications(deningtheprocessesx(t))andusesthecircuittopology(whichdenesthemappingfromlogicalinputstoNicurrentwaveforms)toderivethecorrespondingprocessesatinternalnodes,decipherthestatisticsofi(t),andderiveitsmean.This,somewhatabstract,descriptionwillbemademoreconcretebelow.2.1ProbabilitywaveformsWebuildontheconceptofsignalprobabilities[9],whichhasrecentlybecomepopularinthetestingeld[10].Thiscanbesummarizedasfollows:aprobabilityvalueisassigned1Strictlyspeaking,ifthecircuitcontainsmemoryelements,thenitsinitialstatealsoaectsthestructureof.3 toeachinputnodetoindicatetheprobabilitythatitishigh.Thecircuittopologyisthenusedtopropagatethesevaluessothattheprobabilityatanyinternalnodeisderived.Theprobabilityspaceinthiscaseisasubsetofthesetdenedabove,becauseitcontainssteadystatevaluesonly,andnotwaveforms.Weextendthesignalprobabilitiesconceptbydeningtransitionprobabilities.Thetran-,sitionprobabilityofasignalNattimetistheprobabilityofalow-to-hightransitionfromt+(justbeforet)tot(justaftert),denotedP(t).GiventheseprobabilitiesattheinputsN;lhtheninternalnodetransitionprobabilitiescanbederivedfromthem.Usingtransitionprobabilitieswecancompactlydescribealargesetoflogicwaveforms.Forexample:inputNishighwithprobability.76attime0(P(0)=:76),switcheslow-N;hto-highwithprobability.5attime2ns(P(2ns)=:5),isthenhighwithprobability.35N;lhattime3ns(P(3ns)=:35),etc....SuchanalternatingsequenceofsignalprobabilitiesN;handtransitionprobabilitieswillbereferredtoasaprobabilitywaveform.AnexampleofaprobabilitywaveformandthefewlogicalwaveformsitrepresentsisshowninFig.2.CREST2usessuchawaveformasarepresentationofastochasticprocessatanode.Thesiteofatransitionprobabilityinthiswaveformwillalsobereferredtoasatransitionedge,shownasanarrowinFig.2.Atransitionedgeisanimportantpartofaprobabilitywaveformbecauseitmaycausecurrenttobedrawn.Transitionedgeswillalsobecalledprobabilisticevents,orsimplyevents.,AneventatanodeNattimetisdescribedbythethreeprobabilities:P(t),P(t),N;hN;lh+andP(t).ItiseasytoseethattheseareenoughtodescribethestatisticsoftheeventN;hsinceotherprobabilitiescanbederivedfromthem.Forinstance,theprobabilityofahigh-+,to-lowtransitioncanbeeasilyderivedusingtheidentityP(t),P(t)=P(t),P(t),hhlhhlwhichisobtainedfromsimpleprobabilitytheory.2.2SimulationalgorithmCRESTisaprobabilisticsimulatorsinceitoperatesonprobabilistic,ratherthanlogical,signals.Thesimulationalgorithmitself,however,isdeterministic.Theuserspeciesproba-2This,infact,isanincompleterepresentation,butissucientlyaccurateforourpurposes.Itwouldbeprohibitivelyexpensivetomaintainacompleterepresentation.4 bilitywaveformsattheprimaryinputsofthecircuit,whicharepropagatedintothecircuittoderivetheexpectedcurrentwaveform.Thewaveformsspeciedatthecircuitinputsconstitutetheprimarymeansfortheusertoin uencethesimulation.Theyallowonetostudythereliabilityofthecircuitundertypical"operatingconditions.Asdescribedabove,everyprobabilitywaveformconsistsofasequenceoftransitionedges,orevents,taggedwithsignalandtransitionprobabilities.Iftheseprobabilitiesaresetto0sand1s,thenthewaveformbecomesasimplelogicwaveform.Thus,ifenoughisknownabouttheactivityatthecircuitinputs,theusermaynetunethesimulationtothepointwherelogicalwaveformsarespeciedatsomeinputs(say,clockinputs).Otherwise,iflittleisknownabouttheinputs,thenonecanallowalargevarietyofpossiblesignalsbyspecifyingappropriateprobabilitywaveforms.Toprepareasetofprobabilitywaveforminputs,thereareatleasttwooptions.Ifoneiscomfortablewiththeprobabilitywaveformconcept,thentheseinputsmaybesimplyenteredassequencesofrealnumbersbetween0and1.Otherwise,weassumethattheuserhasavailablearepresentativesetoflogicalinputwaveformsfrompreviouslogic,timing,orfaultsimulationrunsonhisdesign.Thecorrespondingsetofprobabilitywaveformscanthenbeobtainedasfollows.Foragiveninputnode,considerallthelogicalwaveformsthatitmayexperience.Then,foreverytimepoint,taketheaverageofthevaluesinallthesewaveforms,consideringhightobe1andlowtobe0.Whenthesignalisnotchanging,thevaluethusobtainedistherequiredprobabilitywaveformvalueatthattime.Whenthesignalischanging,fromlowtohigh,thenthefractionofthelogicwaveformsinwhichitmakesthattransitionatthattimegivestherequiredtransitionprobabilityinitsprobabilitywaveform.Giventheinputprobabilitywaveforms,anevent-drivensimulationapproach,similartowhatiscommonlyemployedbylogicortimingsimulators,isusedtopropagatethemthroughoutthecircuit.Thecircuitisdividedintogates.Whenaprobabilisticeventoccursontheinputtoagate,theexpectedcurrentpulsecausedbytheeventisestimated,andtheappropriateprobabilisticeventiscreatedontheoutputnodeofthegate.Theexpectedcurrentpulsesfromindividualgatesaresummedtocreatetheexpectedcurrentwaveformdrawnbythecircuit.Theprogramoperatesonatransistordescriptionofthecircuit,whichitpartitionsintoprimitivegatesoftwomajortypes:standardCMOSgatesandpasstransistor5 gates.Currentpulseestimationandprobabilisticeventpropagationforeachofthesegatetypeswillbefurtherdiscussedinsections3and4below,respectively.2.3SignaldependenceAmajorproblemwithanytooldealingwithanumberofstatisticalquantitiesiskeepingtrackof,andmodeling,thecorrelationordependenceamongthem,CRESTisnoexception.DependencebetweensignalsinCRESTisoftwotypes.Therstisadependenceexistingbetweenthetwovaluesatthesamenodeattwodistincttimepoints,thiswillbereferredtoastemporaldependence.Thesecondisthedependenceexistingbetweentwosignalsiftheirnodesdependonthesamefanoutsteminthecircuit,thiswillbereferredtoasspatialdependence.Afeedbacklopinvolvesbothspatialandtemporaldependencies;ingeneraltwosignalsmaybedependentduetoeitherorbothofthesetypes.CRESTaccountsfortemporaldependenceinalimitedsense.Thedependencebetweentwosignalvaluesseparatedbyasingletransitionedgeisaccountedfor-this,infact,isthereasontransitionprobabilitiesareintroduced.Theprogram,however,doesnotkeeptrackofthedependencebetweensignalvaluesseparatedbymorethanonetransitionedge.Itturnsoutthatthisapproachissucientlyaccurateforourpurposesbecausetheprobabilitiesat(andonbothsidesof)atransitionedgeareenoughtoderivethecurrentpulsecorrespondingtoit.Toaccuratelykeeptrackoftemporaldependencebetweenthesignalsatanytwotimepointsinawaveformwouldbeequivalenttoacompleterepresentationofastochasticprocess(seefootnote2above)andwouldbeprohibitivelyexpensive.Spatialdependenceishandledusingtheconceptofasupergate[10],asexplainedinsec-tion5below.Itisimportanttomakethepointnow,however,thatthisreducestosimulatinggateswhoseinputsareindependent.Thedescriptionsofthesimulationofprimitivegatesinthefollowingsectionswillthereforeassumethatagate'sinputsareindependent.2.4GraphreductionThissectionbrie yintroducesagraphreductionprocedurethatiscentraltothesimulationalgorithmstobepresented,andwhichwillbeusedfrequentlybelow.Theappendixisdevotedtoapreciseformulationanddescriptionofthisapproach.6 Simplystated,theneedwillfrequentlyarisetoderivetheprobabilitythatameshoftransistors,joiningtwospeciedpoints,providesaconductingpathbetweenthem.AnexampleisgiveninFig.3,wheretheppartofaCMOScomplexgateisshown.Typically,theprobabilitiesatthegatenodesofthetransistorsareknown,andtheprobabilityatthegateoutputisrequired.Thegeneralmethodologywillbetoconsideragraphthatisidenticaltothetransistormesh(Fig.3)inwhichtheedgesarelabelledwiththeprobabilitiesofthegatenodes.Thisgraphisthenreducedtoasingleedgewhoselabel(s)providetherequiredprobabilities.InFig.3,theprobabilitythattheoutputishighissimplytheprobabilitythattheedgeisconducting.Actually,theedgesarelabelledbybothsignalandtransitionprobabilities,aswellasbytheexpectedconductanceofthetransistors.Afterthegraphisreduced,theresultantlabelsondeterminetheeventattheoutput,anditsexpectedconductanceisusedtoderivetheexpectedcurrent.Thereaderisreferredtotheappendixfordetailsofthisreduction.3StandardGateSimulationThetermstandardgatewillbeusedtorefertoaCMOSfullycomplementarygate,asshowninFig4.Thep-blockorp-part(n-blockorn-part)ofagatewillbeusedtorefertothep(n)channeltransistormeshbetweenitsoutputnodeandthepowersupply(ground).Agatewillbeassumedtohavespatiallyindependentinputs.Thegeneralcaseisproperlyhandledusingtheconceptofasupergate,asdescribedinsection2above,withtheindependent-inputs-gate-solverusedasasubroutine.Simulatingagateistheprocedureofanalyzingagatethathascertaineventsatitsinputstoderivethecorrespondingoutputeventandexpectedcurrentpulse.Giventheeventsattheinputsofagateatacertaintimet,itsoutputeventcanbeeasilyderivedasfollows.Considertheppartofthegateandbuildagraphthatrepresentsitusingthetransistorgateprobabilitiestolabelthegraphedgeswiththeprobabilitiesthateachedgeison,"wason,"andtransitionsfromotoon."ThegraphreductionproceduredescribedintheappendixisthenusedtoreducethegraphtoasingleedgebetweenVandddtheoutputnode.Itisobviousthattheprobabilitiesofthesingleedgeremainingatthe7 endofthereductiongivetherequiredoutputevent.Thetimeofoccurrenceofthiseventwillbederivedattheendofthissection.Thecurrentestimationprocedureateachgatewillnowbediscussed.Theexpectedgate4+currentpulsewillbemodeledbyatriangularpulsethatstartswithapeakofE[I]=E[i(t)]attimetanddecayslinearlytozeroattimet+.TherestofthissectiondescribesthederivationofE[I]and.Wewillfocusonthechargingcurrentcomponentandleaveoutthedirectcomponentwhichmaybedrawnthroughapathofpandnchanneltransistorsduringthetransition.ThispolicyhasbeenadoptedbasedonVeendrick's[11]workwhichsuggeststhatifthegateiswelldesignedthenthedirectcurrentcomponentmaybeneglected.ConsiderthegenericCMOSgatestructureshowninFig.4.Thegureshowsthep-transistorblock,then-transistorblock,andtheoutputnodecapacitancesplitintotwolumpedcapacitorsCtoVandCtoV.Similarly,eachinternalnodenhastwoca-pddnssipacitancesCandC.Thevaluesofthesecapacitancesarederivedfromthecircuitde-inipscriptionandthetransistormodelparameters.Onalow-to-hightransition,thecurrents owingthroughCandCattheoutputnodeareiandi,respectively,asshowninnpp1p2thegure.Thecorrespondingiandiforahigh-to-lowtransitionarealsoshown.Then1n2currentsiandiaredischargingcurrentsthatredistributelocally,andweareinterestedp2n2ini=i+i.Ofcoursethesecurrentsareassociatedwiththeoutputnodeonly,andthep1n1totalgatecurrentiwillbelargerthani.However,theoutputcurrentwillplayacentraltotroleinthederivation.Leti=i+iandi=i+i.It'seasytoverifythati=iC=(C+C),pp1p2nn1n2p1pnpnandi=iC=(C+C).Therefore:n1nppnCCpnE[i(t)]=E[i(t)]+E[i(t)](3:1)pnC+CC+CpnpnAndinparticular,thevalueatthepeakis:CCpnE[I]=E[I]+E[I](3:2)pnC+CC+CpnpnThevaluesofE[I]andE[I]arederivedasfollows.Fori,considertheppartofthepnpgate,andleteverytransistorTberepresentedbyaswitchofon-conductanceg,wherekon;k8 gis(themaximumconductance)givenby:on;kk2g=(V,V)(1+V)(3:3)on;kddTdd2VddwhereVisthemagnitudeofthetransistorthresholdvoltage,isitstransconductance,Tkandisthechannellengthmodulationfactor.Thisdenitionofgisusedbecauseweon;kareinterestedinthepeakcurrentdrawn,whichoccursduringsaturation.Thevalueofgon;kisderivedfromthetransistormodelparametersgivenbytheuser.NowletG(t)betherandomconductancebetweentheoutputnodeandV.Gisapddpfunctionoftheindividualtransistors'randomconductancesg,wheregis0ifthetransistorkk+isoandgifitison.Ifaneventoccursatthegateattimet,thenthevalueofE[G(t)]on;kp,andthepreviousstateoftheoutputnode,V(t),willdetermineE[I].Formally,wehaveop,+E[I]=E[(V,V(t))G(t)],whichbecomes:pddop+,,E[I]=VE[G(t)jG(t)=0]P(G(t)=0)(3:4)pddpppwhereP(A)istheprobabilityoftheeventA,andE[AjB]denotestheconditionalexpected,,valueofAgivenB.TheformulaiscorrectbecauseifG(t)=0(1)thenV(t)=0(V).poddSimilarlyforthenpartofthegate,weget:+,,E[I]=VE[G(t)jG(t)=0]P(G(t)=0)(3:5)nddnnn+,+,IfthegateinputsattareindependentoftheirvaluesattthenE[G(t)jG(t)=pp+0]=E[G(t)]andtheproblemwouldbesimplied.InthiscasethevalueofE[G](orppE[G])maybederivedfromthegraphbyconsideringagraphrepresentationofthep(n)nblockofthegateusingtheconductancesE[g]ofthetransistorsandtheirgatenodeprob-kabilitiesandperformingagraphreduction.Howeverthisisnottrueingeneralandthe+,dependencebetweenG(t)andG(t)shouldbetakenintoaccount.+,TondtheconditionalexpectedvalueofG,E[G(t)jG(t)=0],weperformppp+,+thegraphreductionusingE[g(t)jG(t)=0],insteadofE[g(t)],foreverytransistor;kpklikewiseforG.IfxisthegatenodeoftransistorTinthep-part,thenitcanbeshown[12]nkkthat:P(t)x;llk+,E[g(t)jG(t)=0]=g+kpon;k,P(t)x;lk9 ,,P(G(t)=0jx(t)6=0)pk,+P(t),P(t)P(t)(3:6)x;lhx;lx;hkkk,,P(G(t)=0)P(x(t)=0)pkand,ifTisinthenpart,then:kP(t)x;hhk+,E[g(t)jG(t)=0]=g+knon;k,P(t)x;hk,,P(G(t)=0jx(t)=0)nk,+P(t),P(t)P(t)(3:7)x;lhx;lx;hkkk,,P(G(t)=0)P(x(t)6=0)nkTherefore,ittakesanadditionalgraphreductionforeverygateinputtocomputethevalues,,,,P(G(t)=0jx(t)6=0)andP(G(t)=0jx(t)=0).pknk+,ThederivationofE[G(t)jG(t)=0]outlinedabovemakestheimplicitassumption,thatwhentheprobabilityspaceisrestrictedbytheconditionG(t)=0theindependenceofthegateinputsispreserved.Thismaynotalwaysbetrue,andtheimplementationinCRESThasaprotectionmeasuretosafeguardagainstthisconsistingofasimpleupper+,bound[12]onE[G(t)jG(t)=0].HavingfoundE[I]fortheoutputnode,theexpectedvalueofchargedeliveredto(orfrom)theoutputnodecapacitorsiseasilyfoundasfollows:E[q]=VCP(t)+VCP(t)(3:8)ddno;lhddpo;hlwhereoistheoutputnode.Wenowmaketheapproximationthatthetimeconstantforchargingordischargingtheoutputnodeisthelargestoftheinternalgatenodes.Conse-quently,thetimespanoftheoutputnodecurrentrepresentsthetimespanofthetotalgatecurrent.Bythetriangularpulseapproximation:E[q]=2(3:9)E[I]Next,theexpectedvalueofthechargedeliveredbythetotalgatechargingcurrent,E[q]isderivedusingthecapacitancesateachinternalnodejasfollows:totXXE[q]VCP+VCP(3:10)totddjnj;lhddjpj;hlj2pblockj2nblockStrictlyspeakingtheprobabilitiesPandParehardtond;theyareinfactNP,hardj;lhj;hltondingeneral,basedon[13].Wehavethereforeoptedtouseanupperboundoftheseprobabilitiestoreplacethemintheequation.AnupperboundofP(P),foranodeinj;lhj;hl10 thep(n)block,istheprobabilitythattheconductionstatebetweenjandV(V)goesddssfromo-to-on.ThisisfoundbyagraphreductionthatrepeatstheworkdonetondPo;lhfortheoutputnodeoforeveryinternalnodej.Finally,thepeaktotalcurrentisfoundas:2E[q]E[q]tottotE[I]==E[I](3:11)totE[q]TherelationshipbetweenthesequantitiesisdepictedinFig.5.Havingderivedtheexpectedgatecurrentpulse,thetimeoftheneweventattheoutputofthisgateneedstobederived,asfollows.IfoneconsidersaresistorRchargingacapacitorCfromapowersupplyV,thenthecurrentandvoltageatthecapacitorbothreachtheirhalf-pointattime:693RC.Ifweassumethattheindividualcurrentpulsesi(t)areexponentiallydecaying,ratherthanlinear,thentheswitchingtimeattheoutput,t,iss0:693(C+C)=Gforalow-to-hightransition,and0:693(C+C)=Gforahigh-to-lowpnppnntransition.Thistis,again,arandomvariable,andoneisinterestedinE[tjVtransitions].ssoKnowingthatthedurationofi(ori)determinesthegatedelay,andthatthesecurrentspndeliverchargetobothCandC,thenifqandqarethechargesdelivered,wehave:pnpnE[q]=V(C+C)P;and(3:12)pddpno;lhE[q]=V(C+C)P(3:13)nddpno;hlThedurationofthetwopulsesisderivedasbefore,as:E[q]E[q]pn=2;and=2(3:14)pnE[I]E[I]pnHavingfoundthesevalues,thetimedelaycanbeshown[12]tobe:P+Ppo;lhno;hlE[tjVtransitions]=0:35(3:15)soP+Po;lho;hlItisimportanttonotethatandareindependentoftheparticularpartitioningofpn(C+C),whichmakesthetimingestimatereliable.pn4Pass-TransistorCircuitsPass-transistorspresentaproblembecausetheyactasmemoryelements.Theoutputofapass-transistornetworkdependsonmorethanjustitsinputs,thepreviousvaluesatits11 outputandinternalnodesarealsoimportant.Itisalsonolongertruethattheprobabilitiesofthepath(s)fromtheoutputtoVorVcompletelydenetheoutputeventbecauseddsstheoutputmaybedisconnectedfromboth.Currentdrawnthroughpass-transistorsisarelativelysmallfractionoftheoverallcurrentdissipatedinaCMOScircuitandwillbeignored.However,eventsmustbepropagatedcorrectlythroughthemsothatthegatesdownstreamarecorrectlysimulated.Toreducetheircomplexity,webreakuppass-transistornetworksintotwotypesofprim-itivegates:stagesandwires,asshowninFig.6.AconcreteexampleofthisdecompositionisgiveninFig.7.Stagesrepresentconductingpathsthatconnecttwonodes;whilewiresareusedtotietogethertheoutputsoftwoormorestages.Thesegatescanbeusedtobuildcomplicatedpasstransistornetworks.Thisdecompositioninvolvestwosimplifyingassumptions:transistorsareunidirectional,andmemorystatesaresignicantonlyattheboundariesofstagesandwires.Thedirectionofeachgatemustbecarefullyassigned,andweuseseverallevelsofalgorithms,includingsomerulesfrom[14].Asintraditionallogicsimulation,thetwologicvalues0and1arenotenoughtomodelpass-transistorcircuits,andwaysofrepresentingweak0and1signalsmustbeintroduced.Nodesinapass-transistorsectionofacircuitcanhavefourvalidstates:conductingpathtoV(hightiedorht),conductingpathtoV(lowtiedorlt),chargedwithnoconductingddsspaths(high oatingorhf),anddischargedwithnoconductingpaths(low oatingorlf).Anadditionalstateisintroduced:nopathtoeitherVorV( oatingorf).Althoughddssthereisredundantinformation,veprobabilitiesareusedtofullydenethestatesofallnodesinapasstransistorstructure:P,P,P,P,andP.htlthflffCorrespondingly,thesetofprobabilitiesneededtodescribeaneventisalsoenlarged,theseeventswillbereferredtoasexpandedevents.Expandedeventsmustcontaintheprobabilitythatthenodewashightied(P),lowtied(P),andhigh(P)beforeandafterhtlththetransition.Additionally,transitionprobabilitiesfromlowtohigh(P),lowtiedtohighlhtied(P),lowtiedto oating(P), oatingtohightied(P),and oatingtolt!htlt!ff!ht oating(P)areneededtopropagateprobabilitywaveformsthroughthepass-transistors.f!f12 4.1StagesimulationThesimulationofastageinvolvesagraphreductionbywhichthestageisreducedtoasingleedgebetweenitsinputandoutput.Thisprocedure(seetheappendix)providesthe+,probabilitiesthatthisedgeison,P(t),wason,P(t),andtransitionsfromotoon,;1;1P(t).Otherprobabilities,suchasontoo,P(t),ontoon,P(t),andotoo,;01;10;11P(t),canbederivedfromsimpleprobabilitytheory.Ifthestagehasinputxandoutput;00ythenthefollowingformulascanbederived[12]:P(t)=P(t)P(t)(4:1)y;ht;1x;htP(t)=P(t)P(t)(4:2)y;lt;1x;ltP(t)=P(t)P(t)(4:3)y;lt!ht;11x;lt!ht+P(t)=P(t)P(t)+P(t)P(t)(4:4)y;f!ht;01x;ht;11x;f!ht,P(t)=P(t)P(t)+P(t)P(t)(4:5)y;lt!f;10x;lt;11x;lt!f+P(t)=P(t)+P(t)P(t)y;f!f;00;01x;f,+P(t)P(t)+P(t)P(t)(4:6);10x;f;11x;f!fNoticethattheseformulas,whiledeterminingmostofthestageoutputprobabilities,donotnalizeitssimulationbecausetheprobabilitiesofthehigh oatingorlow oatingstatesarenotyetavailable.Thisistobeexpectedbecausethestateofthe oatingoutputofastagecanbeaectedbyotherstagestiedtothesamewiregate.Thesimulationofawire,tobediscussednext,usesthequantitiesderivedaboveforthestage(s)outputstonalizetheirsimulationandobtainthewireoutputprobabilities.4.2WiresimulationIfawirehasmorethantwoinputs,onecanthinkofitasacascadeofseveralwireswithtwoinputseach.Consequently,itissucienttostudythesimulationofawirewithonlytwoinputsxandy,andanoutputz.Sinceawireisbasicallyawired-orconguration,voltagedivisionmayarisewhenitsinputsarex=ltandy=ht(orviceversa).Inthiscasewemaketheassumptionthattheoutputisz=lt;thisisbasedontheweakpull-uptoV"congurationwhichiscommonlyusedinCMOSandnMOScircuits.Thisdd13 assumptionisimplicitinthederivationofthefollowingwiresimulationformulaswhose(tedious)derivation[12]willnotbeincludedhere:P=PP+PP+PP(4:7)z;htx;hty;fy;htx;fx;hty;htP=P+P,PP(4:8)z;ltx;lty;ltx;lty;lt+P(t)=P(t)[P(t)+P(t)]z;lt!htx;hty;lt!hty;lt!f++P(t)[P(t)+P(t)]y;htx;lt!htx;lt!f+++P(t)P(t)+P(t)P(t)x;fy;lt!hty;fx;lt!ht,P(t)P(t),P(t)P(t)x;lt!hty;lt!fy;lt!htx;lt!f,P(t)P(t)(4:9)x;lt!hty;lt!htP=PP+PP+PP(4:10)z;f!htx;f!hty;f!fy;f!htx;f!fx;f!hty;f!ht++P(t)=P(t)P(t)+P(t)P(t)z;lt!fx;fy;lt!fy;fx;lt!f,P(t)P(t)(4:11)x;lt!fy;lt!fP=PP(4:12)z;f!fx;f!fy;f!fWhenalltheinputsofawirehavebeenconsidered,itssimulationisnalizedusingthefollowingtwoformulas[12]:(,P(t);ifP(t)=0;z;lt!fz;f+,P(t)(4:13)P(t)z;lfz;lfP(t)+P(t);otherwise.,z;f!fz;lt!fP(t)z;f(,0;ifP(t)=0;z;f,P(t)(4:14)P(t)z;lf!htz;lfP(t);otherwise.,z;f!htP(t)z;fAminorindependenceassumptionmustbemadeinthederivationoftheseformulas;thisisnecessarybecauseofthelimitedsenseinwhichtemporaldependenceisaccountedfor(asmentionedinsub-section2.3above).Havingderivedtheprobabilitiesofthewire'soutputevent,theonlyremainingunknownisthetimeofthatevent.TheapproachusedbyHorowitz[15]issuitedtoourprobabilisticmodels.Byusingtheexpectedconductanceofastagederivedinthegraphreductionstep,andtheinternalcapacitancesofstages,atimeconstantcanbederivedforthepass-transistornetwork.Thisisusedtoderivethetimeoftheoutputevent.14 5SupergatesCRESTassumesthattheprimarycircuitinputsareindependent.Thesingle-gatecurrentestimationalgorithmsdescribedaboverequirethattheprobabilitywaveforms,attheinputsofeachgate,beindependent.Thisconditionisviolatedifthecircuitcontainsreconvergentfanoutorfeedback.Toovercomethisproblem,weborrowtheconceptofsupergatesfrom[10];asupergateissimplyasubsetofthecircuitwithindependentinputs,anexampleisshowninFig.8.Supergateinputnodesthatarereconvergentfanoutstems,orthataectinter-nalreconvergentfanoutstemsofthesupergate,arecalledreconvergentfanoutinputnodes,abbreviatedrnodes.NodesAandBinFig.8arernodesofthatsupergate.Iflogic(notprobability)waveformsareassignedtornodes,thenthesignalsatallinter-nalsupergatenodesbecomeindependentandthesupergatecanbeeasilysimulated.Giventheprobabilisticeventsattherinputsofasupergate,supposethesetofallpossiblelogicaltransitionsembodiedbytheseeventsisgenerated(Fig.9),andthesupergatesimulatedforeachofthem.Ifthecurrentresultsaresummedup,weightedbytheprobabilityofeachcase,therequiredsupergatecurrentswouldresult.Basedontheseobservations,thesimulationofasupergateinCRESTiscarriedoutbymaintainingasetofdierentsimulationsub-processes,eachrepresentingtheresultofaparticularsequenceoflogicaleventsatthesupergate'srnodes.Everysub-processhasacertainprobability,namelytheprobabilitythatthesupergatehasthatstateatthattime.Whenaneweventarrivesatanrnodeitisappliedtoallexistingsub-processes,someofwhichwillcausethecreationofnewsub-processes.Whentwosub-processesareperformingidenticalsimulations,theyaremergedtoproduceasinglenewsub-processwhoseprobabilityisthesumoftheirprobabilities.Thisapproach,whileacceptableforsmallsupergates,istooexpensiveforlargerones.Inthesecases,CRESTusestwoheuristicparameterstoreducetheperformancepenaltieswhilemaintainingacceptableaccuracy:(1):Limitsupergatesizetoauser-speciedsizethreshold,.Bylimitingsupergatesize,ssthisindirectlylimitsthenumberofrnodesand,therefore,thenumberofsimulationsub-processes.15 (2):Terminateasimulationsub-processifitsprobabilitybecomeslessthanauser-pspeciedprobabilitythreshold,.Thiseliminatessub-processesthatarelikelytocon-ptributeverylittletothecurrentwaveform.Theeectivenessoftheseheuristicswillbediscussedinthenextsection.Theformationofsupergatesisdoneasapreprocessingstep,duringtheinitialparti-tioningphaseoftheprogram.Thedetailsofthatprocessaretediousandnotinterestingenoughtowarrantinclusioninthispaper.Verybrie y,ifthecircuitiscombinational,thentheprocessinvolvesaforwardandabackwardsweeptodiscoverthenodedependenciesandbuildthesupergates.Inacircuitwithfeedback,it'seasytoseethateveryfeedbackloopis,strictlyspeaking,asinglesupergate.Thereforeastandardstrongly-connected-componentsalgorithmisrstusedtogroupfeedbackloopsintotemporarysupergates,afterwhichthecircuitappearscombinational,andsupergatescanbeeasilybuilt.Sincelargefeedbackloopscanleadtohugesupergates,wehaveusedheuristicstobreakuplargefeedbackblocksintosmalleronestomaintainareasonableexecutiontime.6ImplementationandResultsAsmentionedabove,theprobabilisticsimulationapproachhasbeenimplementedinapro-gramcalledCREST(CuRrentESTimationprogram).Theprogramisabout15000lines,writteninC,andhasbeenrunonavarietyofcircuitsandcomputersystems.ItacceptsaSPICEcircuitdescriptionle,andrequiresanotherlethatspeciestheprobabilitywave-formsattheprimarycircuitinputs.Excellentaccuracyandspeedhavebeenachievedonrealcircuits.Toassesstheaccuracyoftheresults,itisimportanttomakeafaircomparisonwithanexpectedcurrentwaveformderivedusingavalidsimulationtool.Todoso,wehavegeneratedtheexpectedcurrentwaveformforavarietyofexamplesbyrunningSPICEoneverysetofinputvoltagesignalsallowedbytheprobabilityvectors,weightingeachresultingcurrentwaveformbytheprobabilitythattheinputsproducingitwouldoccur,andsummingtheweightedwaveformstoproducetherequiredresult.SincethenumberofrequiredSPICEsimulationrunsgrowsexponentiallywiththenumberofcircuitinputs,thecomparisonstobepresentedbelowwillnecessarilybelimitedtomediumsizedcircuits.Thereisnoreason16 tosuspect,however,thattheaccuracyobservedonthesecircuitswilldeteriorateonlargerones.Figures10and11showtheresultsforasinglecomplexgateandaninverterchainrespectively.ImportantfeaturesofthesetwoguresaretheaccuracyofthecurrentwaveforminFig.10andthegoodtimingperformanceinFig.11.Fig.12showsthecurrentpulseforatypicalpass-transistorcircuit.InFig.13weshowtheresultforalargercircuit-a4-bitALUwith154MOSFETSinvolvingalargenumberofpass-transistorgatesandweakpull-uptransistors.TheALUwasrunforlogical(ratherthanprobabilistic)inputsbecauseitwouldtaketoolongtorunSPICEforallitspossibleinputstoallowacomparisonwithaprobabilisticCRESTrun.CRESTsimulationtimesfortheseandothercircuitsarecomparedwithSPICEinTa-ble1.SPICEwaschosenforthesecomparisonsbecauseitisagenerallyavailabletool,andassuchprovidesacommonframeofreference.SinceSPICEisknowntobeslowonlargecircuits,wealsooerabsolutemeasuresoftimingintheformofCPUseconds.ThetableillustratesthedramaticgainsavailablefromCREST'sprobabilisticanalysiswhenanexpectedwaveformisneeded.Infact,asthenumberofcircuitinputsincreases,thespeedupofCRESTcomparedtoanapproachbasedonlogicalinputsincreasesexponentiallysince2nthesizeoftheinputsspaceincreasesas2.Forexample,a(heuristic)CRESTrunonthe1441839-transistor34-bitALU,whichtakes13secondsonaCONVEX220,isequivalentto2SPICEruns.Thegainspossibleforlogicalinputsareillustratedinthelasttwoexamples,wherelogicalwaveformswereusedsincethecircuitsweretoolargetoexamineforallinputsinSPICE.Wenallypresenttheresultstodemonstratetheeectivenessofthesupergatesimulationheuristics.Threecircuitswereusedforthesesimulations:a2-bitadder(Fig.14),a4-bitadder(Fig.15),anda4-bitmultiplier(Fig.16).ThewaveformsarecomparedintheguresindicatedandthetimingandspeedupresultsofthedierentrunsareshowninTable2.TheexactCRESTsimulationshowninFig.14awas3000timesfasterthanSPICE.Fig.14bshowsaheuristicCRESTrunthatisoverfourtimesfasterwithcomparablecurrentresults.Fig.15showstheresultsofthreedierentheuristicrunsinCRESTcomparedtoafull-accuracyrun.Therstrunmerelyeliminatedextremelyimprobablesupergateprocessesandobtained11Xspeedupwithvirtuallynoaccuracyloss.Thesecondruncombinedboth17 Table1.ExecutiontimecomparisonbetweenCRESTandSPICE.TimeisinCPUsecondsonaSEQUENT.Sizereferstothenumberoftran-sistors.CircuitSizeCRESTSPICESpeedupDecode1201.1642584XDecode2281.4989706XDecode3361.91588836XInvt10201.0221221XInvt40803.32094635XBridge100.82323729000XPass180.8282352XPass291.115051370X4-bitALU15410.93535324X34-bitALU1839145.086152594Xheuristicsandachievedexcellentaccuracywith31Xspeedup.Thenalruncompletelyeliminatedsupergatesandshowsacceptableaccuracywitha59Xspeedup.Fig.16comparesafairlytightheuristicrunandarelaxedheuristicrunfora4-bitparallelmultiplier.Inthetightrun,supergatesareallowedtogrowuptoninegatesandsupergatesimulationprocessesareignoredonlyiftheirprobabilityislessthan.0005.Intherelaxedrun,thesupergatesizelimitissettoonegate,ie osupergates."Therelaxedheuristicran8timesfasterwithcomparableresults.Ingeneral,theheuristicsyieldedcomparableresultswithexcellentimprovementsinspeed.Thiswasparticularlytrueforthemostcomplexcircuit,the4-bitmultiplier.Inallexamplestested,theresultswereexcellent.Peakcurrentswerewithin20%,averagecurrentswerewithin10%,and,asclearlyshowninFig.11,timingestimateswerewithin10%ofSPICE.7SummaryandConclusionsWehavediscussedtheelectromigrationproblemandstressedtheneedforanexpectedcurrentwaveformforMTFestimation.Wehavepresentedsuchatechnique,basedonanewso-calledprobabilisticsimulationapproachwhichhasbeenimplementedintheprogram18 Table2.Performanceofthesupergateheuristics.TimeisinCPUsecondsonaVAX-11/780.Sizereferstothenumberoftransistors.CircuitSizeTimesp2-bitripple541011.4adder102.6(4.4X)4-bitripple20010332.2adder1.0129.0(11.4X)3.110.6(31.3X)105.6(59.3X)4-bit6489.00052403.1multiplier10297.5(8.1X)CREST.Thecombinedeectsofavarietyofinputpatterns,eachofwhichwouldrequireseparateSPICEsimulations,canbederivedwithasinglesimulationatnomoreexpensethanthesimulationforasinglevector.Assuch,ourapproachispattern-independentandprovidesadramaticspeed-up(rangingfrom200Xto29000X)overtheconventionalapproachusingSPICE.Furthermorethespeedupincreasesexponentiallywiththenumberofcircuitinputsbecauseasingleprobabilisticruncoversanexponentiallyincreasingnumberoflogicalruns.ThewaveformsproducedagreewellwithresultsobtainedfromSPICE:peakcurrentsarewithin20%,averagecurrentsarewithin10%,andtimingestimatesarewithin10%.CRESTcanhandlegeneralCMOScircuits,allowingpasstransistors,reconvergentfanoutandfeedback.Heuristicshavebeenpresentedthathelpmaintainspeedinthepresenceofreconvergentfanout,withoutsignicantlyaectingaccuracy.TheresultsofseveralCRESTrunsonrealcircuitshavebeenpresented.Thesuccessoftheheuristicsleadstotheconclusionthatreconvergentfanoutpathsandthecorrespondingsignaldependencebecomelessimportantforlargercircuits(eg.Fig.16).Thisissupportedbytheintuitiveobservationthattheeectofareconvergentfanoutnodebecomesnegligibleifthereconvergentpathscontainalargenumberofgates.TheexpectedcurrentwaveformderivedbyCRESThasanobviousimmediateuseinanunrelatedapplication:thederivationoftheexpectedinstantaneouspowerdissipation,aswellastheoverallpowerdissipationofthecircuit.Apartfromthisobviousapplication,19 futureworkonCRESTwilladdressthesimulationofcircuitswithtrulybidirectionalpass-transistors.Otherextensionsoftheapproachwillalsobeaimedatestimatingthevoltagedroponthepowerandgroundbusses.Thismayrequirederivingmorestatisticsofthecurrentwaveform,suchasthewaveformvariance.Appendix:GraphReductionThisappendixdescribesagraphreductionprocedurethatiscentraltothesimulationalgorithmstobepresented.LetG=(V;E)beanundirectedconnectedgraphwithnoselfloops,possiblywithparalleledges,inwhichtwoarbitraryverticesu;v2Varespecied.+Attimet,eachedgee2EislabeledwiththreeprobabilityvaluesP(t),whichisthee;1,probabilitythattheedgeison,P(t),theprobabilitythattheedgewason,andP(t),e;1e;01theprobabilitythatittransitionsfromotoon.Furthermore,eachedgehasassociatedwithitarandomconductancevalueg(e)whichiseither0,iftheedgeiso,org(e),ifitison.onTheequivalentconductanceofanetworkofedgesisdenedtobethatofanidenticalresistivenetworkwiththesameconductances.Theeventsison,"wason",andtransitionsfromotoon",aswellastherandomconductances,ofanytwodistinctedgeseandeare12assumedtobeindependent.Letbearandomvariablethatis1ifthereexistsatleastonepathofon-edgesinG+,betweenuandv,and0otherwise.TheprobabilitiesP(t),P(t),andP(t)are;1;1;01+denedasabove.Finally,letGbetherandomconductancebetweenuandvatt.WeG+,areinterestedinndingthevaluesofP(t),P(t),P(t),andE[G].;1;1;01G+FindingP(t),whichisperhapsthesimplesttoderive,isknowntobeNP,hard,;1see[16]page211.Thealgorithmstobegivenwill,therefore,includesomeapproximationstomaintainareasonableexecutiontime.Thegeneralmethodologywillbetoreducethesizeofthegraphbyremovingedgesand/orvertices,sothattheprobabilitiesofandE[G]Gremaininvariant,untilthegraphreducestoasingleedgebetweenuandv,asshownin+,Fig.3.Thelabelsonthisedge,P(t),P(t),P(t),andE[g()]aretherequired;1;1;01answers.Hencethetermgraphreduction."Wewillrstdescribesolutionsforarestrictedclassofgraphs,namelyforseries-parallelgraphs(see[17],pp.197{199).Forsuchagraph,onecanaccuratelyderivetheprobabilities20 ofbymakingparallelandseriescombinationsofedgesuntilasingleedgeremains.Ife(e)istheparallel(series)combinationofedgeseande,thenthefollowingformulasps12apply:P(t)=P(t)+P(t),P(t)P(t)(A:1)e;1e;1e;1e;1e;1p1212P(t)=P(t)P(t)(A:2)e;1e;1e;1s12,,P(t)=P(t)P(t)+P(t)P(t),P(t)P(t)(A:3)e;01e;01e;0e;01e;0e;01e;01p122112++P(t)=P(t)P(t)+P(t)P(t),P(t)P(t)(A:4)e;01e;01e;1e;01e;1e;01e;01s122112ThederivationofE[G]isnotassimple.Tobeginwith,E[g(e)]iseasilyderivedforGeveryedgeeasg(e)P.Wethenperformtheseries-parallelcombinationsusingtheseone;1values.Incaseoftwoedgesinparallel,itiseasytoseethat:E[g(e)]=E[g(e)]+E[g(e)](A:5)p12Intheseriescase,however,theproblemisnotassimpleandweresorttotheapproxi-mation:11Eg(e)6=0(A:6)g(e)E[g(e)jg(e)6=0]whereE[AjB]denotestheconditionalexpectedvalueofAgivenB,toderive[12]:111+(A:7)E[g(e)]E[g(e)]PE[g(e)]Ps1e;12e;121Incaseofageneral,nonseries-parallel,graph,andsincetheproblemisNP,hardaspointedoutabove,weresorttoanothertechniquewhichisinlinewiththegraphreductionmethodology.Thisinvolvesanodeeliminationtechniquewhichisthegraph-domainopera-tioncorrespondingtoGaussianEliminationonthegraph'sadjacencymatrix[18].Itworksbyremovingavertexfromthegraphandaddingnewedgesbetweeneachofitsneighbors,asshowninFig.17.Supposeavertexvhasneighborsv;:::;valongedgese;:::;e.Upon1n1nremovingv,everytwoneighborsvandvshareanewedgee(Fig.17)whoseprobabilitiesijijarederivedbyapplyingtheseriesformulas(A.2)and(A.4)abovetoeande.Usingtheijapproximation(A.6),thevalueofE[g(e)]isderived[12]as:ijPnE[g(e)]k=1k111k6=i;j++(A:8)E[g(e)]E[g(e)]PE[g(e)]PE[g(e)]E[g(e)]ijie;1je;1ijji21 Asaresult,certainedgesaresplitintotwoormorenewedgeswhichmaynot,therefore,beindependent.Wehoweverignorethisfactandproceedwiththegraphreductionasbefore.KnowingthattheproblemisNP,hard,theresultinglossofaccuracyisinevitable,butexcellentresultshavebeenobtainedinpractice.22 References[1]F.M.d'Heurle,Electromigrationandfailureinelectronics:anintroduction,"Proceed-ingsoftheIEEE,vol.59,no.10,October1971.[2]J.R.Black,Electromigrationfailuremodesinaluminummetallizationforsemiconduc-tordevices,"ProceedingsoftheIEEE,vol.57,no.9,September1969.[3]J.E.Hall,D.E.Hocevar,P.Yang,andM.J.McGraw,SPIDER-aCADsystemformodelingVLSImetallizationpatterns,"IEEETransactionsonComputer-AidedDesign,vol.CAD-6,pp.1023{1031,Nov.1987.[4]L.W.Nagel,SPICE2:acomputerprogramtosimulatesemiconductorcircuits,"Ph.D.dissertation,Dept.ofElectricalEngineering,UniversityofCalifornia,Berkeley,1975.[5]J.W.McPhersonandP.B.Ghate,Amethodologyforthecalculationofcontinuousdcelectromigrationequivalentsfromtransientcurrentwaveforms,"TheElectrochemicalSociety,Proc.Symp.onElectromigrationofMetals,NewOrleans,LA,pp.64{74,Oct.7{12,1984.[6]R.Burch,F.Najm,P.Yang,andD.Hocevar,Pattern-independentcurrentestimationthforreliabilityanalysisofCMOScircuits",ACM/IEEE25DesignAutomationConfer-ence,pp.294{299,June12{15,1988.[7]F.Najm,R.Burch,P.Yang,andI.Hajj,CREST-acurrentestimatorforCMOScircuits,"IEEEInternationalConferenceonComputer-AidedDesign,SantaClara,CA,pp.204{207,November7{10,1988.[8]A.Papoulis,Probability,RandomVariables,andStochasticProcesses.NewYork,NY:McGraw-HillBookCo.,1984.[9]K.P.ParkerandE.J.McCluskey,Probabilistictreatmentofgeneralcombinationalnetworks,"IEEETransactionsonComputers,pp.668{670,June1975.[10]S.C.Seth,L.Pan,andV.D.Agrawal,PREDICT{probabilisticestimationofdig-thitalcircuittestability,"IEEE15AnnualInternationalSymposiumonFault{TolerantComputing,AnnArbor,MI,pp.220{225,June1985.[11]H.J.M.Veendrick,Short-circuitdissipationofstaticCMOScircuitryanditsimpactonthedesignofbuercircuits,"IEEEJournalofSolid-StateCircuits,vol.SC-19,no.4,August1984.[12]F.Najm,ProbabilisticsimulationforreliabilityanalysisofVLSIcircuits,"Ph.D.the-sis,Dept.ofElectricalandComputerEngineering,UniversityofIllinoisatUrbana-Champaign,June1989.[13]F.NajmandI.Hajj,Thecomplexityoftestgenerationatthetransistorlevel,"Re-port#UILU-ENG-87-2280,CoordinatedScienceLab.,UniversityofIllinoisatUrbana-Champaign,December1987.[14]N.P.Jouppi,DerivationofSignalFlowDirectioninMOSVLSI,"IEEETransactiononComputer-AidedDesign,vol.CAD-6,pp.480{490,May1987.[15]M.Horowitz,TimingModelsforMOSPassNetworks,"ProceedingsoftheIEEEInter-nationalSymposiumonCircuitsandSystems,1983.[16]M.R.GareyandD.S.Johnson,ComputersandIntractability,AGuidetotheTheoryofNP-Completeness.NewYork,NY:W.H.FreemanandCo.,1979.[17]F.Harary,Combinatorialproblemsingraphicalenumeration,"inAppliedCombinatorialMathematics,E.F.Beckenbach,Editor.NewYork,NY:JohnWileyandSons,Inc.,1984.[18]S.Parter,Theuseoflineargraphsingausselimination,"SIAMReview,vol.3,no.2,pp.119{130,April1961.23 FigureCaptions:Figure1:Fouractualcurrentwaveforms(dashed)andthecorrespondingexpectedcurrentwaveform(solid).Figure2:Aprobabilitywaveform(bottom)representsfourlogicalwaveforms(top).Figure3:Atypicalgraphreduction.Figure4:AgenericCMOSgate.Figure5:Relationshipbetweengateoutputcurrentandgatetotalcurrentpulses.Figure6:Stagesandwires.Figure7:Thedecompositionofatypicalpass-transistorcircuitintostagesandwires.Figure8:AsupergateschematicshowingtwornodesAandB.Figure9:Thedecompositionofasingleeventintologicaltransitions.Figure10:Complexgatecurrentestimate.Figure11:A40-stageinverterchaincurrentestimate.Figure12:Currentresultsforatypicalpass-transistorcircuit.Figure13:Currentresultsfora4-bitALUcircuitwith154MOSFETS.Figure14:Currentwaveformsforthe2-bitrippleadderinTable2.Figure15:CurrentwaveformsfordierentheuristicCRESTrunscomparedtothefull-accuracyCRESTrunonthe4-bitrippleadderinTable2.Figure16:Currentwaveformsforafairlytightheuristicrunandarelaxedheuristicrunforthe4-bitmultiplierinTable2.Figure17:Agenericnodeeliminationstep.24