Efficient Crosstalk Noise Modeling Using Aggressor and Tree

TreeReductions

DepartmentofElectricalEngineeringandComputerScienceTheUniversityofMichigan,AnnArbor,MI48109lding,blaauw,mazum@eecs.umich.eduLiDing,DavidBlaauw,andPinakiMazumderABSTRACTThispaperdescribesafastmethodtoestimatecrosstalknoiseinthepresenceofmultipleaggressornetsforuseinphysicaldesignautomationtools.Sincenoiseestimationisoftenpartoftheinner-loopofoptimizationalgorithms,veryefficientclosed-formsolu-tionsareneeded.Previousapproacheshavetypicallyusedsimplelumped3-4nodecircuittemplates.Oneaggressornetismodeledatatimeassumingthatthecouplingcapacitancestoallquietag-gressornetsaregrounded.Theyalsomodeltheloadfrominter-connectbranchesasalumpedcapacitoranduseadominantpoleapproximationtosolvethetemplatecircuit.Whiletheseapproxi-mationsallowforveryfastanalysis,theyresultinsignificantun-derestimationofthenoise.Inthispaper,weproposeanewandmorecomprehensivefastnoiseestimationmodel.Weusea6nodetemplatecircuitandproposeanovelreductiontechniqueformod-elingquietaggressornetsbasedontheconceptofcouplingpointadmittance.Wealsoproposeareductionmethodtoreplacetreebrancheswitheffectivecapacitorswhichmodelstheeffectofresis-tiveshielding.Finally,weproposeanewdoublepoleapproachtosolvethetemplatecircuit.Wetestedtheproposedmethodonnoise-proneinterconnectsfromanindustrialhighperformanceprocessor.Ourresultsshowaworst-caseerrorof7.8%andanaverageerrorof2.7%,whileallowingforveryfastanalysis.

1.INTRODUCTIONCrosstalknoisebetweensignalwireshasbecomeamajorsourceoffailuresinmodernhigh-performanceVLSIsystems[1]-[2].Duetotheaggressiveinterconnectscalinginthelateraldimensionswithrelativelyunchangedverticaldimensions,thecouplingcapacitanceamongadjacentwirescanbesignificantlylargerthanwiregroundcapacitance.Insuchstronglycoupledsystems,thestateofawirestronglydependsonthestatesofitsneighboringwires.Theswitch-ingofafirstnet,referredtoastheaggressornet,mayaffectthestateofasecondnearbynet,referredtoasthevictimnet.

itancesofabranchatthebranchingpointtosimplifythecircuit.Thisresultsinanunderestimationofcrosstalknoise.Finally,pre-viousmethodsuse3-4nodetemplatecircuitswhicharesolvedus-ingadominantpoleapproximation.Wewillshowthattheinabilityofthetemplatecircuittomodeltheresistanceoftheswitchingag-gressorandthedominantpoleapproximationfurthercompromisetheaccuracyoftheexistingfastnoiseanalysismethods.

Inthispaper,wepresentanefficientcrosstalknoiseestimationframeworkwhichmaintainstheefficiencyofpastapproaches,butsignificantlyimprovesontheiraccuracy.Weproposenovelquietaggressornetandtreebranchreductiontechniquewhichmodelsthemwitheffectiveloadcapacitances.Formulasarederivedtocal-culatethevaluesoftheseeffectivecapacitancesusingcoupling-pointandbranching-pointadmittancetogetherwithapproximatewaveformsatthecouplingandbranchingpoints.Inordertomodeltheresistanceoftheswitchingaggressornet,weusea6nodetem-platecircuit,whichsignificantlyenhancestheaccuracyofthenoiseestimation.Tosolvethismorecomplextemplatecircuit,wepro-poseanewdoublepolemethodandconfirmitsaccuracycomparedwithSPICEsimulation.Experimentalresultsonindustrialnetsdemonstratethattheproposedmethodssignificantlyenhancetheaccuracyofthenoiseestimationandeliminatesthetendencyofpriormethodstounderestimatethenoiselevel.Atthesametime,theproposedmethodmaintainstheefficiencyofpreviousmethodsandislinearinruntimewiththenumberofaggressornets.

Therestofthepaperisorganizedasfollows.Section2explainstheoverallframeworkoftheproposednoiseestimationmethodol-ogy.InSection3,weintroducequietaggressornetreductionandtreebranchreductiontechniquesbasedonpointadmittancematch-ing.ThereducedcircuitisthenanalyzedinSection4,whereweproposedthedoublepolemodelforefficientyetaccuratenoisecal-culation.AndinSection5,wepresentresultsofproposedmethod-ologyonindustrialcircuits.

2.METHODOLOGY

Thebasicideaoftheproposedmethodisfirsttoreducealargecrosstalknetworkintoasimpletemplatecircuit.Thetemplatecir-cuitisthensolvedanalytically.TheflowchartofthereductionschemeisillustratedinFigure1.First,weapplythetreereductionoperationoneachaggressornet.Second,weapplyquietaggressornetreductionoperationoneachoftheN-1non-switchingaggres-sors.Third,thebranchesinthevictimnetarereducedinasimilarmannerasthoseaggressornetbranches.Attheendofthisstep,weobtainasimplecircuitwithonlytwomainwireseachcorre-spondingtothevictimnetandtheactiveaggressornet.Finally,resistanceandcapacitancevaluesofthereducedtemplatecircuit,showninFigure2areextracted.

ThetemplatecircuitforcrosstalknoisemodelingshowninFig-ure2isanextensiontothe2-πmodelproposedin[10],wherethevictimnetismodeledusingthe2-π(3-node)circuitwhiletheag-gressornetissimplifiedasasaturatedrampinputatnode1inFig-ure2.Inthispaper,wemodelbothvictimnetandaggressornetas2-πcircuitssothatthelocationofthecapacitivecouplingcanbecorrectlymodeledandoverallmodelingaccuracyismuchim-proved.Wehaveproposedasimpleyetaccuratedoublepolemodeltosolvethecrosstalknoiseestimationprobleminthereducedtem-platecircuit.Notethatthistemplatecircuit,however,isonlysuit-ableforshorttomediuminterconnectsbecauseitusesonlyonelumpedcouplingcapacitor.Morecomplextemplatecircuitswithlargernumberofcouplingcapacitorsshouldbeemployedforverylongwires.Nevertheless,thereductionmethodsproposedinthispaperaregeneric,andtheyarenotrestrictedtothespecificcircuittopologyshowninFigure2.

Aggressor NetTree ReductionQuiet Aggressor Net ReductionRead Netlist

Solve Template Victim Net Circuit

Tree ReductionModel Parameter ExtractionFigure1:Flowchartoftreeandquiteaggressornetreduction.

inRARAL1RARCALCAMCAR

CXRVRVL2RVRoutCVLCVMCVR

Figure2:Singleaggressorcrosstalknoisemodel.

3.REDUCTIONTECHNIQUES

Eachreductiontechniquedescribedinthissectionconsistsoftwophasesinsequence.Inthefirstphase,aquietaggressornetortreebranchismodeledusingsimplereducedcircuitsbymatchingthelowerorderTaylorseriesexpansioncoefficientsoftheadmit-tanceYsatthecouplingpointorbranchingpointofthecircuit.Inthesecondphase,aneffectivecapacitanceisderivedtoreplacethosereducedcircuitstofurtherimprovetheefficiency.

3.1Overviewofpointadmittance

LetYsdenotesthepointadmittanceofageneralcircuit.ItcanbeapproximatedbythesumoflowerorderTaylorseriesexpansionterms

Ys

y0

y1s

2

y2sy3s3

Os4

(1)

whereyn(nthefirsttermy0is12zero3)iswhenthenthere-thexpansionisnodcconductingcoefficient.pathNotefromthattheobservingpoint0totheground.

Thecoupling-pointadmittanceorbranching-pointadmittanceiscomputedstartingfromtheleafnodesofaRCtreethengoingbacktothecouplingorbranchingpoint.Thisissimilartotheapproachesusedinsolvingthedriving-pointadmittanceproblemforgatedelaycalculation[13].Threebasicrulesareusedinthealgorithmtocalculatethelowerordercoefficients.Thoserulesarepresentedin(2)-(4)andareillustratedinFigure3.Rule1:serialresistance:

y0

py0

y1

2py1

y2

p2y2

p3ry21

y3

p2y32p3ry1y2

p4r2y31

(2)

wheretheparameterpisdefinedasp

11ry0.

Rule 1:

Y(s)rY*(s)Rule 2:

Y(s)cY*(s)Y1(s)Rule 3:

Y*(s)Y2(s)Figure3:Rulesforpointadmittanceexpansioncoefficients.

Rule2:serialcapacitance:

y0

0

y1

c

y2

c2y0

y3

c2y1cy20

(3)

Rule3:branchjoin:

y0

y10y20y1y11y21y2y12y22y3

y13

y23

(4)

whereyi0,yi1,yi2andyi3arethefirstfourTaylorseriesexpansioncoefficientsofthei-thbranch(i3canbeappliedformultipletimes12),whenrespectively.therearemoreNotethatthanRuletwojoiningbranches.

Itiseasytoobservethat1)thefirstfourtermsoftheadmit-tancey0,y1,y2,andy3arepreservedbyrepeatedapplicationofaboverules,and2)thetimecomplexitytoreduceasubtreeusingthisreductiontechniqueislinearwithrespecttothenumberofRCelementsinthenetlist.

3.2Quietaggressornetreduction

ConsidertheequivalentquietaggressornetshowninFigure4(a).WefirstreducetheaggressornettoasingleresistorRinFigure4(b)bymatchingtheAandasinglecapacitorCAasshownfirsttwoTay-lorseriesexpansioncoefficientsyonlyy0andy1oftheaggressornetatnodeA.Since0andy1appearattherightsideof(3),wecanhenceneglecthigherorderTaylorcoefficientsatnodeAtoachievethirdorderaccuracyatnodeV.ByapplyingbothRule1andRule3,itisstraightforwardtoobtaintheadmittanceatnodeAas

Y1

As

2CAL

CAMCARs

Os2

RARAL

(5)

Therefore,thedevicesinthesimplifiedcircuitshowninFigure4(b)

havethefollowingvalues

RA

RA

RAL

(6)

CR2A

A

dtCdVVt

X

dt

(8)

AssumethevoltagewaveformofthevictimnetisanormalizedrampinputVVtttr,0ttr.Wehaveobtainedthefollowingformulafortheeffectivecapacitance

CReff

ACX

1

(a)witharisetimeoftr,theeffectivecapacitancecanbederivedas

AARB(b)A(c)C1C2CeffFigure5:Treereductionforcrosstalkestimation.(a)GeneralRCtreebranch.(b)Reduced-orderπ-modelforthetree.(c)Treeeffectivecapacitance.

considerhereareactuallybranchesthatconnectedtothe‘main’wiresoftheaggressornetsorthevictimnet.Wemodelthosebranchesemployingsimilarapproachesasthoseusedin[13]and[14].FirstageneralRCtreestructureisreducedtoasimpleπ-modelasshowninFigure5(b)bymatchingthefirstthreemomentsofthetree.Theresultingmodelisthenfurtherreducedtoaneffec-tivecapacitance,showninFigure5(c),foragivensignalswitchingslopeatthenodeA.

Thedifferencebetweentheproposedmethodandthetechniquesforeffectivedrivingpointcapacitanceliesintheinterfacingoftheπ-typecircuitwithexternalwaveforms.Fordelaycalculation,theeffectivecapacitancetriestomatchtheaveragecapacitancefortheperiodfromstarttothetimewhenthevoltagereaches50%ofthesupplyvoltage.Forcrosstalknoiseestimation,however,wetrytomatchtheaveragecapacitanceofthebranchduringtheentiresignalswitchingperiod.

Sincethereisnodirectdcpathtothegroundincircuitbranches,wealwayshaveyeralRCtreeareobtained00.OncebyrepeatedlythefirstthreeapplyingmomentsRule1of,weagen-canconstructareducedπ-typecircuitwhichmatchesthosethreemo-ments.Thevaluesofthecapacitorsandtheresistorinthefigurearecalculatedas

Cy221

2

3

y1

y3

R

ydt

CdV1

At

dt

(11)

Assuminganormalizedsaturatedrampinputatthevictimnode

Ceff

C1

1

RC2

tr0tV

tr0

1e

CX

Cr

Reff

ARCAR

1

ttA

r

ttrtA

ttrtA

r

1

e

e

t

(15)

tr

(20)

0.3Region IRegion II)V( e0.2gDouble PoleatloV deSPICEzilamro0.1NDominant Pole000.20.4Time (ns)0.60.81.01.2Figure6:Comparisonofnoisewaveforms.

Now,insteadofusingasimplerampfunctionatnode1astheag-gressornetwaveform,weusetheabovemoreaccurateform.Usingdominantpoleapproximationonthevictimnet,wehaveobtainedthetime-domainnoisevoltageoutput,whichcanbedividedintothefollowingtworegions:1)RegionI(0ttr):

VI

ttout

X

ttA

ttrtA

tr

αe

e

e

ttV

e

ttrtV

β(22)

whereαtAtVteasilyobservedAandβtVtVtthatthenoiseA.

Itcanbevoltageincreasesmono-tonicallyinRegionIanditincreases,thendecreasesinRegionII.Therefore,themaximumnoiseBysolvingtheequationdVIIvoltagealwaysoccursinRegionII.

voltagereachesthepeak

outtdt0,weobtainthetimenoise

tpeak

tr

tVtA

1

trtV

(23)

e

WecomparethenoisewaveformsgeneratedbythedominantpoleandthedoublepolemodelswiththatobtainedusingSPICEsimulationinFigure6.Thefollowingcircuitparametersareas-sumed.Thedrivingresistancesoftheaggressorandthevictimare500Ωand1000Ω,respectively;thewireresistancesare100Ωeach;thegroundcapacitancesare50fFeachandthecouplingca-pacitanceis150fF;andtherisingslopeoftheinputsignalis200ps.Clearly,thewaveformobtainedusingthedoublepoleapproxima-tionismoreaccuratethanthatobtainedbythedominantpoleap-proximation.First,thenoisepeaktimeisveryclosetothecorrectvalue.Second,thederivativeofthevoltagewaveformiscontinuousthroughouttheentirerange,whichisimportantformanyoptimiza-tionengines.Andthird,thenoisevoltagematchesthesimulatedresultwellovertheentirewaveform.

Peaknoisevoltageisametrictodeterminewhetherthenoiseonasignalwireexceedsthestaticnoisemarginofthereceivers.How-ever,thedurationthatthesignalishigherthanreceiverstaticnoisemarginshouldalsobeconsideredtomeasuretheeffectofthenoiseonthereceiveroutput.Inliterature,thisisaccomplishedbyusingthenoisewidthmetric.Inthepresenceofmultipleaggressornets,however,thenoisewidthoftheglitchesgeneratedbyeachsingle

Table1:Experimentalresultsonnoisearea.Circuit#RCSPICE

2/21.490.1(1.3)

9/92.800.596(2.2)4/42.620.4(1.7)5/52.800.522(2.6)9/92.790.600(0.2)9/92.610.520(0.3)4/41.470.393(0.7)7/60.710.706(0.0)7/52.071.220(0.2)2/22.820.477(1.2)7/72.700.459(2.4)3/31.690.404(1.3)3/31.690.404(0.7)10/102.580.397(2.1)3/31.470.329(1.5)2/21.710.409(0.4)7/42.828.969(0.0)3/31.680.407(1.1)2/21.490.269(1.2)3/31.700.406(0.1)2/21.650.397(1.1)7/72.730.651(0.6)5/32.728.860(0.1)2/21.480.250(1.5)3/31.700.401(0.7)5/52.410.352(4.3)10/92.750.385(1.2)5/52.710.406(4.5)2/21.470.282(2.5)9/92.120.224

(1.0)

Ave128-

Table2:Experimentalresultsonpeaknoisevoltage.CircuitSimple(Err%)

0.8390.900(7.4)0.7930.782(1.4)0.7900.812(2.7)0.7860.796(1.3)0.7650.765(0.0)0.7720.731(5.4)0.70.772(1.0)0.7160.761(6.3)0.7130.727(2.1)0.7100.6(7.8)0.7040.717(1.8)0.6950.682(1.9)0.6930.682(1.5)0.6820.658(3.5)0.6860.702(2.3)0.6900.683(1.1)0.6860.693(1.0)0.6880.687(0.1)0.6850.684(0.2)0.6850.676(1.3)0.6840.682(0.4)0.6630.658(0.7)0.6620.714(7.7)0.6560.657(0.2)0.6560.0(2.5)0.6320.616(2.5)0.6320.585(7.4)0.6260.625(0.1)0.6260.639(2.0)0.6220.585(5.9)

Ave/Max11.7%/21.3%