FastPlace

The idea

By 2004 analytical placement's quality was established and its runtime was the battleground. FastPlace attacked every cost center. The hybrid net model replaces cliques on large nets with a star (one virtual node) and keeps cliques only for small nets, provably equivalent in the quadratic sense but collapsing the number of spring terms from quadratic to linear in pin count, which alone transforms solver time. Cell shifting handles spreading without heavy computation: examine density row by row, stretch overfilled stripes so cells shift toward whitespace, then add for each cell a light anchor spring to its shifted position and re-solve; a few solve-shift rounds spread the design smoothly. Iterative local refinement then trades squared for real objectives: quick greedy moves of cells between neighboring bins driven by half-perimeter wirelength gain.

What it proved

Competitive wirelength at speedups reported as an order of magnitude or more over contemporary annealing and min-cut placers, and the paper's components became standard vocabulary: hybrid net models are simply how quadratic placers are built now, and anchor-spring iteration became the backbone of the SimPL/ComPLx generation (anchors to legalized shadow placements) and of today's warm starts.

Where you meet it today

Its net model and anchor mechanics are used in most placers' quadratic phases; FastPlace itself, with its detailed-placement companion FastDP, remained a widely used academic baseline for years.