DesignandAnalysisofPhysicalDesignAlgorithms*MajidSarrafzadeh ElahehBozorgzadeh RyanKastner AnkurSrivastavaComputerScienceDepartmentUniversityofCalifornia,LosAngelesLosAngeles,California90095-1596(Contact:[email protected])ABSTRACTWewillreviewafewkeyalgorithmicandanalysisconceptswithapplicationtophysicaldesignproblems.Wearguethatdesignanddetailedanalysisofalgorithmsisoffundamentalimportanceindevelopingbetterphysicaldesigntoolsandtocopewiththecomplexityofpresent-daydesigns.1. INTRODUCTIONProblemsinphysicaldesignaregettingmorecomplexandareoffundamentalimportanceinsolvingpresent-daydesignproblems.Full understanding of the problems and algorithm analysis ofthem are essential to making progress. Whereas problems aregetting harder (e.g. by need for concurrent optimization, finergeometries, and largerproblems)algorithms to cope with themhavenotbeendesignedatthesamerate.Anumberoffundamentalphysicaldesign algorithmshavebeendevelopedinthepastthreedecades.ExamplesaremazerunningandKL-FMpartitioning[7,8,23,24].Theyarebothintheheartof current CAD tools.  A number of existing techniques, usedheavilyincurrentCADtools,havenotbeenfullyanalyzed.Forexample quadratic programming and hierarchical placement areusedpurelyasaheuristicandtheiranalysisisstillopen.Yetthereareproblemsthatarefarfrombeingunderstood.Researchershavestartedonlyveryrecentlytostudythem.Examplesarecongestionestimationandminimizationduringplacement.A heuristics is a good starting point for solving a problem,however,itnormallyfailstoperformwellinachangingoramorecomplex scenario (e.g., hot-spot removal by annealing). TocontinuemakingeffectiveCADtools,weneedtostudyproblemsdeeper,analyzethemthoroughly,andbasetheproposedheuristicsontheperformedanalysis.Herewewilllookatseveralalgorithmdesignandanalysistoolsandconcepts.Themethodsandconceptsthatwewillpointoutinthispaperareusedlessfrequentlyinphysicaldesigntools.Thispaperisorganizedasfollows.InSection2,itisshownhowproblemtransformationisusedtodeviseanewalgorithm.Section3 explains howproof of NP-Completeness of hard problemsisusefulingeneratingefficientalgorithmstosolvethoseproblems.In Section 4, we explain howto obtain the power of a greedymethod through the proof of its correctness. In Section 5, wedescribethatmoreglobalviewtoaproblemcanhelpimprovethegreedyalgorithms.Approximationalgorithmsand advantagesofanalyzingtheperformanceofheuristicmethodsareexplainedinSection6.InSection7,probabilisticalgorithmsandtheirabilitytoprovidesolutionqualityboundsarepresented. InSection 8,someconclusionsaregiven.2. ONPROBLEMTRANSFORMATION:UPPER-BOUNDANALYSISProblemtransformationisaneffectivemethodologyforsolvingaproblem. Mathematicians have used transformation for manyyears and more recently by algorithm designers. Problemtransformation can be used to devise a new algorithm (upper-bound)ortoprovethecomplexityofaproblem(lower-bound).Inthissectionwewillgiveanexampleofnproblemtransformation.The graph-partitioning problem is to partition the vertices of agraphinkintoroughlyequalparts,suchthatthenumberofedgesconnectingverticesindifferentpartsisminimized.Inthispaper,tosimplythepresentation,weuseagraphmodel.Formally,agraphG=(V,E)isdefinedasasetofverticesVandasetofedgesE,whereeachedgeisasubsetofthevertexsetV.Thegraphpartitionproblemis NP-complete.Recently,a numberofresearchershaveinvestigatedaclassofalgorithmsthatcangiveareasonablygood solution for thebi-partition problem[7, 8, 12,13].MostofthesealgorithmsaremoreorlessbasedontheFMalgorithm,whichwasfirstproposedbyFiducciaandMattheysesin1982[7].FMalgorithmisaveryeffectiveheuristicforthebi-partition problem. However, algorithm designers are more andmoreinterestedinthegeneralk-waypartitionproblemwherekisgreaterthantwo.*This work was partially supported by NSF under Grant #CCR-0090203.Permissiontomakedigitalorhardcopiesofallorpartofthisworkforpersonalorclassroomuseis grantedwithoutfeeprovidedthatcopiesarenotmadeordistributedforprofitorcommercialadvantageandthatcopiesbearthisnoticeandthefullcitationonthefirstpage.Tocopyotherwise, or republish, to post on servers or to redistribute to