Explore / Methods & Algorithms / Floorplanning / Min-Cut Floorplanning

Min-Cut Floorplanning

Floorplanning foundational 1977 Breuer; Lauther fast and scalable wirelength by proxy

The idea

Min-cut floorplanning couples two recursions. A netlist partitioner splits the design into two groups while cutting as few nets as possible, and the die is split into two regions. One group is assigned to each region, and the process recurses on each half until every region holds a single block.

The connection to wirelength is indirect. At each level the algorithm minimizes one quantity, computed entirely from the netlist and the current partition:

cut(level) = number of nets whose two groups fall on opposite sides of that level's cut line

groups the two block sets the partitioner produced at this level
cut line the single line splitting the current region; which nets cross it depends only on which group each block was assigned to, so the count is a netlist quantity

Any net counted in cut(level) must be routed across that level's line, so minimizing cuts at every level shortens a hierarchy of crossings. The physical length of each crossing is not read from the netlist: it comes from the geometry. Because the die is halved into regions of known size at each level, a cut made early spans a large region and a cut made deep spans a small one, so the span at each level is just the region dimension the recursion has reached. That geometric weight is why coarse-level cuts matter most and the recursion minimizes them first; the netlist supplies only the counts, the bisection supplies the spans.

The partitioner inside is whatever the state of the art offers: Kernighan-Lin in the early years, Fiduccia-Mattheyses after 1982, multilevel partitioners today. All three have pages in the placement catalog.

The recipe

Step 1 (partition the netlist). Split the current block set into two groups of roughly equal size, minimizing the number of nets with endpoints in both groups.

Step 2 (split the region). Cut the current die region into two sub-regions with one line, alternating direction (vertical, then horizontal) between levels so regions stay compact.

Step 3 (assign and recurse). Assign one group to each sub-region. Repeat Steps 1 and 2 on each (group, region) pair.

Step 4 (stop). Recursion ends when a region holds a single block, which now has a position.

Watch it work: recursive bisection

Eight blocks and ten nets on one die. The walkthrough runs the recursion level by level with the cut-net count computed at each level, shows why minimizing cuts shortens wirelength, and ends on the shape-blindness that limits the method.

Pros, cons, and the trade-off

Strengths

Constructive and fast: one top-down pass with a fast partitioner, near-linear in block count, no iteration.
Wirelength-aware by construction: minimizing cuts at every level directly reduces the crossing hierarchy.
Scales: the recursion and the partitioners inside it both scale to millions of objects, which is why the idea became the backbone of standard-cell placement.

Weaknesses

Shape-blind: the recursion assigns regions, not shapes, so large or oddly shaped macros overflow the small leaf regions.
Greedy and local: a net cut at the top level is accounted once, though its final length depends on decisions made much deeper.
No global optimization: each cut is locally optimal, with no mechanism to revisit an early split that later proves costly.

The trade-off

Min-cut floorplanning trades global optimality for speed and scale. Recursive bisection cannot reason about block shapes or revisit early cuts, but it produces a wirelength-aware placement in a single fast pass. That trade sent the idea into standard-cell placement, where blocks are uniform and small, and left macro floorplanning to methods that reason about shapes directly.

Is it actually used today?

The evidence for min-cut splits between macro floorplanning, where it is historical, and placement, where its descendants are standard.

Floorplanning: rarely for macro placement, because it is shape-blind. Modern macro floorplanners reason about shapes and use annealing or analytical methods.
Placement: the recursive-bisection idea, with multilevel partitioners inside, was the dominant standard-cell placement approach for decades and remains in the literature and in some flows (see the placement catalog).
The partitioners: Kernighan-Lin, Fiduccia-Mattheyses, and multilevel partitioning are documented, in use, and covered on their own placement pages.