11Placement: Key Step for Design ClosureGi-Joon NamIBM Austin Research LabCredits: IBM PDS team, Placement team2Outline of talk Placement in design closure flow Brief review of placement technology ISPD 2005 / 2006 placement contest & benchmark suite. Modern placement methodology Conclusion and future work23Design Closure Flow Microelectronics - ASICs. Continued #1 industry ranking Maintaining high-end technology  Highest gate count, advanced materials, IP Record 35M-gate customer design New cores (eDRAM, eFPGA, serial link) for SoC Continued EDA tool innovations Proven first-time-right methodology Driven down into mid-range applications IP collaboration adding 3rdparty cores Low-power technology for consumer designs Easier design through standard tools Semi-custom platform availability4Global Interconnect Dominance35Design Closure ProblemConvergence???Logic SynthesisPlacement unawareArbitrary wireloadsPlacementWire length drivenTiming unawareRoutingTiming aware6Design Closure Flow Eliminate iterations Reduce TAT Tight integration of relevant tools Floorplanning/Placement Logic transformations to correct timing Gate Sizing Buffering Logic restructuring Interconnection restructuring Physical location change Routing Congestion-aware Noise-aware47Design Closure FlowPlacement-DrivenOptimizationPre-processingCongestion-drivenplacementEarly OptimizationLate OptimizationTiming-drivenplacementDetailed Placement8Outline of talk Placement in design closure flow Brief review of placement technology ISPD 2005 / 2006 placement contest & benchmark suite. Modern placement methodology Conclusion and future work59Key Themes in Placement Placement problem consists of optimizing three orthogonal components: Relative order Spacing Global position All within the context of routability, timing and signal integrity Placement within timing closure system is especially sensitive to stability10Placement Stability Algorithm produces similar results given similar input data Algorithm produces “scaled” results across a range of problem parameters (like density) Results are predictable611Placement Objective Find optimal relative ordering of cells Minimize wire length and congestion Maximize timing slack Find optimal spacing of cells Eliminate wiring congestion problems Provide space for post placement synthesis Clock tree Buffer insertion Timing correction Find global optimal position12Overview of Common Placement Algorithm Simulated Annealing Recursive Partitioning Quadratic Placement Force-directed Placement713Simulated Annealing Great quality of results Excellent relative ordering Excellent spacing Excellent global position Algorithm runtime is a problem Difficult to integrate with timing closure toolsfor (temp=high; temp > absolute_zero; temp -= increment){make a random movescore the moveuse temp dependent probability to decide to accept or reject}Note: Clustering can be used to improve performance14Recursive Partitioning-based Placement Given a set of interconnected blocks, produce two (four) sets that are of equal size such that the number of nets connecting the two sets is minimized815Recursive Partitioning-based Placementlist_of_sets = entire_chip;while(any_set_has_2_or_more_objects(list_of_sets)){for_each_set_in(list_of_sets){partition_it();}/* each time through this loop the number of *//* sets in the list doubles. */}Initial Random PlacementAfter Cut 1After Cut 216Recursive Partitioning-based Placement Finds correct cell ordering Poor spacing Poor position Lack of stability917Quadratic Placement PROUD [DAC88], GORDIAN [TCAD91], GORDIAN-L [DAC91], Vygen [DAC 97] implementation Minimize total squared wire length  wij{ (xi–xj)2+ (yi–yj)2} Form and solve large Ax=b linear system Called Quadratic Placement optimization (QP) But… Solutions will have overlaps Quadrisection will eliminate overlaps Recursive algorithm with Repartitioning refinements18QP Mathematical Formulation Objective function: squared wire length f(X) = (x1–100)2+ (x2– 200)2+ (x1–x2)2 Set the derivative of f(X) to 0, df(X)/dX = 0 df(X)/dx1= 2(x1– 100) + 2(x1–x2) = 0 df(X)/dx2= 2(x1–x2) + 2(x2– 200) = 0x1x2X = 100X = 200w1w12w2w1w2w121019QP Resulting Matrix Equations Thus Ax=b where A = 2 -1 , b = 100-1 2 200 In general, a sparse linear system equationAx bNumber ofmovableobjects=20Quadratic Placement Why formulate the problem this way? Known techniques make solution easy to find There is only one solution (convex solution space) The solution conveys “relative order” information The solution conveys “global position” information However… Solution is not legal, generally densely overlapping Needs to be spread out Solution depends on fixed anchor points Solution minimize squared wire length, not linear wire length, congestion or timing1121Quadrisection Geometric PartitioningxcutycutR0R1R2R3Given:- cut spec- a set of cells V-for each v  V(x(v), y(v))size(v)- capacity for each sub-region0, 1, 2, 322Quadrisection: Geometric Partitioning Partitioning formulation f : V → i  {0, 1, 2, 3} such that Meet capacity constraints { size(v) | v  V, f (v) = i } ñ ifor i=0,1,2,3 Minimize weighted total movement  size(v) $ distance((x(v), y(v)), Rf(v))1223QP Refinements: Repartitioning 2 x 2 sliding window local refinement One pass goes over the entire placement region Keep iterating until the improvement is insignificant Sequence dependent24Outline of talk Placement in design closure flow Brief review of placement technology ISPD 2005 / 2006 placement contest & benchmark suite. Modern placement methodology Conclusion and future work1325Trends in Placement Chips are larger Footprints are more diverse Free space is growing Interconnect delays are larger percentage of chip cycle time Placement is no longer a point tool Core part of a timing closure system26ISPD 2005 Placement Benchmark