Explore / Methods & Algorithms / Placement / PROUD

PROUD

Placement research 1988 Tsay, Kuh, Hsu quadratic solve at scale needs fixed anchors

The idea

Replace each multi-pin net with two-pin springs (a clique or star model). Total squared wirelength becomes, per axis, the quadratic form

Φ(x) = x'Qx − 2 b'x
  • x vector of all movable cell coordinates (one axis at a time)
  • Q sparse connectivity matrix: the graph Laplacian of the spring network
  • b constant pull exerted by fixed objects: pads and pins

where Q is the sparse, symmetric, positive semi-definite graph Laplacian of connectivity and b carries the pull of fixed objects: pads and pins. Setting the gradient to zero gives a sparse linear system; solving it (successive over-relaxation then, preconditioned conjugate gradients now) yields, in one shot, the placement minimizing squared wirelength. This is also the physical equilibrium of a spring network, and the numerical linear algebra scales to enormous netlists.

One catch defines everything after: without constraints, minimizing springs collapses all cells toward the anchors' centroid, a placement that is optimal and useless. PROUD's answer was hierarchical: solve globally, split the die, assign cells to halves by their solved coordinates, then re-solve each half with the other half's cells projected onto the boundary as fixed anchors (terminal propagation, analytically reborn), recursing until regions are small.

Why it mattered

PROUD demonstrated that placement could be numerics instead of combinatorics, at sea-of-gates scale, years before annealing hit its wall. Its solve-partition-resolve loop is the direct template for GORDIAN and the quadratic school that followed.

Where you meet it today

As the historical opening of the lineage that leads through GORDIAN, FastPlace, and ePlace to every modern placer's quadratic warm start.

References and further reading