第七章电路系统划分-以前第十章布线

第第十章第一Introductionto布线引2)构造连线在网格图中有六个点需要连,构造连线表第四节算法 在布图设计中在布图设计中,当布局完成以后,紧接着的步骤就是布线。而简单说来,布线的目标就是根据电路的连接关系,在满足设计规则,工艺规则及电器性能要求的条件下,在限定区域或尽量小的区域内,完成所有指定的互连,同时使得连线总长尽量短,连通孔数尽量少,并具有足够高的设计效率.1)方形网格及走 用树用树的生长算法生成最小生成树以两点间的曼哈坦距离为边权,用树的生长算法,长成的一棵最小生成数有了上面的图,则如用几种颜对图的顶点进行且使得相邻顶点具不同颜色。再把同种颜色的顶点所代表的线放在一层上,整个相交图上的线放在N层上,,的基本要求。分层后不再出现相交线的最小层数即为图模型中相邻顶点具有不同着色的最少颜色数(四色定理)。3)分层对于双层和多层布线而言,在给出了点-点互连以后,紧接着的问题就是把每条线分配到具体层上去。分层问题很容易转化为图论问题。如果用顶点表示相交图中一条直线,用相邻两点之间的一条边表示两顶点所对应的直线相交,图的模型如下: 排排方式进行布线的。就是说当连线表给出以后,,,又是有讲究的。布线的主要目标是获得最高的布通率。为此,,虑当前连线对以后布线所带来的影响。下面的图示就说明了连线次序的重要此时问题归结为一个二问题。VI处理,往往采取横、竖线分层的办法,即横线分配在一层,竖线分配在另一层。 RoutingindesignTheRouting在布图规划/输入网表模块的位置和引脚的位输出所有线网的几何位置（all目标最小化总线长，连通孔数或刚好完成所有的连接而不增加每条线网满足它的时间SteinerTree最小连接对一个多端线网,可以构造一个生成树来把所有的最好使 Atreeconnectingallterminalsandsomeadditionalnodes(Steinernodes).RectilinearSteinerTree:直 Steinertreeinwhichalltheedgesrunhorizontallyandvertically.所有的边都是水平的和垂直的。TheRouting布局约束-placement布线层数-Numberofrouting延迟约束-Delay满足所有的几何约束（设计规则物理/电的/制造的约束RoutingProblemisVeryMinimumSteinerTree--给定一个线网,找出具有最小–这是一个NP-完全问题在布线区域中又可能存在 上例说明了布线次序的重要性,一般有以下几种排序方法相交 点少的线先对两点线网，先求出两点间最短曼哈坦距离，距离小的线先布。以每对互连接点为对顶点分别作一个矩形.这样,每个矩形中会含有数目不等的接点.布线时按所含节点数少的矩形中的顶点互连优先的原则进行布线.线干扰度序法:处理原则与点干扰度法类似基于总体分析的顺序处理方法:以通道损耗最小化为目标,先分析两线网间的基本关系,然后根据分析结果进行排序.最后按排序进行布线. 布线途Sequential布线途SequentialApproach:顺Routenetsoneatatime.一次布一条线Orderdependsonfactorslikecriticality,estimatedwirelength,andnumberofterminals.顺序依赖于判据，如线长估计和端子数。Whenfurtherroutingofnetsisnotpossiblebecausesomenetsareblockedbynetsroutedearlier,apply‘Rip-upandReroute’technique(or‘Shove-aside’technique).有时，进一步布后序线网时，会出现不能布的情况，因为有些线网已被已布线网占去。可采线重布技术ConcurrentApproach:并发Considerallnetssimultaneously,i.e.,noordering.同时考虑所有线Canbeformulatedasintegerprogramming.这可公式化为整数规。GlobalRouting-DetailedRouting-Channel-通道布Switchbox-开关盒布Others迷宫布线-Maze跨单元布线-Overthecell时钟布线-ClockGlobalvs.DetailedGlobalvs.DetailedGlobalInput:detailedplacement,withexactterminalDetermine“channel”(routingregion)foreachObjective:minimizearea(congestion),andtiming(approximate)DetailedInput:channelsandapproximateroutingfromtheglobalroutingphaseDeterminetheexactrouteandlayersforeachObjective:validrouting,minimizearea(congestion),meettimingconstraintsAdditionalobjectives:minvia,总体布线 详细布 特殊布迭

受限 通用

时钟布线迷 通道布

GreedyLeft- GeneralRoutingParadigm一般的布线范分两个阶段布线

第二节总体布线-GlobalGlobalrouingisdividedinto3总体布线被划分为三个阶RegiondefinitionRegionassignmentPinassignmenttoroutingregions布线区引线网表信息提取和时延分Afterglobalroutinganddetailedrouting,informationofthenetscanbeextractedanddelayscan 在总体布线和详细布线以后网表信息能被提取出来,时延也能被也可分析出来.Ifsomenetsfailtomeettheirtimingbudget,detailedroutingand/lobalroutingneedstoberepeated.

全局布线GlobalRouting Routingregion RoutingregionSteiner-tree/area Tilessuper-imposedonRegularorSmallerproblemtosolve,higherlevelof TerminalsatcenterofgridEdgeNumberofnetsthatcanpassacertaingridedge(akacongestion)OnedgeCapacity(E)Congestion(E RoutingRegions布RoutingRegions布线Courseorfine-Vertices:routingregions,edges:routeWeightsonHowcostlyistousethatCouldvaryduringtherouting(e.g.,forHorizontal/verticalmighthavedifferent

区域定义RegionDividetheroutingareaintoroutingregionsofsimplesh(rectangular划分布线区成简单形状的布线区域(如矩形)Channel:Pinson2opposite2-DSwitchbox:Pinson43-DSwitchbox:Pinsonall6

RoutingRegionsinDifferentDesignStyles不同设计风格中的布线Gate- Standard- Full-Feedthrough 区域分配RegionAssignroutingregionstoeachnet.Needtoconsidertimingbudgetofnetsandroutingcongestionoftheregions.对每个线网分配布线区.需考虑线网时延和区域的布线拥挤

GridGraph网格A Anodewith布线区的图

CheckerBoardGraph检查板

11 11A Anodewith ChannelChannelIntersection通道交叉AAnodewithRoutingsalongtheApproacheslobal总体布线的ConcurrentApproach:Considerallnetssimultaneously.Canbeformulatedasanintegerprogram.可被公式化为Approacheslobal总体布线的SequentialApproach:Routethenetsoneatatime.一次一条线网的布Orderdependentonfactorslikecriticality,estimatedwirelength,etc.Iffurtherroutingisimpossiblebecausesomenetsareblockedbynetsroutedearlier,applyRip-upandRerouteThisapproachis ore3.PinAssignment引线端分Assignpinsonroutingregionboundariesforeachnet.(Prepareforthedetailedroutingstageforeachregion.)在布线区域的边界为每条线网分配MazeRoutingGiven給定Aplanarrectangulargridgraph.给定平面矩形网格TwopointsSandTonthegraph.Obstaclesmodeledasblockedvertices.模型化的作为块状顶点的Objective目标FindtheshortestpathconnectingSand找到连接S和T的最短路径Thistechniquecanbeusedinglobalordetailedrouting(switchbox)problems.这种技术能被用在总体或详细布线第三节迷宫布线(MazeGridGraph网格SSTTSXXTAreaGridGraph BasicIdea基本概Lee’s算法的特点AlwaysfindtheshortestpathConsistsoftwoWaveAlwaysfindtheshortestpathConsistsoftwoWavePropagation（波的扩展阶段）Retrace（回溯阶段AnS123123345545T WavePropagation波Atstepk,allverticesatManhattan-distancekfromSarelabeledwithk.在第k步,在离源点S的曼哈坦距离为HowmanygridsvisitedusingLee’s09HowmanygridsvisitedusingLee’s09876543212345678654321S1234567987 32123456783567891110989767892 111211093111213121102931311121312TS0S02S123 76721110 6569891013123111098765098765478967893

3445TMazeSTLee’sAlgorithm李氏算 gorithmforPathConnectionMazeSTLee’sAlgorithm李氏算 gorithmforPathConnectionandApplication”,C.Y.Lee,IRETransactionsonComputers,Retrace回Tracebacktheactualroute.StartingfromT.从目标点T开始Atvertexwithk,gotoanyvertexwithlabelk-1.在标SFinal12TimeTimeandSpace时间和空间复杂ForagridstructureofsizewhTimepernet=Space=O(whlogwh)(O(logwh)bitsareneededtostoreeachlabel.)ForFora40004000grid24bitsperTotal48Mbytesof34545TImprovementImprovementtoLee’s李氏算法的Improvementon AkersCodingImprovementonruntime:StartingpointDoublefan-HadlocksSoukupsDetourForapathPfromStoT,letdetournumberd(P)=#ofgridsdirectedawayfromT,thenL(P)=MD(S,T)+DTshortestManhattanD:d(P)=MD(S,T)=L(P)=6+2x3=Hadlock’sAlgorithmtoReduceRunHadlock’sLabelverticeswithdetourVerticeswithsmallerdetournumberare.Therefore,favorpathswithout32222221S10101222232222Soukup’sAlgorithmtoReduceRunHowmanygridsvisitedusingSTBasicSoukup’sAlgorithm:Exploreinthedirectiontowardsthe withoutchangingdirection.(DFS)Ifobstacleishit,searcharoundtheobstacle.MaygetSub-Optimal221S 22HowmanygridsvisitedusingST Multi-TerminalMulti-TerminalForak-terminalnet,connectthekterminalsusingarectilinearSteinertreewiththeshortestwirelengthonthemaze.Thisproblem JustwanttofindsomegoodExtensiontoMulti-Terminal1st2ndS1223S0S0S01212Multi-TerminalThisproblemcanbesolvedbyextendingtheLee’sConnectoneterminalatatime,Searchfor ssimultaneously,PropagatewavefrontsfromseveraldifferentsourcesGlobalRouting全局布线的SequentialApproach(Rip-upandRe-MazeLineShortestPathBasedSteinerTreeBasedConcurrentIntegerSequentialGraphmodelingoftheroutingForeachnetFindarouterfornetkontheForeachedgeeincapacity(e)=capacity(e)-ifcapacity(e)<0thencost(e)=MazeRoutingonWeightedMazeRoutingforMulti-TerminalExampleofWeighted WeWecanusedifferentmethodstodo i&Tabuchi’s

LineWecanuseallthegridverticesonthelinesegmentsas 101 SIteration T 10

Alwaysfindapathbutmaynotbe第四节线探索布线(LineKeeptwolistsoflinesegments,slistandtlist,forthesourceandthe Ifalinesegmentfromslistintersectswithonefromtlist,arouteisfound;else,newlinesegmentsaregeneratedfromtheescpoints.

Hightower’sS

LineWecanpickjustoneesc pointfromeachline

Comparisonof0 terationT 1Mayfailtofindapathevenifone

ShortestPathBased基于最短路For2-terminalnetsUseDijkstra’salgorithmtofindtheshortestpathbetweenthesourcesandthesinktofanet.DifferentfromMazeThegraphneednotbearectangularTheedgesneednotbeofunit Dijkstra’sShortestPathDijkstra’sShortestPathLabelofvertices=ShortestdistancefromLetPbethesetofpermanentlylabeledP=EmptyLabelofS=0,Labelofallothervertices=While(TisnotinP)Pickthevertexvwiththemin.labelamongallverticesnotinAddvtoUpdatethelabelforallneighboursofSteinerTreeBasedFormulti-terminalFindSteinertreeinsteadofshortest teinertreefromtheminimumspanningtrees(MST)Dijkstra’sAlgorithm:P(PermanentlyMin.LabelB1TB0S101TB1T239470S2394750S 23947A2C21AC15A27C10S23940S23945A0S277C239475A277C5A27CAnetisasetofnDegreeofanetisthenumberofpinsinConsiderroutingalongHananDefineedgelengthshandPotentiallyOptimalWVTofindoptimalwirelength,canenumerateallHowever,mostWVscanneverproduceoptimal–(1,2,1,1,1,2)isredundantasitalwaysproducesalargerthan(1,2,1,1,1,(1,2,1,1,1,(1,2,1,1,1,PotentiallyOptimalWirelengthVector(POWV)isaWVthatmayproducetheoptimalwirelengthWirelengthVectorObservation:WLcanbewrittenasalinearcombinationofedgelengthswithpositiveintegralcoefficients(1,2,1,1,1,2)(1,1,1,1,2,3)(1,2,1,1,1,WLcanbeexpressedasavectoroftheCalledWirelength#ofPOWVsisVeryForany#ofpossibleroutingsolutionsis#ofWVsismuch#ofPOWVsisveryForexample,only2POWVsforthenet888888FLUTEFLUTESolveRectilinearSteinerminimaltree(RSMT)BasicHandlingofsmallnets(withafewpins)isextremelySoFLUTEisespeciallysuitableforVLSI SharingofPOWVsAmong StepsinFLUTEWLTofindoptimalWL,wecan puteallPOWVsandstoretheminalookuptableHowever,thereareinfinitenumberofdifferent

1.Inputa 2.Findh’sand

Findvertical2413WetrytogrouptogethernetsthatcansharethesamesetofPOWVsForexample,thesetwonetssharethesamesetof

GetPOWVsfrom

FindWLforeachPOWVandreturnthebestHPWL+h=22returnHPWL+v=26OneRSMTtopologyc sobe putedandstoredforeachImpracticalforhigh-degreenets(degree>= byVerticalDefineverticalsequencess…stobethelistofpinindexessortediny-coordinateVertical=

NetInsequentialapproach,weneedsomenetAbadnetorderingwillincreasethetotalwirelength,andmayevenpreventcom-pletionofroutingforsomecircuitswhichareindeedroutable. Lemma:Thesetofalldegree-nnetscanbedividedinton!groupsaccordingtotheverticalsequencesuchthatallnetsineachgroupsharethesamesetofPOWVs

A(Good

A(Bad CriteriaforNetCriticalityofnet-critical Estimatedwirelength-shortnets sincetheyarelessflexible.

Rip-UpandRe-tisimpossibletogettheoptimalnetIfsomenetsarefailedtoberouted,therip-upandre-routetechniquecanbeapplied:Considerboundingrectangles

CannotrouteC Sorip-upBandrouteC

FinallyrouteBABWhichoneshouldbeandwhy?(Notethatthisrule

ABisinA’s

thumbisnotalwaysapplicable

NetOrdering

ConcurrentConsiderallthenetsFormulateasanintegerSetofpossiblerouting::::L=TotalwirelengthofTC=CapacityofedgeDeterminevariablexs.t.x=1ifTisx=0 IntegerIntegerProgramIntegerProgrammingStandardtechniquestosolveNonetordering.GiveglobalCanbeextremelyslow,especiallyforlargeTomakeitfaster,afewerchoicesofroutingtreesforeachnetcanbeused.Maymaketheproblem iveabadsolution.Determiningagoodsetofchoicesofroutingtreesisahardproblembyitself.ConcurrentApproach:112332abdPossiblenet1: 2c1,2net2:33C=C=C=C=2net22112Whataretheconstraintsforedgecapacity?2332HierarchicalApproachtoSpeedUpIntegerProgrammingFormulation lobalM.BursteinandR.Pelavin,“HierarchicalWireIEEETCAD,vol.CADs223-234,Oct.HierarchicalLargeIntegerProgramsaredifficulttoHierarchicalApproachreducesglobalroutingtoroutingproblemsona2x2grid.poserecursivelyinatop-downThose2x2routingproblemscanbesolvedoptimallybyintegerprogrammingformulation.Typesof2x2RoutingType TypeTypeTypeTypeTypeTypeTypeTypeTypeTypeHierachicalApproach:Solvinga2xnroutingproblemLevelLevelLevelObjectiveFunctionof2x2PossibleRoutingT11,T12,T21,T22,,T11,1,...,#ofnetsofeachtype:n1,...,Determinexij:#oftype-inetsusingTijforrouting.yi:#oftype-inetsthatfailstoroute. ConstraintsConstraintsof2x2ConstraintsonEdgebadConstraintson#ofBendsinaILPFormulationof2x2Only39variables(28xand11y)19constraints(plus38non-negativeProblemsofthissizeareusuallynottoodifficulttoPopIfyoutwonets,onewith2pins,theotherwith4pinswithazerocapacityedgeTypeTypeAfterGlobalRouting:DetailedTheroutingregionsaredividedintochannelsandABSoonlyneedtoconsiderthechannelroutingproblemandtheswitchboxroutingproblem.ChannelRoutingforDifferent ate-arraydesign,channelwidthsarefixed.Thegoalistofinishroutingofallthenets.ForStandard-cellandFull-customdesign,channelsareexpandable.Thegoalistorouteallnetsusingtheminimumchannelwidth.WewillconsiderthecasewhenthechannelsareChannelNofeasiblechannelorder!NeedtouseCD BABAFixtheterminalsbetweenA&RouteB,C,thenDRouteAChannelAThewidthofAisnotknownuntilAisrouted,wemustroute BBACDWhatshouldbetheroutingorderforthisexample?RoutingGridGrid-based GridlessGrid-basedmodelisthemostcommonlyWewillfocusonitinthis ChannelChannelRoutingUpperLower 第五节通道布线ChannelRoutingTwovectorsofthesamelengthtorepresentthepinsontwosidesofthechannel.NumberoflayersandlayermodelConnectpinsofthesamenetMinimizethechannelMinimizethenumberofRoutingLayer1VHHV2VHVHVHLayerLayerLayer33ChannelRouting2030Example:where0=noConstraint03132546354026635402651215344362Verticalconstraint HorizontalconstraintChannelRoutingAlgorithm“WireRoutingbyOptimizingAssignmentwithin rtures”,A.HashimotoJ.Stevens,DAC1971,pages155-LowerBoundonChannel0205Channeldensityumlocal635402density134444Lowerbound=FeaturesofLeft-edgeOnehorizontalroutingNoverticalconstraint,e.g.,VHV00020121Verticalconstraintmayoccur010002Alwaysgivesasolutionwithchannelwidthequalchanneldensity,ie.,optimalsolution. Left-edgeAlgorithm:0Sortbyleftend6135420161613542

2Placenets0Left-edgeLeft-edgeSortthehorizontalsegmentsofthenetsinincreasingorderoftheirleftendpoints.Placethemonebyonegreedilyonthebottommostavailabletrack.IntervalChannelaLocaldensityatcolumnld(C)=#netssplitbycolumnaChannelDensityd=maxld(CallaEachnetspansoveranaHorizontalConstraintGraph(HCG)node:edge:twointervalsaSizeofmaxcliqueinHCG=channelaAlower#trackschannelLeft-EdgeAlgorithmforIntervalcreateanewtracktputleftmostfeasibleintervaltotuntilnomovefeasibleintervaluntilnomoveIntervalaresortedaccordingtotheirleftO(nlogn)timealgorithm.GreedyalgorithmLowerBoundonChannel02651Lengthofthelongestpathintheverticalcon-straintgraph432Lowerbound=VerticalConstraintTheLeft-edgealgorithmignoresverticalWhenthereisonlyoneverticallayer,thealgorithmwillproduceoverlap ofverticalwiresegments.02LowerBoundonChannel635402

635402

ConstrainedLeft-edge60402Sorttheleftend42016123426

2VerticalconstraintPlacenetsgreedily.25463540246354024 Deutch’sDogleg Deutch’sDoglegSplitea ulti-terminalnetintoseveralhorizontalSplitonlyatcolumnsthatcontainapinofthenet,i.e.,usingrestricteddoglegonly.ApplytheConstrainedLeft-edge

1120212a3a423034

split

ConstrainedLeft-edgeConsiderConstrainedLeft-edgeConsiderverticalSimilartotheLeft-edgeModifications:PlaceahorizontalsegmentonlyifitdoesnothaveanyunplaceddescendantsintheverticalconstraintgraphG.PlaceitonthebottommostavailabletrackaboveallitsdescendentsinG.CyclesinVerticalConstraintIfthereiscycleintheverticalconstraintgraph,thechannelisnotroutable.1 2Doglegcansolvethe 20ReduceChannelWidthbyEvenwithoutcycleintheVCG,Doglegisusefulbecauseitcanreducechannelwidth.Without1122With0203Deutch’sDogleg 1120212343423034RoutingwithoutVerticalconstraintgraphafterRoutingwihDrawbacksoftheConstrainedLeft-edgeAlgorithm00133Vertical3212002ByConstrainedLeft-edgealgorithm00133Thereisabetter120021112211020WithoutByDeutch’sDogleg020302033 DrawbacksoftheConstrainedLeft-edgeAlgorithmWhat’swrongwiththeConstrainedLeft-edgeTheConstrainedLeft-edgealgorithmdoesnottakecareoftheverticalandhorizontalconstraintstogether

CharacterizingChannelRoutingYoshimuraandKuh’s“EfficientAlgorithmsforChannelbyT.YoshimuraandE.

Zone 23535268987IEEETrans.OnComputer-AidedDesignofIntegratedCircuitsandSystems.Vol.CAD-1,pp25-35,Jan

24222224677833467889445955123453

477

Remarks:Anewzoneappearswhenintervalsbeginaftersomeintervalsend. Zone22

Scanningthe1124447911244479123 9224677943467885459 Right=35 234

9

Left={1,2, Right=

4

Left={2,3,Right={8,

5,6

Mergingof

Scanningof1

2 9 9

24

2

Left={2,3.8,Right=

MergingMerging793622384492 238MergingofMakesurethattheVCGremainsTherearetwo approach:Mergethepairssequentially.SelectpairstominimizetheincreaseinthelengthofthelongestpathintheSecondapproach:Mergeallpairssimultaneously.Selectpairsto izethetotalno.ofmatches.Wewillfocusonthesecondapproach:“simultaneousAssigningTrackTrack5,6,9TrackTrack5(or4)3,8Track4(oringsofObservation:MergingoftwonodesmayblocksubsequentmergingNetfcannotbemergedwitheither.But,ifmergedawithd,cwithethenfcanbemergedwithnetProcessingsSimultaneousmergingcanproduceBipartitegraph,22314SimultaneousUseumcardinalitymatchingbipartiteLeft={1,3,Right=1Findum356inthisbipartitegraphsuchtheresultantVCGisstillsBiparitegraphAlgorihmAAAsetofedgesE’Theorem:AnymatchinginG(V,E-E’)is AnExampleofAnExampleofAlgorithmN=setofnodesihavein-degreegadbRemoveedgesbetweenverticesinNgcihhigaibchAnExampleofAlgorithmbNgcic ibhiNbcihhibchAnExampleofAlgorithmigaNibchiNoisolatednode.ThenselectamongNthenodewiththesmallestdegreeinthebipartitegraph.RemoveandputitsedgestoE’.igcibhAnExampleofAlgorithmhNbchh ,alledgesareremoved,andE’={(a,h)}SinceE’,accordingtothecorollary,anymatchinginthebipartitegraphG(V,E-E’)isfeasible.WewillfindamatchinginG(V,E-¬Avoidunnecessaryintroductionofdogleg,useaprocess“mergingofsubnets”-ReduceCPUtime®NeednotstartatzoneRoutingExamplesbyY-K’sRoutingExamplesbyY-K’sDeutsch’sDifficult#columns=174,#nets=72Deutsch’sdifficultexamplewith SummarySummaryofYoshimuraandKuh’saSplitmulti-terminalnetsinto2-terminalaMergingsubnetstoshareaConsiderbothHCGandaGlobalmatchinganddelayedmerging aCannotproduceunrestrictedaVCGcannothaveOverviewofGreedyLeft-to-right,Column-by-columnIngeneral,anetmayGreedyChannelR.L.RivestandC.M.Fiduccia“AGreedyChannelRouter”,19thDAC,1982P418-424aAsimplelineartimeaGuaranteethecompletionofallthenets(mayextendtoright-handsideofthechannel)aProducebothrestricteddoglegsandunrestrictedOperationsatEachAteachcolumn,thegreedyroutertriesto theutilityofthewiringproduced:A:Makeminimalfeasibletop/bottomconnections;B:Collapsesplitnets;C:Movesplitnetsclosertooneanother;D:Raiserisingnets/lowerfallingnets;E:Widenchannelwhennecessary;F:Extendtonext(A)MakeMinimalFeasibleTop/Bottom(C)MoveSplitNets(B)CollapseSplit(D) ((E)InsertNewCommentsonGreedy(Rivest&Fiduccia(F)ExtendtoNextParameterstoGreedyaInitial-channel-aMinimum-jog-aSteady-net-aUsuallystarticwasd.theaMjlcontrolsthenumberofvias,usealargemjlforfewerviasaSncalsocontrols#ofvias,typicalExperimentalaRunsverya20-tracksolutiontotheDeutsch’sDifficultOver-the-CellChannelwidthcanbereducedifsomenetscanberoutedoutsidethechannel.Themetallayersavailableoverthecellrowscanbeusedforrouting.(ItispossibleduetothelimiteduseoftheM2metallayerwithinthecells.)Commonlyusedinstandard-cellChannel/SwitchBoxRoutingaGraphtheorybasedYoshimuraandaGreedyalgorithmRivestandFiducciaChannelaMazeroutinganditsLee,Robin,Soukup,aHierarchicalwireroutingBursteinandPelavinChannel/switchboxandgeneralareaOver-the-CellRouter“Over-the-CellChannelRouting”,J.CongandC.L.Liu,TCAD,pages408-418,1990. BoundaryBoundaryTerminalModelTheRoutingBoundaryTerminalModelTworoutinglayersintheOneroutinglayerforover-the-cellrouting,sotheroutingmustbeplanar.141536563ThreeStepsofthe ertheSelectanetsegmentfromea nettobeconnectedinthechannel.RoutingintheertheReducedtoaMulti-TerminalSingle-LayerOne-SidedRoutingProblem(MSOP).SolvedbydynamicCanbesolvedbydynamicConsiderthesub-problemfromcolumnitoj.LetM(i,j)bethe umreductioninthenumberofhyper-terminalsfromitoj.CaseM(i,j)=NonetsatiorthenetisconnectedtoijCaseM(i,j)=NetijThefewerthenumberofhyper-terminalsresulted,thesimplerthesubsequentchannelroutingproblem.Routingarowofterminalsusingasingleroutinglayerononesideoftherowsuchthatthenumberofhyper-terminalsisminimized.?1215254343CanyougiveasolutionforthisCaseM(i,j)=Nonetsatiorthenetisconnectedto[i,iCaseM(i,j)=jNetipjPuttingthetwocasesM(i,j)=Hyper-AHyper-terminalisasetofterminalsconnectedbyover-the-cellwires.Hyper-terminals:{A,C},{B},{D,F,K},{E},{G,I},{H},ABCDEFGHIJ141536563LMNOPQRSTUHyper-terminals:{L},{M,O},{N},{P},{Q,U,V},{R,T}, MSOPMSOPLetnbethetotalnumberofpinsontheMSOPSelectionofNetNeedtodeterminewhichterminalwithinahyper-terminaltobeusedinthesubsequentchannelrouting.11Pickoneoutof11CanbetransformedtoaspecialspanningforestRuntimeofLetnbethetotalnumberofcolumns.Foreach(i,j),M(i,j)canbefoundinO(?)time.ThereareO(n)pairsof(i,j).So:Totaltime=ConnectivityAweightedmulti-graph.Eachhyper-terminalisrepresentedbyavertexandeachnetisre-presentedbyaconnectedcomponent.Takenet3asan132[8,11]2141536563312345678910aconnectedMinimumDensitySpanningForestProblem(MDSFP)Wanttoconnecthyper-terminalsofthesamenetThatis,findingaspanningtreeforeachconnectedcomponent,orfindingaspanningforestforthewholeconnectivitygraph.Thegoalistominimizethechanneldensity.Thisproblemis EfficientheuristicisViaInVLSIfabrication,theyieldisinverselyrelatedtothenumberofvias.Everyviahasanassociated thataffectsthecircuitperformance.Thesizeofaviaisusuallylargerthanthewidthofawire.Asaresult,moreviaswillleadtomoreroutingHeuristicforForeachedgee,letr(e)=d(e)/D,whered(e)isthedensityoftheintervalassociatedwithedgeeandDisdensityofthewholechannel.r(e)measurestherelativedegreeofcongestionovertheintervalassociatedwithTheheuristicsrepeatedlyremovesedgesofhighr()fromtheconnectivitygraphuntilaspanningforestisobtained.Thevalueofr(e)foreachedgeeisupdatedaftereachremoval.TwoDifferentConstrainedViaMinimizationUnconstrainedViaMinimizationForFori=1tonM(i,i)=Forj=??toFori=??toComputeM(i,i+j)ReturnM(1,n) ConstrainedConstrainedViaMinimizationGivenadetailedroutingsolution,minimizethenumberofviasbyassigningwiresegmentstodifferentlayers.Viasoccuronlyattheturningpoints.AlsocalledtheLayerAssignment1234540123454002100030210003TopologicalUVMis