RTL Design FlowPhysical Design: Overall Conceptual FlowResults of PlacementSlide 4Gordian Placement FlowGordian: A Quadratic Placement ApproachIntuitive formulationImproving the intuitive formulationModeling the Net’s Wire LengthSlide 10Quadratic Optimization ProblemGlobal Optimization Using Quadratic PlacementSetting up Global OptimizationLayout After Global OptimizationPartitioningSlide 16Layout after Min-cutAdding Positioning ConstraintsContinue to IterateFirst IterationSecond IterationThird IterationFourth IterationFinal PlacementFinal Placement - 1Final Placement – Standard Cell DesignsFinal Placement – Creating RowsStandard Cell LayoutAnother Series of GordianRTL Design FlowRTLSynthesisHDLnetlistlogicoptimizationnetlistLibrary/modulegeneratorsphysicaldesignlayoutmanualdesignabsq01dclkabsq01dclkPhysical Design: Overall Conceptual FlowRead NetlistInitial PlacementPlacementImprovementCost EstimationRouting RegionDefinitionGlobal RoutingInputPlacementRoutingOutputCompaction/clean-upRouting RegionOrderingDetailed RoutingCost EstimationRoutingImprovementWrite Layout DatabaseFloorplanningFloorplanning3Kurt KeutzerResults of PlacementA bad placementA good placementA. KahngWhat’s good about a good placement?What’s bad about a bad placement?4Kurt KeutzerResults of PlacementBad placement causes routing congestion resulting in:• Increases in circuit area (cost) and wiring• Longer wires more capacitanceLonger delayHigher dynamic power dissipationGood placement•Circuit area (cost) and wiring decreases• Shorter wires less capacitanceShorter delayLess dynamic power dissipationGordian Placement FlowComplexityspace: O(m) time: Q( m1.5 log2m)Final placement•standard cell •macro-cell &SOGGlobal Optimization minimization of wire lengthPartitioning of the module set and dissection of the placement regionFinal Placement adoption of style dependent constraintsmodule coordinatesposition constraintsmodule coordinatesRegions with k modulesData flow in the placement procedure GORDIANGordian: A Quadratic Placement Approach•Global optimization: solves a sequence of quadratic programming problems•Partitioning: enforces the non-overlap constraintsIntuitive formulationGiven a series of points x1, x2, x3, … xnand a connectivity matrix C describing the connections between them (If cij = 1 there is a connection between xi and xj)Find a location for each xj that minimizes the total sum of all spring tensions between each pair <xi, xj> xjxiProblem has an obvious (trivial) solution – what is it?Improving the intuitive formulationTo avoid the trivial solution add constraints: Hx=bThese may be very natural - e.g. endpoints (pads)To integrate the notion of ``critical nets’’Add weights wij to netsxjxiwij - some springs have more tensionshould pull associated vertices closerx1 xnwijModeling the Net’s Wire Length yyxxLMuvuvvuvvv22module u(xv,yv(xu,yu),(vuvuvupin vulvnet nodexyconnection to other modules( xuvxuuv ;yuvyu y )vuThe length Lv of a net v is measured by the squared distances from its points to the net’s center10Kurt KeutzerCost x1 1002 x1 x22x2 2002 x1Cost 2x1 100 2x1 x2 x2Cost 2x1 x2 2x2 200setting the partial derivatives = 0 we solve for the minimum Cost:Ax + B = 0 = 04 2 2 4x1x2 200 400 = 02 1 1 2x1x2 100 200x1=400/3 x2=500/3x2x1x=100x=200ToyExample:D. PanQuadratic Optimization ProblemDEFABC),(''vu *0 *0 *0000***' )(lAGFEDCBALinearly constrained quadratic programming problem )({minTTRxx }dxCxxm),(vu s.t.)()(lluxAWire-length for movable modulesAccounts for fixed modulesCenter-of-gravity constraintsProblem is computationally tractable, and well behavedCommercial solvers available: mostekGlobal Optimization Using Quadratic PlacementQuadratic placement clumps cells in centerPartitioning divides cells into two regionsPlacement region is also divided into two regionsNew center-of-gravity constraints are added to the constraint matrix to be used on the next level of global optimizationGlobal connectivity is still conservedSetting up Global OptimizationLayout After Global OptimizationA. KahngPartitioning16Kurt KeutzerPartitioningIn GORDIAN, partitioning is used to constrain the movement of modules rather than reduce problem sizeBy performing partitioning, we can iteratively impose a new set of constraints on the global optimization problemAssign modules to a particular blockPartitioning is determined byResults of global placement – initial starting pointSpatial (x,y) distribution of modulesPartitioning costWant a min-cut partitionLayout after Min-cutNow global placement problem will be solved again with two additional center_of_gravity constraintsAdding Positioning Constraints• Partitioning gives us two new “center of gravity” constraints• Simply update constraint matrix• Still a single global optimization problem• Partitioning is not “absolute” • modules can migrate back during optimization• may need to re-partitionContinue to Iterate20Kurt KeutzerFirst IterationA. Kahng21Kurt KeutzerSecond IterationA. Kahng22Kurt KeutzerThird IterationA. Kahng23Kurt KeutzerFourth IterationA. KahngFinal Placement25Kurt KeutzerFinal Placement - 1Earlier steps have broken down the problem into a manageable number of objectsTwo approaches:Final placement for standard cells/gate array – row assignmentFinal placement for large, irregularly sized macro-blocks – slicing – won’t talk about thisFinal Placement – Standard Cell DesignsThis process continues until there are only a few cells in each group( 6 )each group has 6 cellsgroup: smallest partitionAssign cells in each group close together in the same row or nearly in adjacent rowsA. E. Dunlop, B. W. Kernighan, A procedure for placement of standard-cell VLSI circuits, IEEE Trans. on CAD, Vol. CAD-4, Jan , 1985, pp. 92- 9827Kurt KeutzerFinal Placement – Creating Rows1111,21,2 1,21,2222,32,32,32,33333,4 3,43,43,44 4445555554,5 4,5Row-based standard cell designPartitioning of
View Full Document
Unlocking...