In VLSI design, the physical arrangement of functional blocks—the floorplan—determines the final chip's performance, power consumption, and manufacturing cost. However, finding the "best" floorplan is a massive combinatorial challenge. To solve it, researchers don't just move boxes around; they design mathematical languages, or topological representations, to describe how blocks relate to one another.
The evolution of this field has moved from simple geometric descriptions toward highly efficient, non-redundant encodings that allow optimization algorithms to search the space of possible layouts more effectively.
The Cost of Flexibility
Early VLSI designs often relied on "slicing floorplans," which are created by repeatedly dividing a rectangle horizontally or vertically. While easy to represent, slicing structures cannot capture more complex "non-slicing" arrangements, such as a ring of blocks surrounding a central module.
To capture these complex layouts, researchers developed representations like the Corner Block List (CBL). However, early versions had limitations, such as an inability to represent "empty rooms"—gaps in the layout that are often necessary for routing wires. Zhou et al. addressed this by proposing ECBL (Extended Corner Block List). By expanding the representation to include empty spaces, the authors proved that the search space could finally encompass the truly optimal placement for any non-slicing floorplan, balancing design freedom with computational efficiency.
Eliminating Redundancy
A major hurdle in floorplan optimization is redundancy. In many representation schemes, multiple distinct mathematical descriptions might map to the exact same physical layout. This is problematic for optimization algorithms (like simulated annealing): if the search space is cluttered with redundant copies of the same solution, the algorithm wastes time "moving" to a new representation that doesn't actually improve the chip area.
Yao et al. tackled this by introducing twin binary trees for mosaic floorplans. A mosaic floorplan is a layout where the area is completely partitioned into non-overlapping rectangles. By establishing a one-to-one mapping between a pair of binary trees and a specific mosaic floorplan, the authors eliminated redundancy entirely. This ensures that every step an optimization algorithm takes leads to a unique physical configuration, significantly streamlining the search for the minimum-area layout.
Reaching the Information-Theoretic Limit
As chip complexity grows to include thousands of blocks, the memory and time required to process these representations become critical. The goal shifted toward finding the most compact binary encoding possible—how few bits can we use to describe a floorplan of $n$ blocks?
While previous methods required $4n$ bits or more, He developed a simple, optimal representation that uses only $3n-3$ bits. This isn't just a marginal improvement; it represents the theoretical lower bound for encoding mosaic floorplans. By reaching this limit, the representation becomes a "master structure" that can efficiently store and manipulate diverse circuit configurations, a concept mirrored in the study of sparse universal graphs by Capalbo et al..
From Representation to Physical Area
Why does the efficiency of these abstract representations matter? Because the ultimate goal is to minimize the physical "silicon real estate" consumed by the layout.
When blocks are placed, they must be connected. Traditional methods often "stretch" cells to align their connection points, but this increases the total area. Cheng et al. demonstrated that by using "river routing" with a single jog per connection, one can join cells while minimizing this area overhead. Similarly, Singh et al. showed that reordering transistors based on logic equations, rather than static net-lists, provides the flexibility needed to shrink the layout even further.
These low-level geometric optimizations rely on the high-level topological representations to provide a valid, efficient starting point. By moving toward non-redundant, optimal encodings, the field has turned floorplanning from a messy geometric puzzle into a precise, searchable mathematical space.
Key Foundational Work
Single Jog Minimum Area Joining of Compacted Cells (1993) — contributed 2 concept elements to this direction.
A Transistor Reordering Technique for Gate Matrix Layout (1990) — contributed 1 concept elements to this direction.