APlace and NTUplace (Log-Sum-Exp Placement)

The idea

Quadratic placement optimizes the wrong function: squared spring length over-penalizes long nets and only approximates the half-perimeter wirelength (HPWL) that flows actually care about. The nonlinear school optimizes a smoothed HPWL (Half-Perimeter Wire Length) directly. Per net, max(x) is approximated by the log-sum-exp function

• x_i the pin coordinates of one net (per axis)
• γ smoothing parameter: smaller means closer to the true maximum, and sharper to optimize

(and min analogously), which is differentiable everywhere and approaches the true maximum as γ shrinks. Overlap is handled by a smoothed density model: each cell spreads its area into bins through a bell-shaped kernel, and a penalty term punishes bins above target density. The sum, smoothed wirelength plus weighted density penalty, is minimized by conjugate-gradient descent inside a multilevel scheme (cluster, place, uncluster, refine), with the penalty weight and γ tightened as placement matures.

What it changed

APlace demonstrated the formulation's power by winning placement contests of its era; NTUplace3 hardened it for mixed-size designs with macros and legalization-aware refinements. Together they established the template, objective-plus-penalty nonlinear optimization under a multilevel schedule, that defines modern placement. ePlace kept exactly this skeleton and swapped the density model for electrostatics; the wirelength side today often uses the weighted-average smoothing as an alternative to log-sum-exp, but the architecture is unchanged.

Where you meet it today

As the direct parents of ePlace/RePlAce and DREAMPlace: the math in those placers' wirelength gradients is this page's math, running on a GPU (Graphics Processing Unit).