Terminal Propagation

The idea

Raw min-cut placement partitions each region in isolation: a cell inside region R connected heavily to cells far outside R gets sorted by purely internal logic, and wirelength suffers. Dunlop and Kernighan's terminal propagation fixes this with one mechanism. When partitioning region R, take every net that connects R's cells to cells already assigned elsewhere; project each such external connection's position onto R's boundary; and create there a fixed pseudo-terminal belonging to that net. The partitioner now sees these terminals as immovable members of one side, so its cut objective naturally pulls the net's internal cells toward the side nearest their external partners. Nets whose projection lands ambiguously in the middle band are left unpropagated to avoid noise.

Why it was decisive

This one change converts min-cut from a pure netlist clusterer into a genuinely geometric placer: information flows top-down through the recursion, and each local cut now optimizes a sensible surrogate of global wirelength. Published results moved min-cut placement from curiosity to industrial standard, and the technique became mandatory in every serious min-cut placer afterward, including Capo. The idea also generalized: analytical placers doing region-wise refinement use the same project-and-fix trick when solving subproblems.

Where you meet it today

Inside any partitioning-based placement or clustering flow worth its salt, and as a beautiful interview answer to "how do you make local optimization respect global context?"