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]
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.
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 = N P {\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 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 integer program looks as follows:
For fixed relations R i , j , A i , j {\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 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}}.} [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.
A sliceable floorplan is a floorplan that may be defined recursively as described below.[13]
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]
{{cite arXiv}}
{{cite web}}
{{cite journal}}
