Abacus

The idea

Abacus keeps Tetris's outer loop (sort cells by x, insert one at a time, try rows near the target) but replaces the greedy 'nearest free slot' with an exact inner solution. When a cell is inserted into a row, place every cell in that row optimally, in order, minimizing the sum of squared displacements from desired positions. This is solvable exactly and incrementally by clustering: a new cell wants its desired x; if it would overlap its left neighbor cluster, merge them, and the merged cluster's optimal position is a weighted average of its members' desires (the quadratic optimum), possibly cascading further merges leftward. Each insertion is amortized cheap; the row is always optimally packed for the current membership; the cell finally commits to whichever candidate row yielded the smallest cost.

Why it became the default

Displacement drops dramatically versus Tetris (the paper reports large average-movement reductions), which preserves the global placer's carefully optimized wirelength and timing intent; runtime stays near-linear in practice; and the algorithm is compact enough to implement in an afternoon. It slots cleanly after any analytical placer.

Where you meet it today

Abacus or a close variant is the standard-cell legalizer in most academic flows and many production ones; OpenROAD's detailed placer performs Abacus-style row legalization before its optimization passes. Its cluster-merge mathematics also reappears in single-row optimization inside detailed placement.