Convex Optimization and Utility Theory New Trends

ConvexOptimizationandUtilityTheory:NewTrendsinVLSICircuitLayoutbyHusseinA.Y.EtawilAthesispresentedtotheUniversityofWaterlooinfullmentofthethesisrequirementforthedegreeofDoctorofPhilosophyinElectricalEngineeringWaterloo,Ontario,Canada,1999cHusseinA.Y.Etawil1999IherebydeclarethatIamthesoleauthorofthisthesis.Thisisatruecopyofthethesis,includinganyrequirednalrevisions,asacceptedbymyexaminers.Iunderstandthatmythesismaybemadeelectronicallyavailabletothepublic.iiAbstractThedesignofmodernintegratedcircuitsisoverwhelminglycomplicatedduetotheenor-mousnumberofcellsinatypicalmoderncircuit.Todealwiththisdiculty,thedesignprocedureisbrokendownintoasetofdisjointtasks.Circuitlayoutisthetaskthatreferstothephysicalrealizationofacircuitfromitsfunctionaldescription.Incircuitlayout,aconnection-listcallednetlistofcellsandnetsisgiven.Placementandroutingaresubtasksassociatedwithcircuitlayoutandinvolvedeterminingthegeometriclocationsofthecellswithintheplacementareaandconnectingcellssharingcommonnets.Inperformingtheplacementandtheroutingofthecells,minimumplacementarea,minimumdelayandotherperformanceconstraintsneedtobeobserved.Inthiswork,weproposeandinvestigatenewapproachestoplacementandroutingproblems.Specically,fortheplacementsubtask,weproposenewconvexprogrammingformulationstoestimatewirelengthandforcecellstospreadwithintheplacementarea.Asopposedtopreviousapproaches,ourapproachispartitioningfreeandrequiresnohardconstraintstoachievecellspreadingwithintheplacementarea.TheresultoftheglobaloptimizationofthenewconvexmodelsisaglobalplacementwhichisfurtherimprovedusingaTabusearchbasediterativetechnique.Theeectiveness,robustnessandsuperiorityoftheapproacharedemonstratedonasetofninebenchmarkindustrialcircuits.Withregardtotheroutingsubtask,weproposeahybridmethodologythatcombinesTabusearchandStochasticEvolutionasasearchengineinanewchannelrouter.WealsoproposeanewschemebasedonUtilityTheoryforselectingandassigningnetstotracksinthechannel.Inthisscheme,problem-domaininformationexpressedintheformofutilityfunctionsisusedtoguidethesearchenginetoexplorethesearchspaceeectively.Theeectivenessandrobustnessoftheapproachisdemonstratedonveindustrialbenchmarks.iiiAcknowledgementsFirst,allpraisetoGod,themostGraciousandmostMerciful,whosehelpandguidanceiseverdominatingthroughoutmylife.IwouldliketothankmysupervisorDr.AnthonyVannelliforhisconstantsup-portandforprovidingmeadvicewhenappropriate.Hisenthusiasmandguidancehaveproveninvaluabletomyresearch.IwouldalsoliketothankmyfriendandcolleagueDr.ShawkiAreibiforcon-tributingtothisresearchandformanyfruitfuldiscussionsandvaluablesuggestions.MydeepappreciationgoesalsotothepeopleattheCanadianBureauforIn-ternationalEducation(CBIE)fortheirunderstandingandencouragement.FinancialsupportforthisworkwasprovidedbytheSecretariatofScienticResearch(SSR)ofLibyathroughCBIE,andinpartbytheNaturalScienceandEngineeringResearchofCanada(NSERC).Thissupportisgreatlyappreciated.ivToMyParentsvContents1Introduction11.1VLSIDesignCycle...........................21.2CircuitLayoutCycle..........................61.2.1Partitioning...........................61.2.2Placement............................61.2.3Routing.............................81.3DesignStyle...............................91.3.1Macro/Full-Custom.......................91.3.2Semi-Custom..........................101.4MotivationsandObjectives......................121.4.1Motivations...........................131.4.2Objectives............................131.5ThesisOutline..............................15vi2CellPlacement172.1ConstructivePlacement........................182.2IterativeImprovementPlacement...................192.3ACombinationofConstructiveandIterativeMethods............................202.4NetLengthEstimation.........................232.5TestCircuits...............................232.6Summary................................263TheCellRepellerModel283.1ProblemFormulationandtheQuadraticMeasure..........303.2NewConvexModels..........................323.2.1ElementsofvareIndependent................333.2.2ElementsofvareDependent..................353.3TheRepellerModel...........................413.4Summary................................444TheNewGenericPlacementMethod454.1CellSpreadingandthePartitioningApproach............464.2NewMethodforCellSpreading....................494.2.1IdentifyingDenseandSparseRegions.............504.2.2Cell-AttractorAssignment...................52vii4.3TheAttractor-RepellerModel.....................574.4TheAttractor-RepellerPlacer:BasicAlgorithm...........594.5GlobalPlacementLegalization.....................614.6IterativeImprovementMethod.....................624.6.1TabuSearch...........................624.6.2TabuSearchforPlacementIterativeImprovement......644.7Summary................................675ApplicationToStandardCellPlacement685.1QualitativeAnalysis..........................695.1.1Attractors-RepellersandCellSpreading...........705.1.2CellAttractorsandConvergenceoftheGlobalOptimization745.2NumericalResults............................765.3Summary..