Floorplan (microelectronics)

In electronic design automation, a floorplan of an integrated circuit consists of a schematic arrangement of its major functional blocks on the chip area and the specification of high-level parameters such as the aspect ratio or core utilization.^[1]

A mock floorplan viewed in an IC layout editor

The design step in which floorplans are created is called floorplanning, an early stage in the design flow for integrated circuit design.^[1]

Various mathematical abstractions of this problem have been studied.^[2]

Floorplanning design stage

The floorplanning design stage consists of various steps with the aim of finding floorplans that allow a timing-clean routing and spread power consumption over the whole chip.

• Chip Area Estimation: The dimensions and aspect ratio of the chip area are determined. The estimation considers the space required to place macros, standard cells and I/O ports while also leaving enough space for routing resources to enable a successful place and route design flow. Usually a core utilization ${\displaystyle U={\frac {A_{macros}+A_{std\_cells}}{A_{core}}}}$ of 60%-70% is targeted.^[3]

• I/O Pad Positioning: Input/Output Pads usually need to be positioned along the periphery of the chip. Near the I/O Pads space for line drivers needs to be reserved to minimize delay and signal degradation.^[4]
• Macro Placement: During macro placement large functional blocks with a fixed size and fixed pins such as memory arrays, clock generators or custom components need to be placed within the floorplan's outline. Effective macro placement minimizes the length of timing critical paths, avoids routing congestion and ensures thermal balance.^[4]
• Standard Cell Row Creation: Areas where standard cells should be placed are determined and divided into standard cell rows. During the placement stage standard cells are forced to align with standard cell rows^[5] although they might be of multi-row height. The height of the standard cell rows determines the available routing resources per row while also influencing the power.^[6]

• Power / Ground Structures: Obtaining a power/ground network is not always included in the floorplanning stage. There are however approaches to cosynthesize floorplans and P/G networks based on the idea that if macros and I/O pads are fixed, a power grid analysis is possible.^[7]

Mathematical models and optimization problems

In mathematics floorplanning refers to the problem of packing smaller rectangles with a fixed or unfixed orientation into a larger rectangle. The dimensions of the larger and smaller rectangles might be fixed (hard constraints) or must be optimized (soft constraints). Additionally, a measure modelling the quality of routing that the floorplan allows might be optimized.

Since various variants of rectangle packing are NP-hard, the existence of a polynomial-time algorithm for the general floorplanning problem would imply ${\displaystyle P=NP}$.^[8]

Integer Programming
One can model rectangle packing problem for fixed sizes and orientations as an integer linear program. Further, constraints and variables can be added to minimize the bounding-box-netlength. Given small rectangles ${\displaystyle R_{1},...R_{n}}$ with widths ${\displaystyle w_{1},...,w_{n}}$, heights ${\displaystyle h_{1},...,h_{n}}$ and nets ${\displaystyle {\mathcal {N}}_{1},...,{\mathcal {N}}_{n}}$ as well as a larger rectangle with width ${\displaystyle W}$ and height ${\displaystyle H}$, the integer program looks as follows:

• Objective minimizing bounding-box-netlength

${\displaystyle \min \sum _{N\in \cup _{i=1}^{n}{\mathcal {N}}_{i}}y_{N,t}-y_{N,b}+x_{N,r}-x_{N,l}}$

• Non-overlap constraints

${\displaystyle {\begin{matrix}x_{i}+w_{i}\leq x_{j}+W(1-R_{j,i})\\y_{i}+h_{i}\leq y_{j}+H(1-A_{j,i})\end{matrix}}\quad \forall \ 1\leq i\neq j\leq n}$

• Relative placement disjunction

${\displaystyle R_{j,i}+R_{i,j}+A_{j,i}+A_{i,j}\geq 1\quad \forall \ 1\leq i\neq j\leq n}$

• Net bounding box coverage constraints

${\displaystyle {\begin{matrix}x_{N,r}\geq x_{i}+w_{i}\\x_{N,l}\leq x_{i}\\y_{N,t}\geq y_{i}+h_{i}\\y_{N,b}\leq y_{i}\end{matrix}}\quad \forall \ i\in {1,\ldots ,n},\ N\in {\mathcal {N}}_{i}}$

• Binary variables

${\displaystyle {\begin{matrix}R_{i,j}\in {0,1}\\A_{i,j}\in {0,1}\end{matrix}}\quad \forall \ 1\leq i\neq j\leq n}$

• Rectangle position variables

${\displaystyle {\begin{matrix}x_{i}\in {0,\ldots ,W-w_{i}}\\y_{i}\in {0,\ldots ,H-h_{i}}\end{matrix}}\quad \forall \ i\in {1,\ldots ,n}}$

• Net bounding box variables

${\displaystyle {\begin{matrix}x_{N,l},\ x_{N,r}\in {0,\ldots ,W}\\y_{N,b},\ y_{N,t}\in {0,\ldots ,H}\end{matrix}}\quad \forall N\in \cup _{i=1}^{n}{\mathcal {N}}_{i}}$

For fixed relations ${\displaystyle R_{i,j},A_{i,j}}$ the above integer program is the dual of a maximum flow problem and therefore solvable in polynomial time.^[8]

Not all choices for these spatial relation variables correspond to a feasible placement. A set of relations that contains all feasible placements is called complete. The best known upper bound on the size of a complete set of relations was proved by Silvanus and Vygen, who showed that ${\displaystyle O\left(n!\cdot C^{n}/n^{6}\right)}$ with ${\displaystyle C=(11+5{\sqrt {5}})/{2}}$ spatial relations suffice. They also gave a lower bound of ${\displaystyle O\left(n!\cdot c^{n}/n^{6}\right)}$ with ${\displaystyle c=4+2{\sqrt {2}}.}$^[9]

Heuristics
Using different representations such as O-trees,^[10] B*-trees^[11] or sequence pairs^[12] for the spatial relations between rectangles, various heuristic algorithms have been proposed to solve floorplanning instances in practice. Some of them restrict the solution space by only considering sliceable floorplans.

Sliceable and non-sliceable floorplans

A sliceable floorplan is a floorplan that may be defined recursively as described below.^[13]

• A floorplan that consists of a single rectangular block is sliceable.
• If a block from a sliceable floorplan is cut ("sliced") in two by a vertical or horizontal line, the resulting floorplan is sliceable.

Sliceable floorplans have been used in a number of early electronic design automation tools^[13] for a number of reasons. Sliceable floorplans may be conveniently represented by binary trees (more specifically, k-d trees), which correspond to the order of slicing. More importantly, a number of NP-hard problems with floorplans have polynomial time algorithms when restricted to sliceable floorplans.^[14]

• 
  A sliceable floorplan
• 
  A non-sliceable floorplan

Gradient Descent Algorithms

Leveraging the computing power of GPUs, analytical placement approaches such as DreamPlace have been applied to macro placement problems.^[15]

Further reading

• The Chip Planner of the PLAYOUT System
• VLSI Physical Design: From Graph Partitioning to Timing Closure, by Kahng, Lienig, Markov and Hu, doi:10.1007/978-3-030-96415-3ISBN 978-3-030-96414-6, 2022
• Fundamentals of Layout Design for Electronic Circuits, by Lienig, Scheible, Springer, doi:10.1007/978-3-030-39284-0ISBN 978-3-030-39284-0, 2020