Floorplan (microelectronics)

<h2 id="floorplanning-design-stage">Floorplanning design stage</h2>
The floorplanning design stage consists of various steps with the aim of finding floorplans that allow a <a href="/facts/Timing_closure/qr3EUBKJ">timing</a>-clean routing and spread power consumption over the whole chip.

<ul><li>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 <a href="/facts/Place_and_route/UJgLLNdP">place and route design flow</a>. Usually a core utilization 
 
 
 
 U
 =
 
 
 
 
 A
 
 m
 a
 c
 r
 o
 s
 
 
 +
 
 A
 
 s
 t
 d
 _
 c
 e
 l
 l
 s
 
 
 
 
 A
 
 c
 o
 r
 e
 
 
 
 
 
 
 {\displaystyle U={\frac {A_{macros}+A_{std\_cells}}{A_{core}}}}
 
 of 60%-70% is targeted.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li></ul>
<ul><li>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 <a href="/facts/Line_driver/axaAuf8z">line drivers</a> needs to be reserved to minimize delay and signal degradation.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a></li>
<li>Macro Placement: During macro placement large functional blocks with a fixed size and fixed pins such as memory arrays, <a href="/facts/Clock_generator/LLnbc9kp">clock generators</a> 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.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>Standard Cell Row Creation: Areas where <a href="/facts/Standard_Cell/vznSrIbY">standard cells</a> 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<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> 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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li></ul>
<ul><li>Power / Ground Structures: Obtaining a power/<a href="/facts/Ground_(electricity)/F6TEMIVv">ground</a> 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.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li></ul>
<h2 id="mathematical-models-and-optimization-problems">Mathematical models and optimization problems</h2>
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 <a href="/facts/Rectangle_packing/rW4Row14">rectangle packing</a> are <a href="/facts/NP-hard/mQeNPv4R">NP-hard</a>, the existence of a polynomial-time algorithm for the general floorplanning problem would imply 
 
 
 
 P
 =
 N
 P
 
 
 {\displaystyle P=NP}
 
.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>
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
 
 
 
 
 {\displaystyle R_{1},...R_{n}}

with widths 
 
 
 
 
 w
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 w
 
 n
 
 
 
 
 {\displaystyle w_{1},...,w_{n}}
 
, heights 
 
 
 
 
 h
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 h
 
 n
 
 
 
 
 {\displaystyle h_{1},...,h_{n}}
 
 and nets 
 
 
 
 
 
 
 N
 
 
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 
 
 N
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathcal {N}}_{1},...,{\mathcal {N}}_{n}}
 
 as well as a larger rectangle with width 
 
 
 
 W
 
 
 {\displaystyle W}
 
 and height 
 
 
 
 H
 
 
 {\displaystyle H}
 
, the <a href="/facts/Integer_programming/MDaaadoA">integer program</a> looks as follows:

<ul><li>Objective minimizing bounding-box-netlength</li></ul>

min
        
          ∑
          
            N
            ∈
            
              ∪
              
                i
                =
                1
              
              
                n
              
            
            
              
                
                  N
                
              
              
                i
              
            
          
        
        
          y
          
            N
            ,
            t
          
        
        −
        
          y
          
            N
            ,
            b
          
        
        +
        
          x
          
            N
            ,
            r
          
        
        −
        
          x
          
            N
            ,
            l
          
        
      
    
    {\displaystyle \min \sum _{N\in \cup _{i=1}^{n}{\mathcal {N}}_{i}}y_{N,t}-y_{N,b}+x_{N,r}-x_{N,l}}

<ul><li>Non-overlap constraints</li></ul>

x
                  
                    i
                  
                
                +
                
                  w
                  
                    i
                  
                
                ≤
                
                  x
                  
                    j
                  
                
                +
                W
                (
                1
                −
                
                  R
                  
                    j
                    ,
                    i
                  
                
                )
              
            
            
              
                
                  y
                  
                    i
                  
                
                +
                
                  h
                  
                    i
                  
                
                ≤
                
                  y
                  
                    j
                  
                
                +
                H
                (
                1
                −
                
                  A
                  
                    j
                    ,
                    i
                  
                
                )
              
            
          
        
        
        ∀
         
        1
        ≤
        i
        ≠
        j
        ≤
        n
      
    
    {\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}

<ul><li>Relative placement disjunction</li></ul>

R
          
            j
            ,
            i
          
        
        +
        
          R
          
            i
            ,
            j
          
        
        +
        
          A
          
            j
            ,
            i
          
        
        +
        
          A
          
            i
            ,
            j
          
        
        ≥
        1
        
        ∀
         
        1
        ≤
        i
        ≠
        j
        ≤
        n
      
    
    {\displaystyle R_{j,i}+R_{i,j}+A_{j,i}+A_{i,j}\geq 1\quad \forall \ 1\leq i\neq j\leq n}

<ul><li>Net bounding box coverage constraints</li></ul>

x
                  
                    N
                    ,
                    r
                  
                
                ≥
                
                  x
                  
                    i
                  
                
                +
                
                  w
                  
                    i
                  
                
              
            
            
              
                
                  x
                  
                    N
                    ,
                    l
                  
                
                ≤
                
                  x
                  
                    i
                  
                
              
            
            
              
                
                  y
                  
                    N
                    ,
                    t
                  
                
                ≥
                
                  y
                  
                    i
                  
                
                +
                
                  h
                  
                    i
                  
                
              
            
            
              
                
                  y
                  
                    N
                    ,
                    b
                  
                
                ≤
                
                  y
                  
                    i
                  
                
              
            
          
        
        
        ∀
         
        i
        ∈
        
          1
          ,
          …
          ,
          n
        
        ,
         
        N
        ∈
        
          
            
              N
            
          
          
            i
          
        
      
    
    {\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}}

<ul><li>Binary variables</li></ul>

R
                  
                    i
                    ,
                    j
                  
                
                ∈
                
                  0
                  ,
                  1
                
              
            
            
              
                
                  A
                  
                    i
                    ,
                    j
                  
                
                ∈
                
                  0
                  ,
                  1
                
              
            
          
        
        
        ∀
         
        1
        ≤
        i
        ≠
        j
        ≤
        n
      
    
    {\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}

<ul><li>Rectangle position variables</li></ul>

x
                  
                    i
                  
                
                ∈
                
                  0
                  ,
                  …
                  ,
                  W
                  −
                  
                    w
                    
                      i
                    
                  
                
              
            
            
              
                
                  y
                  
                    i
                  
                
                ∈
                
                  0
                  ,
                  …
                  ,
                  H
                  −
                  
                    h
                    
                      i
                    
                  
                
              
            
          
        
        
        ∀
         
        i
        ∈
        
          1
          ,
          …
          ,
          n
        
      
    
    {\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}}

<ul><li>Net bounding box variables</li></ul>

x
                  
                    N
                    ,
                    l
                  
                
                ,
                 
                
                  x
                  
                    N
                    ,
                    r
                  
                
                ∈
                
                  0
                  ,
                  …
                  ,
                  W
                
              
            
            
              
                
                  y
                  
                    N
                    ,
                    b
                  
                
                ,
                 
                
                  y
                  
                    N
                    ,
                    t
                  
                
                ∈
                
                  0
                  ,
                  …
                  ,
                  H
                
              
            
          
        
        
        ∀
        N
        ∈
        
          ∪
          
            i
            =
            1
          
          
            n
          
        
        
          
            
              N
            
          
          
            i
          
        
      
    
    {\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 
 
 
 
 
 R
 
 i
 ,
 j
 
 
 ,
 
 A
 
 i
 ,
 j
 
 
 
 
 {\displaystyle R_{i,j},A_{i,j}}
 
 the above integer program is the <a href="/facts/Dual_linear_program/Qm3r26pm">dual</a> of a <a href="/facts/Maximum_flow_problem/aSal0FGF">maximum flow problem</a> and therefore solvable in polynomial time.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a>
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
 
 (
 
 n
 !
 ⋅
 
 C
 
 n
 
 
 
 /
 
 
 n
 
 6
 
 
 
 )
 
 
 
 {\displaystyle O\left(n!\cdot C^{n}/n^{6}\right)}
 
 with 
 
 
 
 C
 =
 (
 11
 +
 5
 
 
 5
 
 
 )
 
 /
 
 
 2
 
 
 
 {\displaystyle C=(11+5{\sqrt {5}})/{2}}
 
 spatial relations suffice. They also gave a lower bound of 
 
 
 
 O
 
 (
 
 n
 !
 ⋅
 
 c
 
 n
 
 
 
 /
 
 
 n
 
 6
 
 
 
 )
 
 
 
 {\displaystyle O\left(n!\cdot c^{n}/n^{6}\right)}
 
 with 
 
 
 
 c
 =
 4
 +
 2
 
 
 2
 
 
 .
 
 
 {\displaystyle c=4+2{\sqrt {2}}.}
 
<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>
Heuristics
Using different representations such as O-trees,<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> B*-trees<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> or sequence pairs<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a> 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.

<h2 id="sliceable-and-non-sliceable-floorplans">Sliceable and non-sliceable floorplans</h2>
A sliceable floorplan is a floorplan that may be defined recursively as described below.<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a>

<ul><li>A floorplan that consists of a single rectangular block is sliceable.</li>
<li>If a block from a sliceable floorplan is cut ("sliced") in two by a vertical or horizontal line, the resulting floorplan is sliceable.</li></ul>
Sliceable floorplans have been used in a number of early <a href="/facts/Electronic_design_automation/o4la3fmX">electronic design automation</a> tools<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> for a number of reasons. Sliceable floorplans may be conveniently represented by <a href="/facts/Binary_tree/TDV7GMpu">binary trees</a> (more specifically, <a href="/facts/K-d_tree/XuhcfKKq">k-d trees</a>), which correspond to the order of slicing. More importantly, a number of NP-hard problems with floorplans have <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> algorithms when restricted to sliceable floorplans.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

<h2 id="gradient-descent-algorithms">Gradient Descent Algorithms</h2>
Leveraging the computing power of GPUs, analytical placement approaches such as DreamPlace have been applied to macro placement problems.<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a>

<h2 id="further-reading">Further reading</h2>
<ul><li><a href="http://www.schoelzke.info/mirror/galway/projects/ChipPlanner-Description.htm">The Chip Planner of the PLAYOUT System</a></li>
<li><a href="https://www.ifte.de/books/eda/index.html">VLSI Physical Design: From Graph Partitioning to Timing Closure</a>, by Kahng, Lienig, Markov and Hu, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-030-96415-3">10.1007/978-3-030-96415-3</a><a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-030-96414-6, 2022</li>
<li><a href="https://www.ifte.de/books/pd/index.html">Fundamentals of Layout Design for Electronic Circuits</a>, by Lienig, Scheible, Springer, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F978-3-030-39284-0">10.1007/978-3-030-39284-0</a><a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-030-39284-0, 2020</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"Floorplan in VLSI Physical Design". iVLSI Technologies. Retrieved 2025-06-12. <a href="https://ivlsi.com/floorplan-vlsi-physical-design/" target="_blank">https://ivlsi.com/floorplan-vlsi-physical-design/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"Floorplan in VLSI Physical Design". iVLSI Technologies. Retrieved 2025-06-12. <a href="https://ivlsi.com/floorplan-vlsi-physical-design/" target="_blank">https://ivlsi.com/floorplan-vlsi-physical-design/</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">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. <a href="1-58113-191-7" target="_blank">1-58113-191-7</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Liu, Chen-Wei and Chang, Yao-Wen (2024-09-01). "Physical Design: Methodologies and Developments". arXiv:2409.04726 [eess.SY].{{cite arXiv}}: CS1 maint: multiple names: authors list (link) <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">VLSIPD4 (2023-04-23). "Floorplanning in Physical Design". Medium. Retrieved 2025-06-06.{{cite web}}: CS1 maint: numeric names: authors list (link) <a href="https://medium.com/@vlsipd4/floorplanning-in-physical-design-052e4fe2bb66" target="_blank">https://medium.com/@vlsipd4/floorplanning-in-physical-design-052e4fe2bb66</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">VLSIPD4 (2023-04-23). "Floorplanning in Physical Design". Medium. Retrieved 2025-06-06.{{cite web}}: CS1 maint: numeric names: authors list (link) <a href="https://medium.com/@vlsipd4/floorplanning-in-physical-design-052e4fe2bb66" target="_blank">https://medium.com/@vlsipd4/floorplanning-in-physical-design-052e4fe2bb66</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">VLSI‑Talks (January 2023). "FLOORPLAN - VLSI TALKS". VLSI TALKS. Retrieved 2025-06-12. <a href="https://vlsitalks.com/physical-design/floorplan/" target="_blank">https://vlsitalks.com/physical-design/floorplan/</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">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. <a href="https://doi.org/10.1109/ISQED.2019.8697712" target="_blank">https://doi.org/10.1109/ISQED.2019.8697712</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">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. <a href="https://doi.org/10.1145/1123008.1123026" target="_blank">https://doi.org/10.1145/1123008.1123026</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">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. <a href="https://doi.org/10.1016/j.vlsi.2015.07.001" target="_blank">https://doi.org/10.1016/j.vlsi.2015.07.001</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">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. <a href="https://doi.org/10.1016/j.vlsi.2015.07.001" target="_blank">https://doi.org/10.1016/j.vlsi.2015.07.001</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">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 15 June 2025).{{cite journal}}: CS1 maint: DOI inactive as of June 2025 (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">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 15 June 2025).{{cite journal}}: CS1 maint: DOI inactive as of June 2025 (link) <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">"The Electrical Engineering Handbook", Richard C. Dorf (1997) ISBN 0-8493-8574-1 <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">"The Electrical Engineering Handbook", Richard C. Dorf (1997) ISBN 0-8493-8574-1 <a href="/wiki/ISBN_(identifier)" target="_blank">/wiki/ISBN_(identifier)</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">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.
 <a href="https://ieeexplore.ieee.org/abstract/document/580085/" target="_blank">https://ieeexplore.ieee.org/abstract/document/580085/</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">Brian Santo (24 April 2023). AI Can’t Design Chips Without People. EE Times. 
https://www.eetimes.com/ai-cant-design-chips-without-people/. Accessed 18 June 2025. <a href="https://www.eetimes.com/ai-cant-design-chips-without-people/" target="_blank">https://www.eetimes.com/ai-cant-design-chips-without-people/</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
</ol>

Floorplan (microelectronics) open-in-new

Floorplan (microelectronics)