您好,欢迎访问三七文档
1430IEEETRANSACTIONSONCOMPUTER-AIDEDDESIGNOFINTEGRATEDCIRCUITSANDSYSTEMS,VOL.26,NO.8,AUGUST2007MB∗-Tree:AMultilevelFloorplannerforLarge-ScaleBuilding-ModuleDesignHsun-ChengLee,Yao-WenChang,Member,IEEE,andHannahHonghuaYangAbstract—Inthispaper,wepresentanagglomerativelymulti-levelfloorplanning/placementframeworkbasedontheB∗-treerepresentationcalledMB∗-treetohandlethefloorplanningandpackingforlarge-scalebuildingmodules.TheMB∗-treeadoptsatwo-stagetechnique,i.e.,clusteringfollowedbydeclustering.TheclusteringstageiterativelygroupsasetofmodulesbasedonacostmetricguidedbyareautilizationandmoduleconnectivityandatthesametimeestablishesthegeometricrelationsforthenewlyclusteredmodulesbyconstructingacorrespondingB∗-treeforthem.Thedeclusteringstageiterativelyungroupsasetofthepreviouslyclusteredmodules(i.e.,performtreeexpansion)andthenrefinesthefloorplanning/placementsolutionbyusingasimulatedannealingscheme.Inparticular,theMB∗-treepreservesthegeometricrelationsamongmodulesduringdeclustering,whichmakestheMB∗-treeanidealdatastructureforthemultilevelfloorplanning/placementframework.ExperimentalresultsshowthattheMB∗-treeobtainssignificantlybettersiliconareaandwirelengththanpreviousworks.Further,unlikepreviousworks,theMB∗-treescalesverywellasthecircuitsizeincreases.IndexTerms—Floorplanning,layout,multilevelframework,physicaldesign,placement.I.INTRODUCTIONDESIGNcomplexitiesaregrowingatbreathtakingspeedwiththecontinuedimprovementofnanometerICtech-nologies.Ononehand,designswithbillionsoftransistorsarealreadyinproduction(ICswithbillionsoftransistorsareevenexpectedwithinthisdecade),InternetProtocolmodulesarewidelyreused,andalargenumberofbufferblocksareusedfordelayoptimizationaswellasnoisereductioninnanometerinterconnect-drivenfloorplanning[3],[11],[19],[20],[23],[35],allofwhichdrivetheneedofatooltohandlelarge-scalebuildingmodules.Ontheotherhand,thehighlycompetitiveICmarketrequiresfasterdesignconvergence,fasterincrementaldesignturnaround,andbettersiliconareautilization.Efficientandeffectivedesignmethodologyandtoolscapableofplac-ManuscriptreceivedApril5,2003;revisedFebruary28,2004andAugust23,2005.TheworkofY.-W.ChangwassupportedbytheNationalScienceCouncilofTaiwanunderGrantsNSC93-2215-E-002-009,NSC93-2220-E-002-001,andNSC93-2752-E-002-008-PAE.Thispaperwaspresentedatthe40thACM/IEEEDesignAutomationConference,June2003.ThispaperwasrecommendedbyAssociateEditorT.Yoshimura.H.-C.LeeiswithSynopsys,Taipei110,Taiwan,R.O.C.(e-mail:gis88526@cis.nctu.edu.tw).Y.-W.ChangiswiththeDepartmentofElectricalEngineeringandGraduateInstituteofElectronicsEngineering,NationalTaiwanUniversity,Taipei106,Taiwan,R.O.C.,andalsowithWasedaUniversity,Tokyo169-8050,Japan(e-mail:ywchang@cc.ee.ntu.edu.tw).H.H.YangiswithStrategicCADLaboratories,IntelCorporation,Hillsboro,OR97124USA(e-mail:hyang@ichips.intel.com).DigitalObjectIdentifier10.1109/TCAD.2007.891368ingandoptimizinglarge-scalemodulesareessentialforsuchlargedesigns.Manyfloorplanrepresentationshavebeenproposed[9],[15],[24]–[28],[31]–[33],[36],[37]intheliterature.However,tra-ditionalfloorplanning/placementalgorithmsdonotscalewellasthedesignsize,complexity,andconstraintsincrease,whicharemainlyduetotheirinflexibilityinhandlingnonslicingfloorplansand/orintrinsicallynonhierarchicaldatastructures(representations).TheB∗-tree,incontrast,hasshownanef-ficient,effective,andflexibledatastructurefornonslicingfloorplans[9].Itisparticularlysuitableforrepresentinganonslicingfloorplanwithlarge-scalemodulesandforcreatingorincrementallyupdatingafloorplan.Whatismoreimportantisthatitsbinary-tree-basedstructuredirectlycorrespondstotheframeworkofahierarchicaldivide-and-conquerscheme,andthus,thepropertiesinheritedfromthestructurecansub-stantiallyfacilitatetheoperationsformultilevellarge-scalebuilding-modulefloorplanning/placement.BasedontheB∗-treerepresentation,wepresentanag-glomerativelymultilevelfloorplanning/placementframeworkcalledMB∗-treetohandlethefloorplanningandpackingforlarge-scalebuildingmoduleswithhighefficiencyandquality.MB∗-treeisinspiredbythesuccessoftheagglomerativelymul-tilevelframeworkingraph/circuitpartitioningsuchasChaco[16],hMetis[21],andML[4];placementsuchasmPL[6];hierarchicalplacement/floorplanningsuchasBEAR[13];androutingsuchasMRS[10],MR[8],[29],MARS[12],andCMR[17],[18].Unlikemultilevelpartitionersandplacers,however,multilevelfloorplanningposesuniquedifficultiesastheshapesofmodulestobeclusteredtogethercansignificantlyaffecttheareautilizationofafloorplan,andafloorplandesignwithinaclusterneedstobeexploredalongwiththeglobalfloorplanoptimization.Theclusteringapproachalsohelpstodirectlyaddressfloorplancongestionandtimingissues,sincedifferentclusteringalgorithmscanbedevelopedtolocalizeintermodulecommunicationandreducethecriticalpathlength.TheMB∗-treealgorithmadoptsatwo-stagetechnique,i.e.,clusteringfollowedbydeclustering.(SeeFig.1foranillustra-tionofthemultilevelframework.)Theclusteringstageitera-tivelygroupsasetofmodules(couldbebasicmodulesand/orpreviouslyclusteredmodules)basedonacostmetricguidedbyareautilizationandmoduleconnectivityandatthesametimeestab
本文标题:MB-tree a multilevel floorplanner for large-scale
链接地址:https://www.777doc.com/doc-3346366 .html