1 Area Fill Synthesis for Uniform Layout Density

Abstract--- Chemical-mechanical polishing (CMP) and other manufacturing steps in very deep submicron VLSI have varying effects on device and interconnect features, depending on local characteristics of the layout. To improve manufacturability and performan

AreaFillSynthesisforUniformLayoutDensity

YuChen,AndrewB.Kahng,GabrielRobins,andAlexanderZelikovsky

Abstract—Chemical-mechanicalpolishing(CMP)andothermanufacturingstepsinverydeepsubmicronVLSIhavevaryingeffectsondeviceandinterconnectfeatures,dependingonlocalcharacteristicsofthelayout.Toimprovemanufacturabilityandperformancepredictability,weseektomakealayoutuniformwithrespecttoprescribeddensitycriteria,byinserting“area ll”geometriesintothelayout.Inthispaper,wemakethefollow-ingcontributions.First,wede nethe at,hierarchicalandmultiple-layer llingproblems,alongwithauni eddensitymodeldescription.Secondly,forthe at llingproblem,wesummarizecurrentlinearprogrammingapproacheswithtwodifferentobjectives,i.e.,theMin-VarandMin-Fillobjectives.WethenproposeseveralnewMonte-Carlobased llingmethodswithfastdynamicdatastructures.Third,wegivepracticaliteratedmethodsforlayoutdensitycontrolforCMPuniformitybasedonlinearprogramming,Monte-Carloandgreedyalgorithms.Fourth,toaddressthelargedatavolumeandinherentlackofscalabilityof atlayoutdensitycon-trol,weproposepracticalmethodsforhierarchicallayoutdensitycontrol.Thesemethodssmoothlytradeoffruntime,solutionquality,andoutputdatavolume.Finally,weextendthelinearprogrammingapproachesandpresentnewMonte-Carlobasedmethodsforthemultiple-layer llingproblem.Comparisonswithprevious llingmethodsshowtheadvantagesofthenewiteratedMonte-Carloanditeratedgreedymethodsforboth atandhierarchicallayouts,andforbothdensitymodels(spatialdensityandeffectivedensity).Weachievenear-optimal llingfor atlayoutswithrespecttoeachoftheseobjectives.Ourexperimentsindicatethatthehybridhierarchical llingapproachisef cient,scalable,accurate,andhighlycompetitivewithexistingmethods(e.g.,linear-programmingbasedtechniques)forhierarchicallayouts.

ThisresearchwassupportedbyaPackardFoundationFellowship,bytheMARCOGigascaleSiliconResearchCenter,byNSFYoungInvestigatorAwardMIP-9457412,byNSFgrantCCR-9988331,andbyagrantfromCadenceDesignSystems,Inc.

Y.CheniswiththeDepartmentofComputerScience,UCLosAngeles,LosAngeles,CA90095-1596.E-mail:yuchen@cs.ucla.edu.

A.B.KahngiswiththeDepartmentsofComputerScienceandEngineering,andofElectricalandComputerEngineering,UCSanDiego,LaJolla,CA92093-0114.E-mail:abk@cs.ucsd.edu.

G.RobinsiswiththeDepartmentofComputerScience,UniversityofVirginia,Charlottesville,VA22903-2442.E-mail:robins@cs.virginia.edu.

A.ZelikovskyiswiththeDepartmentofComputerScience,GeorgiaStateUniversity,Atlanta,GA30303.alexz@cs.gsu.edu.

E-mail: