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 . [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 with widths , heights and nets as well as a larger rectangle with width and height , the integer program looks as follows:
For fixed relations 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 with spatial relations suffice. They also gave a lower bound of with [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]
Leveraging the computing power of GPUs, analytical placement approaches such as DreamPlace have been applied to macro placement problems. [15]
{{cite arXiv}}
: CS1 maint: multiple names: authors list (link){{cite web}}
: CS1 maint: numeric names: authors list (link){{cite journal}}
: CS1 maint: DOI inactive as of June 2025 (link){{cite journal}}
: CS1 maint: DOI inactive as of June 2025 (link)