Floorplan (microelectronics)

A mock floorplan viewed in an IC layout editor

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]

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

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-3 ISBN   978-3-030-96414-6, 2022
• Fundamentals of Layout Design for Electronic Circuits, by Lienig, Scheible, Springer, doi : 10.1007/978-3-030-39284-0 ISBN   978-3-030-39284-0, 2020

References

1. "Floorplan in VLSI Physical Design". iVLSI Technologies. Retrieved 2025-06-12.
2. Kahng, Andrew B. (2000). "Classical floorplanning harmful?". Proceedings of the 2000 international symposium on Physical design. ISPD '00. Association for Computing Machinery. pp. 207–213. doi:10.1145/332357.332401. ISBN   1-58113-191-7 . Retrieved 2025-06-12.
3. Liu, Chen-Wei and Chang, Yao-Wen (2024-09-01). "Physical Design: Methodologies and Developments". arXiv: 2409.04726 [eess.SY].
4. VLSIPD4 (2023-04-23). "Floorplanning in Physical Design". Medium. Retrieved 2025-06-06.
5. VLSI‑Talks (January 2023). "FLOORPLAN - VLSI TALKS". VLSI TALKS. Retrieved 2025-06-12.
6. Lin, Ruei-Bin; Chiang, Yi-Xiu (2019). Impact of Double-Row Height Standard Cells on Placement and Routing. 20th International Symposium on Quality Electronic Design (ISQED). Santa Clara, CA, USA: IEEE. pp. 317–322. doi:10.1109/ISQED.2019.8697712 . Retrieved 2025-06-12.
7. Liu, Chen-Wei; Chang, Yao-Wen (2006). Floorplan and power/ground network co-synthesis for fast design convergence. 2006 International Symposium on Physical Design. ISPD '06. San Jose, California, USA: Association for Computing Machinery. pp. 86–93. doi:10.1145/1123008.1123026 . Retrieved 2025-06-12.
8. Funke, Julia; Hougardy, Stefan; Schneider, Jan (2016). "An exact algorithm for wirelength optimal placements in VLSI design". Integration: The VLSI Journal. 52: 355–366. doi:10.1016/j.vlsi.2015.07.001 . Retrieved 2025-06-12.
9. Silvanus, Jannik; Vygen, Jens (2017). "Few Sequence Pairs Suffice: Representing All Rectangle Placements". SIAM Journal on Discrete Mathematics. 34: 2017–2032. doi:10.1137/16M1095880 (inactive 1 July 2025).
10. Tang, M.; Sebastian, A. (2005). "A Genetic Algorithm for VLSI Floorplanning Using O-Tree Representation". Applications of Evolutionary Computing. Lecture Notes in Computer Science. Vol. 3449. Springer Berlin Heidelberg. pp. 215–224. doi:10.1007/978-3-540-32003-6_22.
11. Fernando, J.; Katkoori, S. (2008). "An Elitist Non-dominated Sorting Based Genetic Algorithm for Simultaneous Area and Wirelength Minimization in VLSI Floorplanning". Proceedings of the 21st International Conference on VLSI Design. IEEE. pp. 337–342. doi:10.1109/VLSI.2008.56.
12. Lin, P.-H.; Chang, Y.-W.; Lin, S.-C. (2009). "Analog Placement Based on Symmetry-Island Formulation". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. 28 (6). IEEE: 791–804. doi:10.1109/TCAD.2009.2015708 (inactive 1 July 2025).
13. "The Electrical Engineering Handbook", Richard C. Dorf (1997) ISBN   0-8493-8574-1
14. 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.