博士论文-approximation algorithms for vlsi routing

《博士论文-approximation algorithms for vlsi routing》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IonI.MandoiuPh.D.DefenseofResearchAugust11,2000ApproximationAlgorithmsforVLSIRoutingVLSIRoutingVLSIPhysicalDesignElectricaldescriptionGeometricallayoutVLSIGlobalRoutingGiven:locationsfornetterminalsFind:treeinterconnectionforeachnetMinimizing:totallength(RSMTproblem)skew(

2、ZSTproblem)numberofbuffers(MSPTproblem)…OverviewofResultsSingle-netrouting:NewRSMTheuristicruns10timesfaster,andgiveshigher-qualitysolutionsthanpreviousbestRSMTheuristicImprovedZSTapproximationalgorithmsveryfast:O(nlogn)runningtimeTightanalysisoftheMSTheuristicforMSPTMulti

3、-netrouting:MCF-basedapproximationalgorithmsforglobalbufferingviabufferblocksANewRSMTHeuristicTheRSMTproblemRSMTSteinerpointMSTMSTgives3/2approximation[H76]WhyRSMT?MinimumwirelengthgivesMinimumareaMinimumresistance/capacitanceRSMTusedfor:Non-criticalnetsPhysicallysmallinsta

4、ncesKeyResultsonRSMTProblemReductiontodiscretegrid[H66]NP-hard[GJ77]Iterated1-Steinerheuristic[KR90]GreedilyaddsSteinerpointstothetreeAlmost11%improvementoverMSTonaverageFastbatchedimplementation(BI1S)Exactalgorithm:GeoSteiner3.0[WWZ98]Branch-and-cut11.5%improvementoverMSTo

5、naverageAveragespeedcomparabletoBI1S!!!TheIRVAlgorithm:High-LevelIdeaIterativemethod:ineachstepadd/removeoneSteinerpointto/fromtreeUnlikeIterated1-Steinerheuristic,donotinsistonchoosingbestSteinerpointineachstepSteinerpointtobeaddedischosenusingapowerfulLPformulationoftheSt

6、einertreeproblemingraphs,calledthebidirectedcutformulationTheBidirectedCutFormulationTheBidirectedCutFormulationTheBidirectedCutFormulationTheBidirectedCutFormulationValidcutCCTheBidirectedCutFormulation(cont.)TheBidirectedCutFormulation(cont.)LPrelaxationTheBidirectedCutFo

7、rmulation(cont.)LPrelaxationDualLPTheBidirectedCutFormulation(cont.)LPrelaxationDualLPGivesoptimumintegersolutionifallverticesareterminals,i.e.,fortheMSTproblem(E66)Integralitygapbelievedtobeverycloseto1TheRVAlgorithm[RV99]3/2approximationalgorithmforSteinertreeproblemingra

8、phsbasedonbidirectedcutformulationAppliesonlytoquasi-bipartitegraphs,i.e.,graphswi