CreatingandExploitingFlexibilityin
RectilinearSteinerTrees
ElahehBozorgzadeh,RyanKastner,andMajidSarrafzadeh
Abstract—Theglobalroutingproblemdecomposesthelarge,complexroutingproblemintoasetofmoremanageablesubproblems.Thehighcorrelationbetweentheoutputoftheglobalrouterandthedetailedrouterenablesthedesignertoefficientlyusetheglobalroutetorefinethedesignquicklybeforerunningfulldetailedroute.Hence,routabilityoftheglobalroutingsolutionisthekeyfactor.Theroutabilityofthecircuitdependsonthecongestionoftherouting.Inthispaper,westudySteinertreesintermsofroutability.Weintroducethenotionofflexibility–ageometricpropertyassociatedwithSteinertrees.WeshowthattheflexibilityofaSteinertreeisrelatedtoitsroutability.ThemaincontributionofthispaperisanalgorithmwhichtakesastableSteinertreeasaninputandmapsittoamoreflexibleSteinertree.AnyexistingSteinertreealgorithmcanbeusedfortheinitialconstructionoftheSteinertree.Experimentswithaglobalrouteronasubsetofnetsshowthatroutingcongestionisimprovedbyapproximately20%locallythroughouttheregionwherethosenetsarerouted.
I.INTRODUCTION
W
ITHtoday’ssilicontechnology,notonlyhastheeffectofinter-connectdelayontotalpathdelaybecomesignificant,butalso
dominant.Theroutermusthavegoodcontrollabilityandpredictabil-ityoncongestionandtimingissues,sothatthedesigncanconvergeontimingandinterconnectwithoutexcessiveroutingiterations.
Astandardcellrouterneedstohandleaverylargenumberofsmallstandardcells.Currentstandardcellroutersaremainlyarea-basedgriddedrouters.Theseroutersextensivelyemployrip-upandreroute(searchandrepair)algorithmstocleanupdesignruleviolations.TheadventofDSM(DeepSub-Micron)technologyhasgreatlycompli-catedthestandardcellroutingprocedure.
Routingusuallyinvolvestwosteps:globalroutinganddetailedrout-ing.Globalroutingcreatesanapproximatepathforeveryinterconnect,eventhoughthispathisnotyetphysicallyexact.Detailedroutingthenfollows,determiningthewidthandspacingneededforeachdifferentmetallayer.Theglobalroutershouldconsideranumberofdifferentmetricsincluding–butnotlimitedto–minimizingthedelayoftheeachnet,reducingthesizeofthechip,minimizingthenumberofviasanddistributingtheroutesequallyacrosstheroutingarea[19].Theimportantproblemfacingglobalroutingistodevelopsub-solutionssuchthattheycanbesolvedbydetailedrouter.Aglobalroutingso-lutionwithminimumdelayandchipsizeaccomplishesnothingifthedetailedroutercannotfindasolution.Hence,routabilityoftheglobalroutingsolutionisthekeyfactor.Routabilityofthecircuitdependsonthecongestionoftherouting.Mostglobalroutersusecongestionmapstohelpdesignersunderstandtheresultsofglobalrouting.Ifthedesignappearscongestedaftertheglobalroute,designersalterthetoplevelfloorplanorplacementofcellsinsidetheblocktogetabettercongestionbeforestartingadetailedroutingjob.
Steinertreeconstructionisanessentialpartofglobalrouting(theproblemisformallydefinedlaterinSectionII).TheearlysetofSteiner
ThisworkwaspartiallysupportedbyNSFunderGrant#CCR-0090203.ElahehBozorgzadehandMajidSarrafzadeharewithComputerSci-enceDepartmentatUniversityofCalifornia,LosAngeles.(email:elib,majid@cs.ucla.edu)
RyanKastneriswithDepartmentofElectricalandComputerEngineeringatUniversityofCalifornia,SantaBarbara.(email:kastner@ece.ucsb.edu)
treealgorithmsfocusedonminimizingthetotalwirelengthastheob-jective(see[19]foranoverview).Aswiredelayhasbecomeincreas-inglymoreimportant,Steinertreealgorithmshavefocusedonmini-mizingthedelayofthenet.Recently,therehasbeenmuchfocusonalgorithmswhichsimultaneouslyconsiderbufferinsertion,wiresizingand/orSteinertreeconstruction[11],[15],[18].
Typically,criticalnetsareasmallsubsetoftheoverallnumberofnets.However,thenumberofcriticalnetsareincreasingwithtoday’sDSMtechnology.Thedelayofnon-criticalnetsisnotcrucialtotheperformanceonthecircuit.Therefore,thesenetsshouldberoutedinamannerwhichincreasesthelikelihoodthatthedetailedroutercanfindafinal,validsolution.Yet,wedonotknowofanypreviousSteinertreealgorithmswhichexplicitlyconsiderroutability.Mostlyroutabilityisreferredtoasthedensityofroutingedgesinglobalrouting.Thereexistmanydifferentglobalroutingalgorithmsbothinindustryandresearch.Inmostofthesetechniques,thecongestionishandleditera-tively.Thereareothertechniqueswhicharenotbasedonnetordering.In[5],aSteiner-treebasedglobalrouterispresented.TheproposedalgorithmfindsaweightedSteinertreeforanetwhiletheweightofaregionrepresentsthedemandoftheregion.Theaimistooptimizethelengthanddensitysimultaneously.In[6],aperformance-drivenSteinertreealgorithmisproposed.TheobjectiveistominimizethedelayfunctionofSteinertree.Globalroutingproblemisformulatedasmultiterminalmulticommodityflowproblem.Theobjectiveistomax-imizetheoverallroutabilitybyminimizingtheedgecongestionforasetofnets.In[3],anapproximationalgorithmformulti-commodityflowisusedforglobalroutingwhichcanreducethecongestionsig-nificantly.Inthatpaper,itisassumedthatthealgorithmcanqueryasubroutetogiveaSteinertreeofanetwithfixedlength.
Inthiswork,westudySteinertreesintermsofroutability.Wein-troducethenotionofflexibility–ageometricpropertyassociatedwithSteinertrees.Flexibilityinroutingedgeshasbeenexploitedinmanyoftheabovementionedexistingresearchtoimprovetheroutingcon-gestion.Tothebestofourknowledge,therehasnotbeenanyworkwhichtriestomaximizetheflexibilityinroutingtrees.Inthiswork,ourfocusisnottoproposeanewglobalroutingalgorithmortode-velopanewalgorithmtoconstructanewSteinertreebuttointroduceandunderstandthepropertyofflexibilityforSteinertrees.Withnodeepunderstandingofflexibility,thispropertyhasbeenexploited(notfully)inseveralglobalroutingtechniques.Forexample,flexibilityinSteinertreeshasbeenexploitedinthetiming-drivenglobalroutingproposedin[10].Theglobalroutertriestoreduceroutingconges-tionbytakingadvantageofdifferentpossibleroutesforedgescalledsoftedges.WeshowthattheflexibilityofaSteinertreeisrelatedtoitsroutability.Specifically,aflexibletreeislesspronetobeingroutedthroughacongestedregion.Wedemonstratethisconceptbyconstruct-ingflexibletreesinastate-of-the-artglobalrouter.Globalrouters(e.g.[10],[8])cantakeadvantageofflexibilityinflexibleroutingtreestoreducethecongestionlocally.
Themaincontributionofthispaperisanalgorithm,whichtakesaSteinertreeasaninputandproducesamoreflexibleSteinertree.Theonlyrestrictionontheinitialtreeisthatitmustbestable(stabilityisdefinedinSectionII-B).Thenew,flexibletreeisguaranteedtohavethesametotallength.AnyexistingSteinertreealgorithmcanbeusedfortheinitialconstructionoftheSteinertree.Asanexample,ourtechniquetomaponeSteinertreetoanothertreewithsamelengthbutmoreflexibilitycanbeusedinqueryingthesubroutinetoobtainnewSteinertreesforthenetsintheapproximationalgorithmdescribedin[3].HereitmeansthatnewSteinertreemightbefoundbychangingtherouteofflexibleedgesforthenetonly.Asaconsequence,ouralgorithmcanbeappliedorintegratedintoglobalroutingalgorithmstoreducethecongestionlocally.ThepreliminaryversionofthisworkhasbeenpublishedinDAC2001[7].In[7],onlytheconceptofflexibility
IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS—...2
inglobalroutingisproposed.Thedetailedanalysisofcreatingandexploitingflexibilityispresentedhereinthiswork.
Thepaperproceedsasfollows:InSectionII,wegivesomebasicroutingdefinitions,definetheminimumSteinertreeproblemandsomeassociatedpropertiesofSteinertreesincludingflexibility.InSectionIII,theproblemofgeneratingflexibilityinSteinertreesisformulated.Thenouralgorithmisdescribed,whichtakesanexistingSteinertreeasinputandincreasesitsflexibility.InSectionIV,experimentalre-sultswhichstudytheimpactofflexibilityduringglobalroutingarepresented.WeconcludeandgivesomepossibilitiesforfutureworkinSectionV.
II.PRELIMINARIES
A.GlobalRoutingDefinitions
AgridgraphisagraphG(V,E)suchthateachvertexcorrespondstoapointinaplane(anexampleisshowninFigure1).Anet
isanunorderedsetof=
pointsonagridgraph.Asinglepointofthenetisreferredtoasater-minal.Aroutingofanetisasetofgridedgessuchthattheterminalsarefullyconnected.Integergridroutingisassumed.Therouteedgesofanetarethesetofedgesusedintheroutingofthatnet.
Aglobalbinisarectangularpartitionofthechip.Bypartitioningthechipintomanyrectangularregionsandplacingthecellsintotheseregions,wehaveaplacementusingglobalbins.Theboundariesoftheglobalbinsareglobalbinedges.
(2)
whereisthenumberofbinedges.Thetotaloverflowreflectstheshortageofroutingresourcesforaparticularsetofedgecapacities.Theobjectivesofourglobalrouterisalinearfunctionoftheoverflowofarouteandtheroutelength.Ourindustrialexperienceshowsthattotaloverflowisagoodmeasureofcongestion[8].
B.RectilinearSteinerTree
Givenanet(setofnodescalledterminalsofthenet)embedded
,arectilinearSteinertree(RST)isatreeinagridgraph
interconnectingtheterminalsofandsomearbitrarypoints
.ThepointsareknownastheSteinerpoints(alsocalledSteinernodes)of.TherectilinearSteinertreeproblemistofindarectilinearSteinertreeofminimumlength(SteinerMinimalTree).ThelengthofaSteinertreeisthesumofthelengthoftheedgesofthetree.In
metricrectilinearSteinertreeproblem,thedistanceisdefinedin
(rectilinearmetric),inwhichthedistancebetweentwonodesisthesumofthedifferenceoftheir-coordinateand-coordinates.TheconstructionofaRectilinearSteinerMinimalTree(RSMT)hasbeengivenmuchattentionandshowntobeNP-Complete.[14].
Formally,asegmentisahorizontalorverticallinesegmentconnect-ingitstwoendpointsintheplane.Degreeofeachpointisatmost.Steinerpointshavetheedgedegreeofatleast.corner-pointisapointwithdegreewithnon-collinearsegmentsthatisnotaterminal.Twopointsaredirectlyconnectediftheyareconnectedbyasequenceofoneormoresegmentsincludingonlycorner-points.Sucharoutehasstaircaseshape.
ForanygivenrectilinearSteinertree,thereisacorrespondingtree
),whichiscalledtopology.Verticesofcorrespondgraph(
totheterminalsandSteinerpointsofRST.Notethatthecorner-connectsverticesandpointsarenotverticesofthegraph.Edge
iffthecorrespondingpointsaredirectlyconnectedin.Aslongastheedgesbetweentheverticesremainconsistent,thetopologyisconsideredunchanged.InagivenRST,locationofSteinernodescanchangesuchthattopologydoesnotchange(seeFigure3).Similarly
,thedegreeofverticesisboundedby.IftheSteineringraph
pointhasedgedegreeof,itiscalledcross-point.T-pointisanodewithdegreeinwhichoneofincidentedgesisperpendiculartotheothertwoincidentedges.
In[2],Hwangetal.definetwodifferenttransformationsforrec-tilinearSteinertrees:flippingandsliding.Eachtransformationmapsonesuchtreetoanotherwithoutmovingthepositionsoftheterminalsandwithoutincreasingthelengthofthetree.Dependingonthedi-rectionoftransformation,therearedifferentslidesandflipmoves.Inslide,asegmentperpendicularandincidenttoparallelsegmentsisreplacedbynewsegmentwhichisstillperpendicularandincidenttotheparallelsegments.SlidetransformationandFliptransformationareshowninFigure3.
Global BinsCells( a )Global Edges(b)Fig.1.(a)PlacementofCellsintoGlobalBins.(b)TheCorrespondingGridGraph.
Inthispaper,weassumethataglobalplacementofcellsandtheirinterconnectionsaregivenbysomeplacementengine.Eachcellisassumedtobeplacedinthecenteroftheglobalbin.Theglobalbinsandedgescanbetransformedintoagridgraph(seeFigure1).Theinterconnectionsbetweenthecellscanbemodeledbynets.
Thecapacity(alsoknownassupply)ofedgeis.Itisthemaxi-mumnumberofnetsthatcanberoutedover.isafixedvaluethatisbasedonthelengthoftheedgeandthetechnologyusedincreatingthechip.Theroutingdemandof,specifiedas,isdefinedasthenumberofrouteedgescrossingedge.Similarly,thedemandofavertexis.Herethedemandcorrespondstothenumberofroutesthatpassthoughthevertex(equivalentlytheglobalbin).Anedge
.Formally,theoverflowofanisoverflownifandonlyifthe
edgeis:
if
otherwise
overlape(1)
eBounding boxof edge ebounding box of edge eisathresholdvaluewhichallowstogoabovewithoutanoverflowpenalty.isusedsinceyoucanoftenrouteuptonetsthoughneighboringbinswithoutaffectingthecongestionofthosebins.isusuallyasmallconstant(between2-5).Usingtheglobalbinandglobaledgenotation,thetotaloverflowofaroutingis:
Stable RSTUnstable RSTFig.2.ExamplesofStableandUnstableRSTs.
IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS—...3
Hoetal.introducedthenotionofstabilityunderre-routinginanRST[16].ARSTisstableifthereisnopairofedgessuchthattheirboundingboxesintersectoroverlapexceptatacommonendpoint(ifany)ofthetwoedges.Equivalently,astableRSTwillnothaveover-lapswhentheedgesareroutedwithminimumlength.Fromthispointforward,anyreferencetoaRSTassumesthatthetreeisstable.Figure2showsexamplesofstableandunstableRSTs.C.PatternRouting
Sincewearefocusingonroutability,wedefinethecostoftheSteinertreeasalinearfunctionoftheoverflowandroutelength.Weneedtoassignarouting(rectilinearroute)totheedgeswhicharenei-therverticalnorhorizontal(e.g.edgeinFigure2).Wechoosetopatternroutesuchedges.Patternroutingisthenotionofusingpre-definedpatternstoembedanedgeonthegridgraph.UsuallythesearesimplepatternssuchasaL-shaped–1-bend–oraZ-shapedpat-tern–2-bends,routerestrictedwithinboundingbox.Inthispaper,werestrictourpatternroutedefinitiontoL-shapedorZ-shapedpatterns.Patternroutinghasmanybenefits.First,ithasalowerruntimecom-plexitywhencomparedtomazerouting[13]–acommonlyusedrout-ingalgorithm.Second,apatternroutednethassmalldelaysinceitintroducesaconstantpredeterminednumberofviasandroutesthenetwithminimumwirelength.Finally,byproperlychoosingasubsetofnetstopatternroute,theglobalroutingsolutionismorepredictablewithouthinderingtheoverallqualityoftheroutingsolution;thisgiveshighlevelCADtools(e.g.placementengine,floorplanner)higherac-curacywhenestimatingroutingmetricssuchascongestion,routingareaandwirelength[8].
flips1(a)T1(b)T2Fig.3.(a)RSTWithFlexibleEdges.(b)RSTWithNoFlexibleEdges.
Additionally,afunctioncorrespondingtoedgeshouldhavethefollowingproperties:
whenor.
isamonotonicallyincreasingfunctionofand.
Twosuggestedflexibilityfunctions,and,areshowninEqua-tions5and6.
iforOtherwise
(5)
(6)
Functioncorrespondingtoflexibleedgereturnsthevalueequaltohalfofthelengthoftheboundingboxofedge.Thevalueof
correspondingtoedgeistheareaoftheboundingboxfunction
ofedge.TheflexibilityofaSteinertreeiscomputedbysummingtheflexibilityoveralltheedges.Equation7definestheflexibilityonasubtree.Anumberofotherfunctionscanbeintroduced.
D.Flexibility
Inthissection,wedefinethepropertyofflexibility.WearguethatflexibilityrelatestotheroutabilityoftheSteinertree.
Aflexibleedgeisanedgebywhichtwonodesaredirectlyconnectedwithmorethanonesegment.Thereforetheflexibleedgehasoneormorecorner-points(staircaseshape,L-shapedorZ-shaped).Flexibleedgesallowmorethanoneminimumlengthroute.Ifanedgeisroutedwithminimumrectilinearlength,therouteiscontainedwithintheboundingboxof.Aninflexibleedgehasonlyoneminimumlengthrouting.Givenaflexibleedgewithcoordinatesofitstwoend-and,andaredefinedasfollows:pointsas
(7)
III.CREATINGFLEXIBILITYINRECTILINEARSTEINERTREESInthissection,wepresentanalgorithmwhichmapsagivenrectilin-earSteinertreetoanotherRSTwithmaximumincreaseintheflexibil-ityoftheSteinertree.First,weformallydefinetheproblem.Next,we
describeouralgorithmtomaximizetheflexibilityofagivenRST.Ouralgorithmsolvestheproblemoptimallysubjecttoasetofconstraints.A.ProblemFormulation
GivenastableRST,
MapittoastableRSTsuchthat,theincreaseinflexibilityoftheRST,ismaximized,Subjectto:
-Topologyandstabilityremainunchanged,
-Eachedgeisroutedwithminimumrectilinearlength,-Noedgeisdegradedinflexibility1.
Theorem1:InastableRST,iftheSteinerpointhasaflexibleedge,thedegreeofis.OnlyoneflexibleedgecanbeincidenttoaSteinerpoint.
Proof:MorethanoneflexibleedgecannotbeincidenttotheSteinerpointduetothestabilityoftheRST.Theexamplesofstableandnon-stableSteinerpointsinatreeareshowninFigure4.
NoSteinercross-pointcanhaveaflexibleedge.SteinerpointwithedgedegreeiseitheraT-point(notincidenttoaflexibleedge)orincludingaflexibleedge.WhenaSteinerpointisincidenttoaflexibleedge,werefertothatpointasaflexiblepoint(seeFigure4).
Definition:TheSteinerpointinastableRSTismovableifwecanmovetoanyotherlocationwhilekeepingtheRSTstableandthe
(3)(4)
andarecalledthe-coordinateand-coordinateofedge,respectively.Thenumberofdistincttwo-bendroutes(equivalentlyZ-andthenumberofdistinctshaped)withminimumlengthis
one-bend(equivalentlyL-shaped)routeswithminimumlengthis.Inthispaper,theflexibleedgesareshownasdiagonaledgesinthefigurestoshowthattherearemorethanonepossiblerectilinearroutesforsuchanedge.
LookingatFigure3,weshowtworectilinearSteinertreesforthesamenet.Onetreehassomeflexibleedgeswhiletheotherhasonlyinflexibleedges.Bothtreeshavethesamerectilinearlengthandtopol-ogy.Assumethattheshadedareaiscongested.Theflexibletreeisabletoavoidthecongestedregionwhiletheinflexibletreehasnochoicebuttoberoutedthroughthecongestedareaifeachedgeisroutedwithminimumrectilinearlength.
Weneedtodefineafunctionwhichevaluatestheflexibilityofagivenedge.Thefunctionshouldreflecttheroutabilityoftheedge.
IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS—...4
IIImove PPP∆lPPPIIIIVP1Flexible and Stable PP1move P1P1stablestableFig.7.MovingSteinerPoint
AlongDirection.
PPUnstable PT-point Stable P
Fig.4.ExamplesofStableandUnstablePoint
inaRST
3241P56Fig.5.SixDifferentDirectionsforMovingSteinerPointp.
thetreeisunstableunlesspointismovableindirectionaswell.By
inparallelwithindirection,treewouldremainstablemoving
whilethetopologyalsoremainsunchanged(seeFigure7).Thisshowsthattwoincidentnodes(i.e.anedge)havetobemoved.Inotherword,movingonenoderesultsinmovingoneofthenodesincidenttothat.BasicallypointneedstobeaT-pointorflexiblepointwhereinbothcasesthetwocollinearincidentedgesarealongdirection.Movingtowardsdirectionissimilartodirection.
Notethatanedgecanalsobemovedonlyfromoneendpoint.Whenanedgeismovedfrombothends,theincidentedgestobothendnodesoftheedgearemovedfromoneend.Wedonotconsidersuchedgesasmovableedge.Wewillseelatersuchedgescanbeflexiblecandidatesorparalleledgesofmovablesets.
Theorem3:AnedgeinastableRSTismovablealongdirectionifbothverticesincidenttothesegment
areSteinerpointswithedgedegree.
haveincidentedgestowardsthesamedirection,i.e.direction.Thatisthedirectionofmoveforedge.
topologyunchanged.Similarly,anedgeismovableifcanbemovedandtheresultingRSTremainsstablewithnochangeintopology.Theorem2:ThereisnosinglemovablenodeinastableRST.Atleasttwoadjacentnodes(twoSteinernodes)havetobemoved.
Proof:Inordertomakesegmentmoreflexible,canmoveinsixdifferentdirections(seeFigure5).ChangingtheconnectivitybetweenSteinernodesandterminalsisnotallowed.Todiscovertherequirements,themovingofnodealongallpossibledirectionsisinvestigated.Figures5,and7arereferredduringtheproof.Bymovingtowardsanyofdirections,theRSTgetsunstableunlessthetopologyoftheRSTchanges.InFigure6,pointismovedtowardsdirection.Atmostoneedgewouldbelocatedontherightsideofandtherestwillbeontheleftsideoforalongtheverticalborders.Onlyoneoftheedgesontheleftsideofcanbeflexibleandonlyoneedgecanbehorizontal.InalldifferentconfigurationsoftheedgestheRSTwouldbeunstable.
Ifnodeismovedtowardsdirection,noedgeindirectionshouldexist.Otherwise,bymovingpoint,RSTgetsunstable.Therefore,pointcannotbeaT-pointwiththecollinearincidentedgesperpen-diculartosegment.Bymovingpointtopointindirection,
e1111000000001111000011110000111100001111000011110000111100001111yP’PFig.8.MovableSegment.
Thisassumptionslightlysimplifiestheproblem.Theproblemcanbeex-tendedwithoutit.
sPsmove PPProof:ConsiderFigure8.AccordingtotheproofofTheorem2,
anedgeismovableineitherhorizontalorverticaldirectionwhilebothendsaremoved.Whennodeismovedtowardsdirection,therehastoexistanedgeincidenttothenodetowardsdirection.Ifthereisnoedgeincidenttotowardsdirection,theboundingboxesoftheedgesincidenttowilloverlapafteredgeismovedtowarddirection.ThatviolatesstabilityofRST.Therefore,theremustbeanedgeincidenttoindirection.SinceRSTisstableandedgedegreeofisthree,theotheredgeincidenttoisindarkenedregionshowninFigure8.Therefore,Steinerpointhasanincidentedgetowards
ismovable.directionandtheedge
AccordingtoTheorem3,theconditionsunderwhichanedgecanbemovedissimilartoslidetransformationinrectilinearSteinertree.Thedifferenceisthatinmovableedgetopologycannotchange.ThereforebymovingthemovableedgeinagivenrectilinearRST,itismappedtoanotherRSTwithsametopology.Wecanrefertothemovablesegmentasslidingsegmentaswell.
Corollary1:Onamovableedgeslidetransformationcanbeap-pliedwhiletopologydoesnotchange.
Asubtreeconsistingofmovablesegmentandasetofedgesadja-.centto,,canbedefinedasaMovableSet
Fig.6.UnstableMove
,
IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS—...5
Sf1S(a)(b)Sf3Sf4f2(c)(d)Fig.9.MovableSetWithMovableEdge.
parallel edgeh1flexibleh2parallel edgemovable segmentflexible candidateFig.10.FlexibleSegmentGeneratedbyAlgorithmGenerateflexibleTree.
,
,
flexiblecandidateis,
,
whereisthesetofalladjacentedgestoincludingsegment.
consistsofthreedifferentedgesubset.isthesetofthetwo
paralleledgesaccordingtoTheorem3.
isthemovablesegment,i.e..
isthesetofflexiblecandidatesamongtheadjacentedgesto.Bymovingedgetheflexibilityofedgesinincreases.isthe
setofedgesexcludingtheonesbelongingto,
,and.Foranexampleofamovableset,seeFigure10.
Themovablesetisasubtreewithleavesandtwointernalnodes.ItissimilartodefinitionoffullcomponentinSteinertree.Fullcom-ponentisdefinedasasubtreewithleavesofterminals[2].However,inamovableset,theleavesneednottobetheterminals.
Corollary2:Iftheleavesofsubtreeofmovablecomponentaretheterminals,themovablesetisafullrectilinearSteinercomponentwith4nodes.
B.Algorithm
Figure9showsdifferentmovablesets
.Themovablesetshavedifferentsubsetsofedgesin.Theedgesadjacenttoaredifferentintermsofflexibility.ThemovablesetinFigure9(a)hasno
flexiblecandidatei.e.
.Theothermovablesetshaveatleastoneflexiblecandidate.Theflexiblesubsets()are
9(b),
inFigure9(c)andinFigure9(d).EdgeinFigureisalreadyaflexibleedge.Howeverbymovingsegmenttheflexibilityofcanincrease.Edges,,andbecomeflexibleaftersegmentismoved.InFigure9(a)movingsegmentproducesnoadditionalflexibility.Intheothercases,theflexibilityoftheRSTincreasesbymovingsegment.ThisimpliesthatatleastoneflexiblecandidatehastoexistinamovablesetinordertoincreasetheflexibilityoftheRSTbymovingthemovableedge.
Theorem4:InastableRST,bymovingamovableedge,flexibleedge(s)canbegeneratedorflexibilityofanedge(s)canincreaseifatleastoneofthetwoverticesincidenttothemovableedgeisaflexiblenodewithanincidentedgetowardsthemovingdirection.
Proof:IfbothendpointsofthemovingedgeinamovablesetareT-points,noflexibleedgecanbegeneratedbymovingthemovableedge.
InordertoincreasetheflexibilityofaRST,wefirstneedtosearchformovablesetswhichhavethepotentialtogenerateflexibleedges.
MovablesetsinaRSTcanbefoundin
,whereisthetheedgesetoftheSteinertree.AccordingtoTheorem3,eachedgeischeckedwhetheritismovablewithincidentflexiblecandidate.
Whenamovablesetisfound,themovablesegmentcanmovealongtheparalleledges.Themaximummovementistheminimumlengthofthetwoparalleledgesincidenttothemovablesegment.Inotherwords,thisisthemaximumrangeforslidingtransformationonmov-ablesegmentwithoutchangingthetopologyofRST.InFigure10,the
maximumlengthofslidingis
whereandarethelengthoftheparalleledges.Sincetopologyshouldnotchange,thesegmentcanmoveasfarasonegridbeforeitreachestheendnodeofanyofthetwoparalleledges.AccordingtoTheorem3,bymovingamovableedge,theflexibilityoftheRSTimproveswithoutchangingthewirelengthandtopology.However,bymaximizingtheflexibilityofamovableset,wemayrestricttheflexibilityofanothermovableset.Wediscussthissituation,calledoverlap,next.
C.OverlapinMovableSets
OnceeveryindividualmovablesetisfoundinagivenRST,theques-tionis:Arethemovablesegmentsindependentandbymovingallofthem,canmaximumflexibilitybeobtained?Inordertoanswerthequestion,weneedtoseehowmovablesegmentscanoverlap.
Whenthereisnooverlap,weeasilycomputetheflexibilityfunc-tionforeachmovingsegment.Sincetheflexibilityfunctionismono-tonicallyincreasingintermsof-coordinateand-coordinateofthe
edges,themaximumof
occursifeachmovingedgeismovedtoitsmaximumlimit.Unfortunately,theflexibilitycannotbecomputedindependentlyfortwooverlappingsegments.
Twomovablesegmentshaveoverlapwitheachotherineitherofthetwofollowingcases:
1)Themovementofmovableedgeislimitedbythemovementoftheothermovableedge(Figure11).
2)Movingthemovableedgeincreasesflexibilityofanedgewhilethemovementofsomeothermovablesegmentleadstoadecreaseintheflexibilityof(Figure12).
Twomovablesetsintersectiftheircorrespondingedgesetsshareacommonedge.Therearesixpossibleintersectionsbetweenanytwomovablesets.Onlythreeofthemcauseoverlapbetweenthesegments.
Let
bethepairandofincidentbenodestwoformovablesegmentsegmentsandandandrespectively.Thesixdifferentintersectionsbetweenthetwosetsareasfollow:1).
Segmentandsegmenthaveasameparalleledge.a).
Themovingdirectionofbothmustbethesame.Other-wisethedegreeofcannotbe3.Thisisoverlaptype.ThiscaseisshowninFigure11(a).Inordertohavethesametopologyandmaximizetheflexibility,theamountofmovementforeachsegmentwouldbe:
b)
isthesetofnodes.
incidentto.Ifthemovingdirec-tionofbothisthesame,nooverlapwouldoccur(Figure11
IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS—...6
s2l(s2)l(s1)s2s1s2(a)(b)w3s1w1s1l1s3Dl2s2s2w2w1w2(c)(d)Fig.11.IntersectionBetweenTwoMovableSetsWithSharedParallelEdge.
w3lxlxlylyw1w2( 1 ) ( 2 )Fig.12.IntersectionWhenaParallelEdgeBeingAnotherMovingEdge.
(b)).Whentheymoveinoppositedirections,overlapcanoccur.ThetwocasesinwhichoverlapoccurareshowninFigure11(c)and(d).
InFigure11(d),thesegmentoverlapswithaswell.Thiscaseiscomplicatedwillbediscussedlater.Thisisacombinationofoverlaptypesand.
InthecaseshowninFigure11(c),overlapcanoccuriftheconditionbelowholds.
Thisisoverlaptype.
2)
Themovingedgeistheflexibleedgeofsegment
.Thisis
sameasintersection
.3)
Themovableedgeofasetisaparalleledgeofanotherset.The
twocasesareshowninFigure12.Thefirstcasedoesnotover-lap,butthesecondoneissimilartotheoverlapshowninFigure11(d).4)SuchacasewillnothappensincetheRSTisstable.
5)
Theparalleledgeofisaflexibleedgeinset.Theconfigu-rationissameastheoneshowninFigure12(2).
6)
ThiscaseisshowninFigure13.Figure13(a)showswhentwosetshavethesameflexibleedgeinthesamemovingdirection.Inthiscasethereisanothermovablesetbetweenthose,whichhasoverlapcasewithbothofthem.Thisisachainofcasewithoverlaptype.ThereisnooverlapinthecaseshowninFigure13(b).
Accordingtothestudyonallpossibleintersectionbetweenthetwomovablesets,therearetwotypesofoverlapthatcanoccur:
OverlapType1:Itoccurswhenaparalleledgeoftwomovablesetsisthesameandinequalitiesmentionedinintersection1hold.OverlapType2:Itoccurswhenflexibleedgeofamovableseg-s1s2s1s2(a)(b)Fig.13.TwoMovableSegmentSharingaFlexibleCandidate.w3s5w5w4s4w2s2s3lxlyw1s1w’1Fig.14.MaximumOverlapofaMovableSetwithOtherMovableSets.
mentisaparalleledgeoftheothermovingset.
Theorem5:Eachmovablesegmentsetcanhaveatmosttwoover-lapsoftype1andtwooverlapsoftype2.
Proof:Sinceeachmovablesethastwoparalleledges,eachcanhaveoverlap(type)withanothermovableset.Amovablesethasatmosttwoflexibleedges.Therefore,atmosttwooverlapsoftypecanoccurbyflexibleedgesbeingtheparalleledgesofthetwoothermovablesets.Overlapsmorethanleadstoedgedegreeforthesteinernodesattwoendsofmovableedgeswhichcontradictswiththepropertiesofmovableset.
InFigure14,movableset,,andoverlaps.Twowithofthesegments
overlaps
areoverlaptypeandtheothertwooverlapsareoftype.
WhenmovablesetsarebeingfoundinaRST,overlapsamongthemovablesetcanbedetectedaswell.Whenanedgeisbeingre-visiteditmeansthattheedgehasalreadybeenrecognizedasamemberofanothermovablesetwhichhasalreadybeenfound.Insuchacasethealgorithmcheckswhethersuchanintersectiongeneratesoverlap.SinceeachedgecanparticipateatmostinmovablesetsaccordingtoTheorem5,thecomplexityofthealgorithmtofindthemovablesets
andtheiroverlapstillremains
.Thefirstloopofthepseudo-codeshowninFigure16findsthemovablesetsandtheoverlapsamongthesets.
Inbothtypesofoverlap,weneedtomeasuretheflexibilityinordertodecideonmovingthemovablesegments.Thebehavioroftheover-lapwilldependontheflexibilityfunction.Ifthemovablesetsover-lapwitheachother,themaximumofflexibilityfunctioncannotbeobtainedbymaximizingtheflexibilityfunctionforeachmovableset.Thereforedealingwithoverlapsdependsonthedefinitionofflexibilityfunction.WeshowhowtoresolvetheoverlapifflexibilityfunctionsintroducedinSectionII-Dareused.
ConsidermovingsetsshowninFigure15.Inbothfigures,segmentoverlapswithsegment.Wewillstudyhowthedecisiononmov-ingtheoverlappingedgesismadebyusingeachflexibilityfunctionmentionedinSectionII-D.Notethatinthefollowingdiscussionvari-ablesorisusedtodefinetheamountofslidingforthemovable
segmentinmovableset
.Theyarenotrelatedtocoordi-IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS—...7
Algorithmw2s2y2w3Generate_flexible_treeInput: ERST- Edge set of an RST of a multi-terminal net.DxOutput:RSTnews2ys1y1s1w1w1for each edge ein ERSTifw2Is_movable(e) and Flexible_exist(e)Create_movable_set(e,movable_set(e)Check_and_update_overlap(movable_set(e), overlapList)(a)(b)for each movable_set M = ( s, Es) ifNo_overlap(M, overlapList)Fig.15.ExampleofOverlapType1(a)andOverlapType2(b)forMovable
Setsand.
Move_segment(s, RSTnew)Solve_overlap_and_move(overlapList,RST )newnatesofthepointsontheplanebutvariablesoftheflexibilityfunctions
andcorrespondtothe-whenmovablesegmentismoved.
coordinateand-coordinateofedgebeforeanysegmentismoved.
iforOtherwise
Thisfunctionisadiscontinuousfunctionator.IfoverlapoccursliketheoneshowninFigure15(a),theflexibility
,aunionsubtreeofoverlappingmovablefunctionofthesubtree
setandmovableset,willbe:
return RSTnewFig.16.AlgorithmGenerateflexibletreePseudo-code.
(10)
(8)
andand.Maximumofoccurswhen
IfoverlaptypeoccursasshowninFigure15(b),theflexibilityof
isformulatedas:subtree
if
ifif
(9)
occurswhenand(Maximumof
).Thevalueofisnotfixed,butithastobenonzero.Thevalueofxcanbechosensuchthatthesegmentpassesthroughlesscongestedarea.
isusedastheflexibilityfunction,inthecaseofoverlapWhen
typeorinthesubtreesofRST,thedecisiononmovingthemov-ableedgescanbefoundbysolvingalinearequation.Iftherearemorethanoneoverlapsbetweenthemovablesetsinsubtree,thefunction
isformulatedintermsofvariablesassociatedwitheachmovable
ismaxi-set.Thevaluesofthevariablesareassignedsuchthat
ismaximizedwhenthevari-mized.Inbothtypesofoverlap,
ablesarenon-zero.Therefore,whenresolvingtheoverlapamongasetofmovablesets,weusethecasewithnon-zerovariablesinequation
.ThereforeG(T)canbedefinedasaequationofsetofinde-pendentvariableswhichcanbemaximizedinlineartimeintermsofnumberofvariablesintheequation.
Thisfunctionisanonlinearcontinuousmonotonicallyincreasing
and.Ifoverlaptypeoccurs(Figure15(a)),functionintermsof
canberepresentedas.Thenthefunctionwillbelinearintermsofandtheproblemcanbelinearlysolved.Thelinearsolutionwouldleadtoacceptanceofjustoneofthetwomovingsets.InthecaseofoverlaptypeasshowninFigure15(b),theflexibilityfunctionoftwooverlappingmovingsegmentswillbe:
TheHessianmatrix()isindefinite.Thefunctioncreatesasad-dlepoint.Themaximumoccursonthelimitsofxandy.SofourpointsneedtobecheckedtofindthegreatestvalueforG.
NotethatforthecasewhenasegmenthasoverlapsfrombothtypesononeparalleledgeasshowninFigure11.d,thevariableassociatedwithmovablesetcanbedefinedintermsofthevariableassociatedwithmovingsegment.Thereforetheproblemwillbereducedtofindingamaximumofafunctionoftwovariableswithoverlaptype.InFigure16,algorithmGenerateflexibletreeispresented.Basi-cally,thefirstpartfindsmovablesets(MovableList)andtheoverlapsbetweenthesesets(overlapList).Usingappropriatedatastructures,thefirst“for”loophasO()time.Thesecond“for”loopmovestheindependentmovablesetsindividually.solveoverlapandmove()resolvestheconflictbetweenoverlappingsetswhilemaximizingtheflexibilityoftheRST.Thecomplexityofthesecondpartdependsonthecomplexityoftheflexibilityfunction.
IfthereisachainofconfigurationsasshowninFigure14andisusedasaflexibilityfunction,theexpressionofflexibilityfunctionwillincludeallthequadratictermsofoverlappingsets.Findingthemaximumofisexponentialintermsofnumberofmovablesetsintheoverlappingchain.Weexpectthesechainstobeshortinmostapplications.
Theorem6:ThealgorithmGenerateflexibletreesolvestheprob-lemofmaximizingflexibilityinagivenRSTunderthedefinedflex-ibilityfunctionandconstraintsasformulatedinSectionIII-A.Ifflexibilityfunctionisalinearfunction,thealgorithmrunsinpolyno-mialtime.Ifisquadraticfunctionthealgorithmcomplexitycanbepseudo-polynomialintermsofnumberofmovablesetinoverlappingchain.
),thoseProof:Afterallthemovablesetarediscovered(
movingedgeswhichdonotoverlapwithanyothermovablesets(in-dependentsets)aremovedasfaraspossible.Forthosewhichoverlap,functionsolveoverlapandmove()findsthemaximumvalueofflexi-bilityfunctionfortheoverlappingsegmentsanddeterminesthelimitofmoveforeachofthetwosegments.Accordingtoaforementioned
pro-detailsaboutresolvingtheoverlap,themaximumvalueof
videsthemostflexibleconfigurationforsubtree.Thereforetheal-gorithmisabletofindthemostflexibleRST.Thetimecomplexityofthealgorithmdependsontheflexibilityfunction,,Ifislinear(like
IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS—...8
),theoverlapsaresolvedinpolynomialtimeasdescribedabove.In
andchainofmovingthecasewhereflexibilityfunctionis
edgesoverlap(type),themaximumflexibilityisfoundbycheckingallthemaximumlimitofoverlappingmovableedges.Thereforethecomplexitycangrowuppseudo-polynomiallyintermsofwhereisaglobalrouterbasedonmazerouting.Labyrinthsequentiallymazerouteseverynet.Then,arip-upandreroutephaseisappliedtodealwiththenetorderingproblem.
Ourexperimentsfocusedon4-terminalnets.Wechoosethe4-terminalnetswhichhaveonlyonemovableedge.Werefertothisthenumberofmovablesetsinoverlappingchain.
ItisimportanttomentionthattheRSTresultedfromalgorithmGen-erateflexibletreehasthesamewirelengthastheoriginalRST.ThereisnodegradationinthelengthofthegivenRSTwhileflexibilityismaximized.WehaveshownthatmovablesetsaretheonlyfeasiblemovesforSteinernodessothattheresultingRSTisstillstablewiththesametopology.Inaddition,sinceeachedgeisroutedinminimumrectilinearlength,totalwirelengthwillremainthesame.Inouralgo-rithm,therectilinearlengthofflexibleedgesareincreasedasmuchastherectilinearlengthofparalleledgesisdecreased.Therefore,thetotalwirelengthremainsthesame.
IV.EXPERIMENTS
Inthissection,weperformexperimentswhichattempttoshowtherelationshipbetweenflexibilityandroutability.First,wepresentthecharacteristicsofthebenchmarks.Then,wepresentexperimentstoshowthatflexibilityisrelatedtoroutability.A.Benchmarks
Toperformourexperiments,weusedMCNCstandard-cellbench-markcircuits[17]andbenchmarksfromtheISPD98suite[12].ThecharacteristicsofthecircuitsareshowninTableI.ThecircuitswereplacedintousingtheDragonglobalanddetailedplacementengine[20]whichiscomparableinqualitytothecommercialversionofTim-berwolf[21].TheISPD98benchmarksareslightlymodified[20]sothattheycouldbeplaced.
TheMCNCbenchmarksarerelativelysmallcomparedtotoday’sdesignsandarequestionabletousewiththefixed-dieplacementen-gines[9].Yet,theyaretheonlypubliclyavailableplacementbench-marksandarewidelyusedinliterature.TheISPD98benchmarksarelargerandcomparableinsizetocurrentASICdesigns.
DataNumNumNumGlobalFileCellsNetsPinsBinsavqlarge2527833290665256avqsmall2158430038840813080avqsmall.22158430038840818080biomed177052222532040biomed.2177052222534040ibm01.11203613055815ibm01.21203613055815256ibm05.128146297127509ibm05.228146297127509256ibm10.16868575940298311ibm10.26868575940298311256primary183311563303816primary2
3014
3671
12014
1616
TABLEI
BENCHMARKCIRCUITINFORMATION
B.ExperimentalResults
Ourexperimentsfocusondeterminingtheeffectofflexibilityusingglobalrouting.WeperformedourexperimentsusingLabyrinth[1],
setofnetsasconsiderednets.Then,weproducedtwoSteinertreesforeachnet,aninflexibletreewecallinflexandaflexibletreenamedflex.Theflexibilityoftheinflexisguaranteedtobelessthantheflexibilityoftheflex.Theexperimentalflowisasfollows:firstallthenetsotherthanconsiderednetsareroutedusingmazerouting.Aftercongestionisgeneratedonthegriddedgraph,theconsiderednetsarerouted.Inonesetupofexperiments,theyareroutedwithinflextreepattern.Inanothersetofexperiment,theyareroutedwithflextreepattern.
Beforewediscusstheresults,wesummarizedthedatacategoriesofpresentedinTableII.
NumberofNetsconsidered:thenumberofnetswhichhave4terminalsandhaveonemovableedge
TotalRouteLength:thelengthoftheroutedSteinertree(net)summedoveralltheconsiderednets.Rememberthattheroutelengthfortheflexibleandinflexibletreeisequivalent.TotalOverflow:Theoverflow.Thefortotaloneoverflownetis
is
thesummedoverflowoftheconsiderednets.TotalDemand:Demandofanetis[numberofnetsroutedthrough].Totaldemandisthesummeddemandoftheconsiderednets.
OverflowImprovement:.Apositivepercentageindicatesthattheoverflowoftheflexibletreeisbetterthantheoverflowoftheinflexibletree.DemandImprovement:.
Inourexperiment,wecomparedtheoverflowandroutingdemandofaflexibleandinflexibletree.TheedgesoftheSteinertree(boththeflexibleandinflexible)wereroutedinanZ-shapedpattern.Wecomparedtwopropertiesoftherouting,theoverflowandthedemand;botharerelatedtothecongestionofthecircuit(botharedefinedinSectionII-A).Theoverflowoftherouteisthedemandminustheca-pacitysummedoveralltherouteedges.Intuitively,thisdeterminestheamountofroutingresourceswhichareneeded,butcannotbesupplied.Thedemandsimplyisamountofotherroutingswhicharecompetingforthesameroutingresources(edges).
ReferringtoTableII,wecanseethattheflexibletreeproducesaroutingwhichhas,onaverage,20.17%lessoverflowthantheinflexi-bletree(wewanttominimizeoverflow).Infact,theflexibletreewasbetterineverybenchmarkexceptone(biomed).Additionally,theflex-ibletreeencouragedaroutingwhichpassedthroughlessdemandedregions.Theaveragedemandwas4.49%betterfortheflexibletreeascomparedtotheinflexibletree.
Inanothersetofexperiment,weusedaL-shapedpattern-routefortheSteineredges.Theresultshadasimilartrendasthez-shapedpat-ternresults.Inthiscase,theflexibletreehasanoverflowwhichis18.95%betterthantheoverflowoftheinflexibletree.Thedemandfortheroutingoftheflexibletreeis4.34%less(better)thanthedemandfortheinflexibletree.
Inbothoftheexperiments,theflexibletreeproducedaroutingwhichhaslessoverflow.Furthermore,theflexibletreeroutingtendtopassthoughedgeswithlessdemand.
V.CONCLUSIONANDFUTUREWORK
Thispaperstudiedtheproblemofroutabilityinglobalroutingfromadifferentperspective.Flexibility–anewgeometricalpropertyofaRST–wasdefinedanddiscussed.WearguedthatflexibilityhasahighcorrelationtotheroutabilityoftheSteinertree.Analgorithmwas
IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS—...9
Circuitavqlavqsavqs.2biomedbiomed.2ibm01.1ibm01.2ibm05.1ibmo5.2ibm10.1ibm10.2Primary1Primary2TotalAverage
NumberofNets18414582461699221421504-
LengthofRoute151261271703182591519944852437107074565216990-TotalOverflowFlexIn-flex51924261812357858101221573774661596199033638078531661801453319021314249361235933485--TotalDemandFlexIn-flex39246224125568473922022265305531042823296615116158583750388112612867881839088226766828209522723755875881402574421492--
OverflowImprovement73.69%7.69%22.98%3.09%22.29%19.10%19.80%7.69%5.40%11.88%23.60%26.19%19.44%-20.17%
DemandImprovement15.16%5.49%7.44%2.78%1.58%4.82%4.68%3.37%1.72%2.97%5.11%4.22%5.00%-4.49%
TABLEII
OVERFLOWANDCONGESTIONRESULTSWITHZ-SHAPEDPATTERNROUTESFORFLEXIBLEEDGES.
proposedtogenerateanoptimallyflexibleRSTgivenastableRST.Ourinitialexperimentalresultssupportsouridea.OurresultsshowedthatamoreflexibleSteinertreeproducesaroutewhichhassmalleroverflowandhaslessdemand.Sincetheroutabilityofacircuitisrelatedtotheoverflowofitsrouteedges,aflexibleRSTproducesaglobalroutingsolutionwithlessercongestion.
WebelievethattheproposedalgorithmcanbeusedinearlystagestoassignthelocationofSteinerpointswhileconsideringroutability.Byusingthismethod,theglobalroutingcandealwithroutingcongestionmoreeasily.Asfutureworkweplantostudytheflexibilityfunctionsinmoredetailandintegratetheflexibilityalgorithmintoourexistingglobalrouter.
VI.ACKNOWLEDGMENT
AuthorswishtothankDr.DirkStroobandtforhisvaluablefeedbackregardingvariousaspectofthiswork.Authorsarealsogratefultoreviewersfortheirdetailedcommentstechnicallyandconceptually.
REFERENCES
[1]R.Kastner,andM.Sarrafzadeh.“Labyrinth:aGlobalRouterandDevel-opmentTool”.URL:http://www.cs.ucla.edu/kastner/labyrinth/.1999.[2]F.K.Hwang,D.S.Richards,andP.Winter.“TheSteinerTreeProblem”.
AnnalsofDiscreteMathematics53,North-Holland,pp.203-282,1992.[3]C.Albrecht.ACM/SIGDAInternationalSymposiumonPhysicalDesign
“Provablygoodglobalroutingbyanewapproximationalgorithmformul-ticommodityflow”.InProc.ACM/SIGDAInternationalSymposiumonPhysicalDesign,April2000.
[4]R.C.CardenIV,J.M.Li,andC.k.Cheng.“Aglobalrouterwithatheo-reticalboundontheoptimalsolution”.IEEETransactiononComputer-AidedDesign,15(2),pp.208,1996.
[5]C.Chiang,C.K.Wong,andM.Sarrafzadeh.”AWeightedSteiner
Trees-BasedGlobalRouterwithSimultaneousLengthandDensityMini-mization”.InIEEETransactionsonComputer-AidedDesign,13(12),pp.1461-1469,December1994.
[6]X.Hong,T.Xue,E.S.Kuh,C.K.Cheng,J.Huang.“Performance-driven
Steinertreealgorithmforglobalrouting“.InProc.ACM/IEEEDesignAutomationConference,pp.177-181,1993.
[7]E.Bozorgzadeh,R.Kastner,andM.Sarrafzadeh.“CreatingandExploit-ingFlexibilityinSteinerTrees”.InProc.ACM/IEEEDesignAutomationConference,June2001.
[8]R.Kastner,E.Bozorgzadeh,andM.Sarrafzadeh.“PatternRouting:Use
andTheoryforIncreasingPredictabilityandAvoidingCoupling”.InIEEETransactionsonComputer-AidedDesignofIntegratedCircuitsandSystems,pp.777-791,vol.21,No.7,July2002.
[9]A.Caldwell,A.KahngandI.Markov.“CanRecursiveBisectionAlone
ProduceRoutablePlacements?”.InProc.ACM/IEEEDesignAutomationConference,June2000.
[10]J.Hu,S.Sapatnekar.“ATiming-constrainedAlgorithmforSimulta-neousGlobalRoutingofMultipleNets”.InACM/IEEEInternationalConferenceonComputerAidedDesign,November2000.
[11]A.Jagannathan,S.-W.HurandJ.Lillis.“AFastAlgorithmforContext-AwareBufferInsertion”.InProc.ACM/IEEEDesignAutomationCon-ference,June2000.
[12]C.Alpert.“TheISPD98CircuitBenchmarkSuite”.InProc.International
SymposiumonPhysicalDesign,April1998.
[13]E.F.Moore.“TheShortestPaththroughaMaze”.AnnalsoftheHarvard
ComputationLaboratory,Vol.30,Pt.II,1959.
[14]M.GareyandD.Johnson.“TheRectilinearSteinerTreeProblemisNP-Complete”.SIAMJournalonAppliedMathematics,March1977.
[15]J.CongandX.Yuan.“RoutingTreeConstructionUnderFixedBuffer
Locations”.InProc.ACM/IEEEDesignAutomationConference,June2000.
[16]J.Ho,G.VijayanandC.K.Wong.“ANewApproachtotheRectilinear
SteinerTreeProblem”.InProc.ACM/IEEEDesignAutomationConfer-ence,June19.
[17]K.Kozminski.“BenchmarksforLayoutSynthesis-EvolutionandCur-rentStatus”.InProc.ACM/IEEEDesignAutomationConference,June1991.
[18]M.LaiandD.F.Wong.“MazeRoutingwithBufferInsertionandWire
sizing”.InProc.ACM/IEEEDesignAutomationConference,June2000.[19]M.SarrafzadehandC.K.Wong.AnIntroductiontoVLSIPhysicalDesign.
McGraw-Hill,NewYork,NY,1996.
[20]M.Wang,X.YangandM.Sarrafzadeh.“DRAGON:FastStandard-Cell
PlacementforLargeCircuits”.InProc.IEEEInternationalConferenceonComputerAidedDesign,November2000.
[21]W.J.SunandC.Sechen.“EfficientandEffectivePlacementforVery
LargeCircuits”.InProc.InternationalConferenceonComputerAidedDesign,November1993.
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- huatuo6.com 版权所有 湘ICP备2023023988号-11
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务