VLSI Physical Design AutomationHierarchical DesignSlide 3FloorplanningFloorplanning v.s. PlacementFloorplanning ProblemBounds on Aspect RatiosSlide 8Objective FunctionWirelength EstimationDead spaceSlicing and Non-Slicing FloorplanPolar Graph RepresentationPolar Graph: ExampleSimulated Annealing using Polish Expression RepresentationRepresentation of Slicing FloorplanPolish ExpressionSkewed ST and Normalized PENormalized Polish ExpressionNeighborhood StructureExample of MovesShape CurveCombining Shape CurvesFind the Best Area for a NPEUpdating Shape Curves after MovesInitial SolutionAnnealing ScheduleHandling both Rectangular and L-Shaped BlocksRectangular and L-Shaped BlocksBasic IdeaOperatorsBinary Operators V1, V2, H1 and H2Example of Combining 2 BlocksAnother Example of CombiningMovesAnother Classic WorkDifficultyKey IdeaExample of Merging: only keep irredundant solutionsStockmeyer AlgorithmStockmeyer Algorithm (Cont’d)Complexity of the AlgorithmSummary: What’s BIG idea?01/13/191VLSI Physical Design AutomationProf. David [email protected]: ACES 5.434Lecture 6. Floorplanning (1)201/13/19Hierarchical Design•Several blocks after partitioning:•Need to:–Put the blocks together.–Design each block. Which step to go first?301/13/19Hierarchical Design•How to put the blocks together without knowing their shapes and the positions of the I/O pins?•If we design the blocks first, those blocks may not be able to form a tight packing.401/13/19Floorplanning The floorplanning problem is to plan the positions and shapes of the modules at the beginning of the design cycle to optimize the circuit performance:–chip area–total wirelength–delay of critical path–routability–others, e.g., noise, heat dissipation, etc.501/13/19Floorplanning v.s. Placement•Both determines block positions to optimize the circuit performance.•Floorplanning:–Details like shapes of blocks, I/O pin positions, etc. are not yet fixed (blocks with flexible shape are called soft blocks).•Placement:–Details like module shapes and I/O pin positions are fixed (blocks with no flexibility in shape are called hard blocks).601/13/19Floorplanning Problem•Input:–n Blocks with areas A1, ... , An–Bounds ri and si on the aspect ratio of block Bi•Output:–Coordinates (xi, yi), width wi and height hi for each block such that hi wi = Ai and ri  hi/wi  si•Objective:–To optimize the circuit performance.701/13/19Bounds on Aspect Ratios If there is no bound on the aspect ratios, can we pack everything tightly? - Sure! But we don’t want to layout blocks as long strips, so we require ri  hi/wi  si for each i.801/13/19Bounds on Aspect Ratios•We can also allow several shapes for each block:•For hard blocks, the orientations can be changed:901/13/19Objective Function A commonly used objective function is a weighted sum of area and wirelength:cost = A + L where A is the total area of the packing, L is the total wirelength, and and are constants.1001/13/19Wirelength Estimation•Exact wirelength of each net is not known until routing is done.•In floorplanning, even pin positions are not known yet.•Some possible wirelength estimations:–Center-to-center estimation–Half-perimeter estimation1101/13/19Dead space•Dead space is the space that is wasted:•Minimizing area is the same as minimizing deadspace. •Dead space percentage is computed as (A - iAi) / A  100% Dead space1201/13/19Slicing and Non-Slicing Floorplan•Slicing Floorplan: One that can be obtained by repetitively subdividing (slicing) rectangles horizontally or vertically.•Non-Slicing Floorplan:One that may not be obtained by repetitively subdividing alone.•Otten (LSSS-82) pointed out that slicing floorplans are much easier to handle.1301/13/19Polar Graph Representation•A graph representation of floorplan.•Each floorplan is modeled by a pair of directed acyclic graphs:–Horizontal polar graph–Vertical polar graph•For horizontal (vertical) polar graph,–Vertex: Vertical (horizontal) channel–Edge: 2 channels are on 2 sides of a block–Edge weight: Width (height) of the blockNote: There are many other graph representations.1401/13/19Polar Graph: ExampleHorizontal Polar GraphVertical Polar Graph01/13/1915Simulated Annealing using Polish Expression RepresentationSimulated Annealing using Polish Expression RepresentationD.F. Wong and C.L. Liu,D.F. Wong and C.L. Liu,““A New Algorithm for Floorplan DesignA New Algorithm for Floorplan Design””DAC, 1986, pages 101-107.DAC, 1986, pages 101-107.1601/13/19Representation of Slicing Floorplan6235471Slicing FloorplanVH H2 1 3HV6 4V7 5Slicing TreePolish Expression(postorder traversalof slicing tree)21H67V45VH3HV1701/13/19Polish Expression•Succinct representation of slicing floorplan–roughly specifying relative positions of blocks•Postorder traversal of slicing tree1. Postorder traversal of left sub-tree2. Postorder traversal of right sub-tree3. The label of the current root•For n blocks, a Polish Expression contains n operands (blocks) and n-1 operators (H, V). •However, for a given slicing floorplan, the corresponding slicing tree (and hence polish expression) is not unique. Therefore, there is some redundancy in the representation.1801/13/19Skewed ST and Normalized PE•Skewed Slicing Tree: –no node and its right son are the same.•Normalized Polish Expression: –no consecutive H’s or V’s.6235471Slicing FloorplanVH H2 1 3HV6 4V7 5Slicing Tree (Skewed)Polish Expression21H67V45VH3HVVH H2 1 HV6V73Slicing Tree4521H67V45V3HHV1901/13/19Normalized Polish Expression•There is a 1-1 correspondence between Slicing Floorplan, Skewed Slicing Tree, and Normalized Polish Expression.•Will use Normalized Polish Expression to represent slicing floorplans.–What is a valid NPE? •Can be formulated as a state space search problem.2001/13/19Neighborhood Structure•Chain: HVHVH.... or VHVHV....•The moves:M1: Swap adjacent operands (ignoring chains)M2: Complement some chainM3: Swap 2 adjacent operand and operator(Note that M3 can give you some invalid NPE. So checking for validity after M3 is needed.)•It can be proved that every pair of valid NPE are connected.16H35V2HV74HVChains2101/13/19Example of Moves2154334V2H5V1H143 2532V4H5V1H1542332V45HV1H14 53 232V45VH1HM1M3M22201/13/19Shape Curve•To represent the possible shapes of a block.wh(0,0)wh = ASoft blockBlock with several existing