IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS —... 1 Creat

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.