VLSI Cell Placement Techniques
VLSI Cell PlacementK. SHAHOOKARDepartmentUniversityAND P. MAZUMDERof Electricalof MichiganSc ence,48109VLSI cell placement problem is known to be NP complete. A wide repertoire ofheuristic algorithms exists in the literature for efficiently arranging the logic cells ona VLSI chip. The objective of this paper is to present a comprehensive survey of thevarious cell placement techniques, with emphasis on standard ce11and macroplacement. Five major algorithms for placement are discussed: simulated annealing,force-directed placement, rein-cut placement, placement by numerical optimization,and evolution-based placement. The first two classes of algorithms owe their origin tophysical laws, the third and fourth are analytical techniques, and the fifth class ofalgorithms is derived from biological phenomena. In each category, the basic algorithmis explained with appropriate examples. Also discussed are the differentimplementations done by researchers.Categories and Subject Descriptors: B.7.2 [IntegratedAids—placement and routingCircuits]:DesignGeneral Terms: Design, PerformanceAdditional Key Words and Phrases: VLSI, placement, layout, physical design, floorplanning, simulated annealing, integrated circuits, genetic algorithm, force-directedplacement, rein-cut, gate array, standard cellINTRODUCTIONComputer-aideddesigntoolsare nowmakingit possible to automatethe entirelayoutprocess thatfollowsthe circuitdesign phase in VLSIdesign.This hasmainlybeen made possible by the use efficientsoftwarepackagesfor automaticplacementandrouting.Figurela shows a chip usingthe standardcell layoutstyle, whichinc]udes some macro blocks. Standardcells(Figurelb) are logic moduleswith a predesignedinternallayout.They have afixedheightbutdifferentwidths,dependingon the functionalityof the modules.Theyare laid out in rows, withroutingchannelsor spaces betweenrowsreservedfor layingout the interconnectsbetweenthe chip components.Standardcells are usuallydesignedso the powerand groundinterconnectsrun horizontallythroughthe top and bottomof thecells. When the cells are placed adjacentto each other, these interconnectsform acontinuoustrack in each row. The logicinputsand outputsof the moduleareavailableat pins or terminalsalong thetop or bottomedge (or both).They areThis research was partially supported by the NSF Research Initiation Awards under the grant numberMIP-8808978, the University Research Initiative program of the U.S. Army under the grant numberDAAL 03-87-K-OO07,and the Digital Equipment Corporation Faculty Development Award. K, Shahookaris supported by the Science and Technology Scholarship Program of the Government of Pakistan.Permission to copy without fee all or part of this material is granted provided that the copies are not madeor distributed for direct commercial advantage, the ACM copyright notice and the title of the publicationand its date appear, and notice is given that copying is by permission of the Association for ComputingMachinery. To copy otherwise, or to republish, requires a fee and/or specific permission.@ 1991 ACM 0360-0300/91/0600-0143 01.50ACM Computing Surveys, Vol. 23, No. 2, June 1991
144“K. Shahooharand P. MazumderCONTENTS[INTRODUCTIONClassification of Placement AlgorithmsWire length Estimates1 SIMULATED ANNEALING11 Algorithm12 Operation of Simulated Annealing13 TlmberWolf 321.4 Recent Improvements m Simulated Anneahngz FORCE.DIRECTED pLAfJEMENT2 1 Force-DwectedPlacement Techniques2.2 Algorithm2,3 Example24 Goto’sPlacement Algorithm25 Analysls3 PLACEMENT BY PARTITIONING3 1 Breuer’s Algorithms32 Dunlop’s Algorithm and Termmal Propagation33 Quadrlsectlon34 Other Techmques35 Analysls4, NUMERICAL OPTIMIZATION TECHNIQUES41 Eigenvalue Method42 Resu%lveNetwork Optlmlzatlon43 PROUD: Placement by Block Gauss-SeldelOptlmlzatlon44 ATLAS: Techmque for Layout UsingAnalytlc Shapes45 Algorithm for Block Placement by SizeOptlmlzatlon46 Other Work in This Field5 PLACEMENT BY THE GENETIC ALGORITHM5.1 Geme: Genetic Placement Algorlthm5.2 ESP: Evolution-Based Placement Algorlthm53 GASP Genetic Algorlthm for StandardCell Placement6 CONCLUSIONACKNOWLEDGMENTSReferencesconnectedby runninginterconnectsorwires throughthe routingchannels.Connectionsfromone row to t the edges of the chip or byusing feed-throughcells, which are standard heightcells witha few interconnects runningthroughthemvertically.Macro blocks are logic modules not in thestandardcell format,usuallylarger on the chip.Figure2 shows a chip using the gatearray design style. Here, the circuitconsists only of primitivelogic gates, such asNANDgates, not only predesignedbutACM Computing Surveys, Vol 23, No 2, June 1991prefabricatedas a hannelsbetweengates reservedfor interconnects.The design of a chip is thenreducedto designingthe layoutfor theinterconnectsaccordingto the circuitdiagram.Likewise,fabricationof a customchip requiresonly the maskingsteps forinterconnectlayout.Figure3 shows a thirdchip layoutstyle,whichuses onlymacroblocks.These blocks may be of irregularshapesand sizes and do not fit togetherin regular rows and columns.Once again, spaceis left around the modules for wiring.Fora detaileddescriptionof the layout styles,see Muroga[1982] and Ueda et al. [1986].The placementproblemcan be definedas follows.Givenan electricalcircuitconsistingof modules with predefinedinput and outputterminalsand interconnected in a predefinedway, constructalayoutindicatingthe positionsof themodules so the estimatedwire length andlayout area are minimized.The inputs tothe problemare the moduledescription,consistingof the shapes, sizes, and terminal locations,and the netlist,describingthe interconnectionsbetweenthe termi nals of the modules.The outputis a listof x- and y-coordinatesfor all modules.Figure4 providesan exampleof placement,wherethecircuitschematicofFigure4a is placed in the standardcelllayout style in Figure4b. Figure4C illustratestheCheckerboardmodelof theplacementin which all cells are assumedto be squareand of equalsize and allterminalsare assumed to be at the center of the cells. Thus, the lengthof theinterconnectfrom one cell to the next isone unit.The main objectivesof a placementalgorithmare to minimizethe totalchiparea and the total estimatedwire lengthfor all the nets. We need to optimizechiparea usage in order to fit more functionality into a given chip area. We need tominimizewire lengthin order to reducethecapacitivedelaysassociatedwithlonger nets and speed up the operationofthe chip. These goals are closely relatedto each other for standardcell and gatearraydesign styles, since the total chip
Iz E&llnlnEam on 0[1 ACM ComputingSurveys, Vol, 23, No 2, June 1991
146.K. Shahookarand P. MazumderEIUUEIEIEI ATE aaDtlaaaDaInPADHORIZONTALCHANNEL 1 ullElnclElcln0000 001317CICICIEIDCI 00 un oon non un un 00Elan un on clrl nnnclonclnclclclElncinclnnclclclnnnunnclclcl izlclntlnclnclclnclaclcltlclclclnlzclclclclnnnn lclnnnclclnnclclclcincl lnnclciclncltlnnclclncl lnnnnclclclnclnnclclcl.tlnnnnnnclclnclnan lclnclnnnciclclnnnn nnnclcl13clnnnDlJnn clcinElnElclnElclrJnclcl lnnnclclnclclnncluclclclnnclcllJnnclnclclucln nclnclclnclnElclclclclcl lnclclnclnclnnclclclclcl lclclclclclnclclnclnucicl lclclclclclnclElclciclElunn EIEIEIcl 1 1 1 onvERTIciLCHANNELFigure 2.Gate array layout stylearea is approximatelyequal to the areaof the modulesplus the area occupiedbythe interconnect.Hence, minimizingthewire lengthis approximatelyequivalentto minimizingthe chip area. Inthemacrodesign style, the irregularlysized macrosdonotalwaysfittogether,and some spaceis wasted.This playsa majorrole indeterminingthe total chip area, andwehave atrade-offbetween minimizingareaandminimizingthewire length.In somecases, secondaryperformancemeasures,such as the preferentialminimizationofwire lengthof a few criticalnets, mayalsobeneeded, at the cost ofan increasein total wire length.ACM ComputmgSurveys, Vol. 23, No. 2, June 1991Anothercriterionfor an acceptableplacementis that it should be physicallypossible;that is, (1) the modulesshouldnot overlap,(2) they shouldlie withinthe boundariesof the chip, (3) standardcells shouldbeconfinedto rows inpredeterminedpositions,and (4) gates in agate arrayshouldbe confinedto gridpoints.It is commonpracticetodefine afunction,cost functionor an objectivewhichconsistsof the sum of the totalestimatedwire lengthandvariouspenalties for moduleoverlap,total chip area,and so on. The goal of the placementalgorithmis to determinea placementwith the minimumpossible cost.
VLSI Cell PlacementonTechniquesn147nanC—3L .d WASI’EI). PACEElHOR mu- CHANNEL [1[nn-1 pnclncl 1 1!VERTICALCHANNELFigure 3.Macro block layout styleSome of the placementalgorithmsdescribedin thispaperare ‘suitableforstandardcells and gate arrays,some aremore suitablefor macro blocks, and somem-e suitablefor both. In this paper, thewords module,cell, and element are usedto describeeithera standardcell or agate (or a macro block, if the algorithmcan also be used for macros).The wordsmacro and block are used synonymouslyin place of macro block. Their usage alsodepends on the usage in the originalpapers. Similarly,net, wire,interconnect,and signalline are used synonymously.The terms configuration,placement,andsolution(to the placementproblem)areused synonymouslyto representan assignmentof modulesto ‘physicallocationson the chip. The termspin andterminalreferto terminalson themodules.Theterminalsof thechipare referredto as pads.Moduleplacementis an NP-completeproblemand, therefore,cannot be solvedexactly in polynomialtime [Donath1980;Leighton1983; Sahni1980]. Tryingtoget an exact solutionby evaluatingeverypossible placementto determinethe bestone would take time proportionalto thefactorialof the numberof modules.Thismethodis, therefore,impossibleto usefor circuitswith alny reasonablenumberACM Computing Surveys, Vol. 23, No 2, June 1991
148K. Shahookar and P. MazumderAB D Nethst:[A, 1,2, 3,4),(B, 1,2,3,4, 11, 12),(C, 6, 10, 11, 12, 13),[1,8),(2,5),(3,7),(4, lo),(11, 13],(12, 14),(5, 6),{6,8),(8,9),[7,9),(9, 15),{lo, 15),(13, 16),(14, 16),[D, 15),(E, 16). t()co1? *113 lbOE12?[a)T1iI11: v550—d2B400 —1J‘II3IIi,I1I1III14III13IGNDIr350—II 5II107Placement(cell, x, y):)b[,IIIE16!-Kld’“’”w :h150 —c6(0, o; 89—(1, O, 600)(2, o,400)(3, 100,400)(4, 100,600)(5, o, 200)(6, O, O)(7, 75, 2(Y3)(8, 100, O)(9, 200, o)(lo, 150, 200)(11, 300, 600)(12, 200, 600)(13, 300, 400)(14, 2CH3,4fw)(15, 300, o)(16, 250, 200)D15—400(b)Figure 4. Cell placement:checkboard modelACM ComputingSurveys, Volproblemdefinition23, No 2, June 1991(a) Input:Nethst;(b) Output:modulecoordinates;(c)
VLSIA--01TechniquesD0oQCell 1075 ()?6—07T.300co8600159e00-*—[c)Figure 4.a largeof modules.To search throughconficu numberof candidate.dacementrationsefficiently,a heuristicalgorithmmust be used. The qualityof the placement obtaineddepends on the heuristicused. At best, we can hope to find a goodplacementwith wire lengthquite close totheminimum,withno guaranteeofachievingthe absoluteminimum.Theobjectiveof this paper is to introducethereaderto thevariousheuristicalgorithmsdevelopedfor solving this comput ationallyintractableproblemandtoanalyze their performance.The placementprocess is followedbyrouting,that is, determiningthe physicallayoutof the interconnectsthroughtheavailablespace. Findingan optimalrouting givena placementis also an NPcomplete problem.Many algorithmsworkby iterativelyimprovingthe placementand, at each step, estimatingthe wirelengthof an intermediateconfiguration.It is not feasibleto route each intermediateconfigurationto determinehowContinued,good it is. Insteadwe estimatethe wirelengthas describedin the ionof PlacementAlgorithmsPlacementalgorithmscan be divided intotwo major classes: constructiveplacementand iterativeimprovement.In constructive placement,a method is used to buildup a placementfrom scratch; in lacementand repeatedlymodifyit in search of a cost reduction.If a modificationresults in a reductionin cost, themodificationis accepted;otherwiseit e generallybased on t al. [1983], Hanan[1972a],Kambe et al. [1982], Kang [1983], Kozawaet al. [19831, Magnuson[19771, and Persky et al. [1976]. Typically,a seed module is selectedand placedin the chipACM ComputingSurveys, Vol. 23, No. 2, June 1991
150“K. Shahookarand P. Mazumderlayoutarea. Then other modulesare selectedone at a timein orderof theirconnectivityto the placed modules(mostdensely connected first) and are placed ata vacant locationclose to the placed modules, such that the wire lengthis minimized.Suchalgorithmsare generallyvery fast, but typicallyresult in poor layouts. These algorithmsare now used forgeneratingan initialplacementfor iterative improvementalgorithms.The mainreason for their use is theirspeed. Theytake a negligibleamountof computationtime comparedto iterativeimprovementalgorithmsand providea good startingpointfor them.Palczewski[19841 discusses the complexityof such algorithms.More recent constructiveplacementalgorithms,such as numericaloptimizationtechniques,placementby partitioning,and a force-directedtechniquediscussedhere, yield better layouts but requiresignificantlymore CPU egood placementsbut require enormousamountsof computationtime.Thesimplestiterativeimprovement strategyinterchangesrandomlyselected pairs of modulesand accepts theinterchangeif it resultsin a reductionincost [Gotoand Kuh1976;Schweikert1976]. The algorithmis terminatedwhenthere is no furtherimprovementduringagivenlargenumberof trials.An improvementover thisalgorithmis repeated iterativeimprovementin which theiterativeimprovementprocessis ionsin thehopeofobtaininga good configurationin one ofthe hmsincludesimulatedannealing,the geneticalgorithm,and some force-directedplacementtechniques,whichare discussedin detailinthe followingsections.Other possible classificationsfor placement algorithmsare Algorithmsthat functionon the basis offixedconnectivityrulesor formulasordeterminethe placementby solvingsimultaneousequationsare deterministicand will always produce the same resultACM Computmg Surveys, Vol 23, No 2, June 1991fora ,on the otherhand,workbyrandomlyexaminingconfigurationsand may producea differentresulteach timetheyare whereasiterativeim provementalgorithmsare usuallyprobabilistic.WireLengthEstimatesTo makea good estimateof the wirelength,we shouldconsiderthe way inwhich routingis actuallydone by routingtools. Almostall automaticroutingtoolsuse Manhattangeometry;thatis, onlyhorizontaland verticallines are used toconnect any two points. Further,two layers are used; only horizontallines areallowedin one layerand only verticallines in the other.The shortestroute for connectinga setof pins togetheris a Steinertree (Figure 5a). In this method, a wire can branchat anypointalongitslength.Thismethodis usuallynot used by routers,because of the complexityof computingboth the optimumbranchingpoint,andthe resultingoptimumroutefromthebranchingpointto the pins.Instead,minimumspanningtree connectionsandchainconnectionsare the mostcommonlyused connectiontechniques.Foralgorithmsthat compute the Steiner tree:see Chang[1972],Chen[1983],andHwang[1976, 19791.Minimalspanningtreeconnections(Figure5b), allow branchingonly at thepin locations.Hence the pins are connected in the form of the minimalspanning tree of a graph. Algorithmsexist forgeneratinga minimalspanningtreegiven the netlistand cell coordinates.Anexampleof the minimalspanningtreealgorithmis Kruskal[1956].Chainconnections(Figure5c) do notallowany branchingat all. Each pin issimplyconnectedto the next one in theform of a chain.These connectionsareeven simplerto implementthanspanning tree connections,but they resultinslightlylonger interconnects.
/x[,,,:.VLSICell PlacementTechniques“151(a)4xxQ) t (c)(d)Figure 5. Some wiring schemes. (a) Steiner tree- wire length 10; (b) minimal spanning tree —wirelength 11; (c) chain c nnection–wire length 12; (d) sour;e-to-sink connections–wire length 19, 0:source; X, sinkSource-to-sinkconnections(Figure5d),wherethe outputof a moduleis connected to all the inputs by separate wires,are the simplestto implement.They,however,result in excessive interconnectlength and significantwiringcongestion.Hence, this type of connectionis seldomused.Anefficientandcommonlyusedmethod to estimatethe wire lengthis thesemiperimetermethod. The wire length isapproximatedby half the perimeterofthe smallestboundingrectangleenclosing all the pins (Figure6). For Manhattan wiring,this methodgives the exactwirelengthfor alltwo-terminalandthree-terminalnets, providedthe routingdoes not overshootthe boundingrectangle. For four-terminalnets, in the worstcase the semiperimeterestimatepredictsa wirelength3370 less thanboth theactualchainconnectionand spanningtree wirelengths.For nets withmorepins and more zigzagconnections,thesemiperimeterwire length will generallybe less than the actual wire length.Be-sides, this method providesthe best estimate for the most efficientwiringscheme,the Steinertree. The error will be largerfor minimalspanningtreesand stilllarger for chain connections.In practicalcircuits,however,twoandthreeterminalnets are most common.Moreover, among the more complexnets, notall will be worst case, so the semiperimeter wire lengthis a good estimate.Some of the algorithmsdescribedinSection 4 use the euclideanwire lengthor squaredeuclicleanwirelength.Thesquaredwire lengthis used to save thetime requiredfor computinga square rootand for floatingpointcomputationsascomparedto integerprocessing.Optimizationof the sc[uared wire lengthwillensure that the e uclideanwire lengthisoptimized.1. al.1983]is probablythemostACM Computing Surveys, Vol 23, No 2, June 1991
152 K. Shahookarand P. Mazumderwell-developedmethod availablefor module placementtoday. It is very time consumingbut yields excellentresults.It isan excellentheuristicfor solvinganycombinatorialoptimizationproblem,suchas theTravelingSalesmanProblem[Randelmanand Grest19861 or VLSICADproblemssuchas PLAfolding[Wong et al. 19861, kpatrick19831, logicminimization[Lam and Delosme1986], floor planning[Otten and van Ginnekin1984], or placement. It can be consideredan improvedversionof the bove.This latteralgorithmhas a tendencyofgettingstuck at local minima.Suppose,for example,duringthe executionof thepairwiseinterchangealgorithm,we encountera configurationthat has a muchhighercost thanthe optimumand nopairwiseinterchangecan reduce the cost.Since the algorithmacceptsan interchange only if there is a cost reductionand since it examinesonly pairwisein -1.1tima, we need an algorithmthat periodically accepts moves that resultin a costincrease.Simulatedannealingdoes justthat.The basic procedurein simulatedannealingis to accept all moves that resultin a reductionin cost. Moves that resultin a cost increaseare acceptedwithaprobabilitythatdecreaseswiththe increase in cost. A parameterT, called thetemperature,is used to controlthe acceptance probabilityof the cost increasingmoves. Highervaluesof T cause moresuch moves to be accepted.In most implementationsof this algorithm,the acceptanceprobabilityisgive
VLSI Cell Placement Techniques K. SHAHOOKAR AND P. MAZUMDER Department of Electrical Engineering and Computer Sc ence, University of Michigan, Ann Arbor, Michigan 48109 VLSI cell placement problem is known to be NP complete. A wide repertoire of heuristic algorithms exists in the literature for efficiently a
Table of Contents Sequence strong List /strong . Unit 0 1 Introduction 2 How to take the placement tests 3 Placement Test I 4 Placement Test II 5 Placement Test III 6 Placement Test IV 7 Placement Test V 8 Placement Test VI 9 Placement Test VII 10 Placement Test VIII 11 Placement Test IX 12 Placement Test X
VL2114 RF VLSI Design 3 0 0 3 VL2115 High Speed VLSI 3 0 0 3 VL2116 Magneto-electronics 3 0 0 3 VL2117 VLSI interconnects and its design techniques 3 0 0 3 VL2118 Digital HDL Design and Verification 3 0 0 3 VL2119* Computational Aspects of VLSI 3 0 0 3 VL2120* Computational Intelligence 3 0 0 3
Table of Contents Sequence strong List /strong . 50-090816 Unit 0 1 Introduction 2 How to take the placement tests 3 Placement Test I 4 Placement Test II 5 Placement Test III 6 Placement Test IV 7 Placement Test V 8 Placement Test VI 9 Placement Test VII 10 Placement Test VIII 11 Placement Test IX
VLSI Design 2 Very-large-scale integration (VLSI) is the process of creating an integrated circuit (IC) by combining thousands of transistors into a single chip. VLSI began in the 1970s when complex semiconductor and communication technologies were being developed. The microprocessor is a VLSI device.
VLSI IC would imply digital VLSI ICs only and whenever we want to discuss about analog or mixed signal ICs it will be mentioned explicitly. Also, in this course the terms ICs and chips would mean VLSI ICs and chips. This course is concerned with algorithms required to automate the three steps “DESIGN-VERIFICATION-TEST” for Digital VLSI ICs.
Dr. Ahmed H. Madian-VLSI 3 What is VLSI? VLSI stands for (Very Large Scale Integrated circuits) Craver Mead of Caltech pioneered the filed of VLSI in the 1970’s. Digital electronic integrated circuits could be viewed as a set
55:131 Introduction to VLSI Design 10 . Simplified Sea of Gates Floorplan 55:131 Introduction to VLSI Design 11 . SoG and Gate Array Cell Layouts 55:131 Introduction to VLSI Design 12 . SoG and Gate Array 3-in NAND 55:131 Introdu
Reading Comprehension Study Guide and Practice Test 2015 Page 6 Part C: Reading Skill: Making Inferences Read the following passage and answer the questions that follow it. Of all the farm animals a person might own, the goat is the best personal pet. For one thing, you can keep it for a longer time than other farm animals. Even after a doe is .
