Min-Cut Placement

The idea

Identical DNA to min-cut floorplanning, applied at cell granularity. Cut the die with a vertical line; bipartition the netlist with a partitioner (Kernighan-Lin then, Fiduccia-Mattheyses and multilevel later) so the two cell sets match the two regions' capacities and few nets cross; recurse with alternating cut directions until regions hold a handful of cells each, then order cells within rows. Every net that crosses a cut must physically cross that line on the die, so total cut over the hierarchy lower-bounds and correlates with routed wirelength.

Cut sequencing is a real design space: strict alternation, quadrature (cut the larger dimension), and bisection versus quadrisection all change results, as does how region capacities absorb differing cell widths.

Strengths and the structural flaw

Strengths: deterministic, fast, naturally hierarchical, and congestion falls out of it (cut counts are crossing demand, so capacity-aware partitioning controls routability directly). The flaw: decisions are irrevocable and locally blind. A net cut at level one is charged once, though its endpoints may drift far apart in later levels; conversely cells that should hug a fixed pin can be exiled early. Terminal propagation (next page) is the classic repair.

Where you meet it today

The pure form is retired, but its skeleton persists in placers that warm-start analytical engines with a partitioning pass, in congestion-driven region budgeting, and in Capo, the method's definitive final form.