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.

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

Various mathematical abstractions of this problem have been studied.

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 $U = \frac$ of 60%-70% is targeted.

*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.

*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.
*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 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

*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.

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 $P = NP$.

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 $R_1,...R_n$
with widths $w_1,...,w_n$, heights $h_1,...,h_n$ and nets $\mathcal_1,...,\mathcal_n$ as well as a larger rectangle with width $W$ and height $H$, the integer program looks as follows:
* Objective minimizing bounding-box-netlength
::$\min \sum_ y_ - y_ + x_ - x_$

* Non-overlap constraints
:
::$\begin x_i + w_i \leq x_j + W(1 - R_) \\ y_i + h_i \leq y_j + H(1 - A_) \end \quad \forall\ 1 \leq i \ne j \leq n$
* Relative placement disjunction
:
::$R_ + R_ + A_ + A_ \geq 1 \quad \forall\ 1 \leq i \ne j \leq n$

*Net bounding box coverage constraints
:
::$\begin x_ \geq x_i + w_i \\ x_ \leq x_i \\ y_ \geq y_i + h_i \\ y_ \leq y_i \end \quad \forall\ i \in ,\ N \in \mathcal_i$

*Binary variables
:
::$\begin R_ \in \\ A_ \in \end \quad \forall\ 1 \leq i \ne j \leq n$

*Rectangle position variables
:
::$\begin x_i \in \\ y_i \in \end \quad \forall\ i \in$
*Net bounding box variables
:
::$\begin x_,\ x_ \in \\ y_,\ y_ \in \end \quad \forall N \in \cup_^n\mathcal_i$

For fixed relations $R_, A_$ the above integer program is the dual of a maximum flow problem and therefore solvable in polynomial time.

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 $O\left( n! \cdot C^n /n^6 \right)$ with $C = (11 + 5\sqrt)/$ spatial relations suffice. They also gave a lower bound of $O\left( n! \cdot c^n /n^6 \right)$ with $c = 4 + 2\sqrt 2.$

Heuristics

Using different representations such as O-trees,

B*-trees

or sequence pairs

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."The Electrical Engineering Handbook", Richard C. Dorf (1997)
*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 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.Sarrafzadeh, M,
Transforming an arbitrary floorplan into a sliceable one
, Proc. 1993 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-93), pp. 386-389.

File:Flo-01.png, A sliceable floorplan
File:Flo-02.png, A non-sliceable floorplan

Further reading

by Kahng, Lienig, Markov and Hu, , 2022


by Lienig, Scheible, Springer, , 2020

References

{{reflist

Electronic design automation
Electronics optimization
Combinatorial optimization
Rectangular subdivisions