Design Flow & Floorplanning :
Chip planning involves organizing large parts of a chip, Chip planning has three main stages: (1) floor planning, (2) pin assignment, and (3) power planning.
A gate-level or RTL netlist can be automatically divided into modules. These modules can also be taken from a hierarchical design. Large chip modules are arranged as blocks or rectangular shapes. Floor planning decides where these shapes go and their sizes, based on the areas and aspect ratios of the modules to optimize chip size, reduce interconnect, and improve timing. This stage ensures that every chip module is assigned a shape and a location. This facilitate gate placement and every pin that has an external connection is assigned a location so that internal and external nets can be routed. Pin assignment connects outgoing signals to block pins, and I/O placement finds locations for the chip's input and output pads, usually around the edge of the chip. This step ideally happens before floor planning, but locations can be updated during and after floor planning. Power planning creates the power supply network to ensure each block gets the right supply voltage. Partitioning and chip planning significantly impact later design steps.
Goals for Floorplan :
Importance of FLOOR PLAN:
- Arranging the partitioned blocks on a chip
- Placement of the macros
- Specifying the location of the I/O pads
- Specifying the location and number of the power pads
- Deciding the type of power distribution.
The core of the chip is made up of one or more top level blocks). Core is is surrounded by a ring of pads. The design of the blocks and the arrangement of blocks and pads can affect the overall chip area (and hence the cost/yield).
A module becomes a rectangular block after it is assigned dimensions or a shape. These blocks can be either hard or soft. The dimensions and areas of hard blocks are fixed. For a soft block the area is fixed but the aspect ratio can be changed.
A floor planning usually includes following parameters :
- the area of each module
- all potential aspect ratios of each module
- the netlist of all external connections incident to the module
Required Files for Floor Plan:
1. Synthesized Netlist :
A synthesised netlist describes the electrical connection of the ckt.. It consists of the electrical components and list of connected nodes. A synthesized Netlist can be written in Verilog/VHDL.
2. Physical/Reference Library:
Physical/reference libraries contains physical information for standard cell, macro cell and pad cells. These information are necessary for placement and routing.
3. Logic Libraries :
Logic library contains timing and functionality information of all standard cells used in the design. Timing information of hard macros such as IP, RAM, ROM etc also provided there.
4. Timing Constraints :
Design constraints, clock constraints, max skew, max and min insertion delay, number of clock domain,clock start point all these information are required.
5. Power Requirement : Power and ground Nets
6. Floor Planning Control Parameter :
Die size estimation, core size, aspect ratio, core height, core width.
Optimization in Floor planning :
Area and shape of the global bounding box: The global bounding box of a floor plan is the smallest rectangle that fits around all floorplan blocks. The area of this bounding box represents the total area of the top- level floorplan i.e. the full design and affects circuit performance, yield, and manufacturing cost. To minimize the area of the global bounding box, we need to find the best (x, y) locations and shapes for each module so they fit closely together. Another goal, besides minimizing area, is to keep the aspect ratio of the global bounding box close to a target value. We can adjust the shapes of individual modules to achieve this. The area and aspect ratio of the global bounding box are connected, and both objectives are often optimized together.
Total wirelength: Long connections between blocks slow down signal propagation. For better performance connections must be shortened. Shorter connections means less wire capacitance i.e. reduced energy dissipation. Minimized wire length reduce power consumption. Shorter wire lengths improve routability and reduce manufacturing costs. If connections are too long or dense in one area, there may not be enough routing resources. Spreading circuit blocks apart can add routing tracks but increases chip size and cost. To simplify wire length calculation, we can connect all nets to the centers of the blocks. This method is accurate for small and medium blocks and allows quick interconnect evaluation.
Floorplan Tree :
A floorplan tree represents a hierarchical floorplan. Each leaf node represents a block . Each internal node represent Horizontal Cut (H), Vertical Cut(V) or wheel (W). Order of Floorplan tree is the number of internal/non leaf node.
Constraint Graph Pair :
A constraint-graph pair is a floorplan representation that includes directed graphs showing the relationships between block positions.
Two types of graph :
1. the Vertical Constraint Graph ,
2. the Horizontal Constraint Graph
A constraint graph consists of edges connecting n+2 weighted nodes, one source node s, one sink node t, n block nodes v1,v2 ….vn representing blocks m1,m2 ...mn. The weight of a block node represents the size of the corresponding block. The weights of the source and sink node are zero.
Vertical Constraint Graph (VCG) node weights represent the heights of the corresponding blocks. Two nodes vi and vj with corresponding blocks mi and mj are connected with a directed edge from vi to vj if mi is below mj.
Horizontal Constraint Graph (HCG) node weights represent the widths of the corresponding blocks. Two nodes vi and vj with corresponding blocks mi and mj are connected with a directed edge from vi to vj if mi is to the left of mj.
Longest path in VCG is the min vertical extent requires to pack the blocks (floorplan height)
Longest path in HCG is the min horizontal extent requires to pack the blocks (floorplan width)
A sequence pair is an ordered pair(S+, S-) of block permutations. Together the two permutations represent geometric relations between every pair of blocks a and b.
If a appears before b in both S+ and S-, then a is the left of b.
If a appears before b in S+ but not in S- then a is above b.
S+ : < ...a...b...> S- : <...a...b...> if block a is left of block b
S+ : < ...a...b...> S- : <...b...a...> if block a is above block b
Floorplan Sizing :
Floorplan Sizing determines the minimum area of floorplan as well as the associated orientations and dimensions of each individual block. Algorithm uses the shapes of both the individual blocks and top-level floorplan, shape functions and corner points (limits)play a major role in determining an optimal floorplan. Shape functions (shape curves) and corner points.
Floorplan sizing consists of three major steps:
1. Construct the shape functions of the blocks :
2. Determine the shape function of the top level floorplan:
The overall shape of the top floorplan is based on the shapes of the individual blocks. Combining the blocks in either a vertical or horizontal way can lead to different outcomes.
3. Find the floorplan and individual blocks dimensions and locations :
After figuring out the shape of the top-level floorplan, the smallest possible floorplan area is calculated. These minimum-area floorplans are always located at the corner points of the shape function. Once the corner point with the minimum area is found, we can determine the size and position of each individual block by tracing back from the overall floorplan's shape to each block's shape.
Linear Ordering – I , II & III :
Linear ordering algorithms are frequently used to generate initial placement solutions for iterative improvement placement techniques. The goal of linear ordering is to arrange the given blocks in a single row to minimize the total wire length of the connections between them.
New nets : have no pins on any block from the partially-constructed ordering
Terminating Nets : have no other incident blocks that are unplaced.
Continuing nets : have at least one pin on a block from the partially constructed ordering and at least one pin on an unordered block.
The block with the maximum gain is selected to be placed next.
There are 5 blocks A,B,C,D,E.
There are 6 nets N1, N2, N3, N4, N5, N6.
N1 = { A,B } N2 = { A,D }
N3 = { A,C, E } N4 = { B,D }
N5 = { C, D, E } N6 = { D, E }
A is initial block.
ITERATION - 0 :
ITERATION - 1 :
ITERATION - 2 :
ITERATION - 3 & 4 :
Initial & Final Arrangement:
Cluster Growth :
Floorplan is created by adding blocks one by one until all are placed. Start by choosing an initial block and placing it in any corner. Each new block is added and merged with the cluster, either horizontally or vertically or diagonally. The position and orientation of each new block depend on the current cluster shape. The goal is to place blocks in a way that best meets the floorplan’s objectives. Only the orientations of individual blocks are considered. The order of adding blocks is determined by a linear ordering algorithm. Blocks are added in such a order that overall floor planning area is minimum.
Simulated Annealing :
Simulated annealing algorithms work by starting with an initial random solution and gradually improving it. In each step, they look at nearby solutions by making small changes to the current one and choose a new solution from these options. Unlike greedy algorithms, simulated annealing (SA) algorithms don’t always reject solutions that are worse than the current one. In a greedy algorithm, if a new solution is better (for example, has a lower cost), it is accepted and replaces the current one. If no better solution is found nearby, the algorithm stops, as it’s stuck at a local minimum. The main problem with greedy algorithms is that they only accept changes that improve the solution. The idea of annealing can be used to solve complex optimization problems. In the case of minimizing costs, finding the best solution is like finding the lowest energy state of a material. Simulated annealing algorithms start with a messy (high-cost) solution and mimic the annealing process to create a more organized (lower-cost) solution. The simulated annealing algorithm is random by nature, so running it twice usually gives different results. The difference in outcomes comes from random decisions, like how new solutions are created (for example, by swapping parts) and whether those changes are accepted or rejected.
Watch the Video Lecture Here :
Courtesy : Image by www.pngegg.com
