Give millions of standard cells exact positions so that wirelength is short, timing closes, and the router can finish. Placement research runs from 1970 graph partitioning through annealing to today's electrostatics-based analytical solvers running on GPUs (Graphics Processing Units).
Before anything is placed, netlists get cut into pieces. These three algorithms are the cutting tools the whole field leans on, in placement and far beyond.
Improve a bipartition by tentatively swapping the best-gain pair of nodes, locking them, and continuing; then keep the best prefix of the whole swap sequence. Hill climbing that can climb out of shallow local minima.
Single-vertex moves, a gain-bucket data structure, and true hypergraph cut handling make Kernighan-Lin's idea run in linear time per pass. The refinement engine of physical design ever since.
Coarsen the hypergraph by clustering, partition the small version, then uncoarsen while refining at every level. The V-cycle that made million-node partitioning routine.
Recursively bipartition netlist and die together and let cut minimization stand in for wirelength. The dominant school of the 1980s and 1990s, and the engine of the last great min-cut placer in 2000.
Recursively slice the die and the netlist together, assigning cells to regions so few nets cross each cut line. The placement school that partitioning built.
When recursing into a region, project outside connections onto its boundary as fixed pseudo-terminals, so the partitioner inside feels the pull of the world outside.
A fast, clean, open min-cut placer: multilevel bisection with terminal propagation, careful tolerance control, and end-case placers, tuned until min-cut ran out of road.
For a decade the quality king: move cells at random, accept uphill moves with cooling probability, and let the physics metaphor grind out excellent placements slowly.
Model wirelength as a differentiable function and descend it. From quadratic solvers of the late 1980s to the electrostatics formulation that powers OpenROAD and GPU (Graphics Processing Unit) placers today, this lineage won.
Model nets as springs and solve the resulting sparse linear system for all cell coordinates at once, then partition and re-solve regionally. Analytical placement's opening move.
Global quadratic optimization with explicit center-of-mass constraints per region, refined by recursive partitioning; final placement by slicing-style area assignment. The quadratic school's canonical form.
Add to the spring system an explicit spreading force computed from cell density via a Poisson equation, and iterate: each solve moves cells as if charged, until density evens out.
Quadratic placement made fast: a hybrid net model that kills clique blowup, cell shifting with anchor springs for spreading, and cheap local refinement, delivering competitive wirelength at a fraction of the runtime.
Stop squaring: approximate half-perimeter wirelength directly with the smooth log-sum-exp function, add a bell-shaped density penalty, and descend with nonlinear optimization. The nonlinear school that closed the wirelength gap.
The multilevel V-cycle applied to placement itself: cluster the netlist, place coarse, interpolate down, and relax at every level with nonlinear optimization.
Cells become positive charge, density becomes electric potential solved by fast Fourier transform, and Nesterov's accelerated gradient descends smoothed wirelength plus system energy. The formulation modern placement runs on.
ePlace hardened for practice: dynamic step control, density-function refinements, and routability-driven inflation, shipped open source and adopted as OpenROAD's global placement.
The observation that analytical placement's math is the math of training a neural network, so run it on GPU deep learning infrastructure: same quality, tens of times faster.
Global placement leaves cells overlapping and off-row. These algorithms snap everything legal and then polish locally, where the last percent of quality lives.
Sort cells (typically by x), then place each in turn at the nearest legal free slot across the rows, like dropping Tetris pieces. Crude, quick, everywhere.
Legalize cell by cell, but within each candidate row solve exactly: cluster colliding cells and position clusters to minimize total squared displacement by dynamic programming over merges.
After legality: local swaps, single-row dynamic programming, independent-set matching, and window re-placement, iterated until wirelength stops improving.