What is the quadratic placement objective function actually minimizing, and what's its well-known real limitation?
From PDVerse PnR Interview Handbook · pdVerse Mentor Guide
Short Answer
Quadratic placement minimizes total squared wire length: Phi(x,y) = 1/2 sum(c_ij) [(xi-xj)^2 + (yi-yj)^2]. With a symmetric connectivity matrix C and modified matrix B=D-C (D diagonal, d_ii = sum of c_ij), this reduces to Phi(x,y) = x^TBx + y^TBy -- because x and y are symmetric and independent, only a 1-D problem needs solving in each dimension. The main problem: it creates very high cost for long wires and very low cost for short wires, so a highly-connected cluster can spread out over the core, increasing congestion and reducing routing-resource flexibility.
Technical Explanation
- Quadratic placement minimizes total squared wire length: Phi(x,y) = 1/2 sum(c_ij) [(xi-xj)^2 + (yi-yj)^2], an analytical (not partition-based) approach that assumes point instances and two-point nets.
- With connectivity matrix C=[c_ij] and modified matrix B=D-C (D diagonal, d_ii = sum of c_ij), this reduces to Phi(x,y) = x^TBx + y^TBy -- because x and y are symmetric and independent, this becomes two separate 1-D problems rather than one combined 2-D problem.
- The MAIN PROBLEM: the squared term creates very high cost for long wires and very low cost for short wires -- a strongly nonlinear penalty.
- As a direct consequence, a highly connected cluster can spread OUT over the core (since the quadratic penalty punishes any single long wire heavily, favoring many medium-length wires over a compact cluster), increasing congestion and reducing routing-resource flexibility -- the opposite of what a compact, well-clustered placement would look like.
Formula Or Decision Rule
Phi(x,y) = 1/2 sum(c_ij) [(xi-xj)^2 + (yi-yj)^2] = x^TBx + y^TBy, where B = D - C.
What To Check
- Warning sign: a highly connected functional cluster (e.g. a tightly-coupled datapath) ends up spread across a wide area after global placement rather than tightly grouped.
- Inspect: consider whether the quadratic objective's known spreading tendency for highly-connected clusters explains this, rather than assuming a placement bug.
- Correct: this is a documented limitation of the quadratic objective itself -- mitigations (clustering, attraction constraints) may be needed for clusters where this matters.
Command Checks & Actions
create_bound -type soft -boundary {...} [get_cells ...]Verify exact command/flags against the ICC2 Implementation User Guide’s placement/floorplanning chapter -- defines a soft placement region around a highly connected cluster, the real region/bound-based mitigation for the quadratic objective’s spreading tendency.
Healthy, Suspicious & Hard-stop Results
- Expected: highly connected functional clusters remain reasonably compact after global placement, with any known spreading tendency mitigated by explicit attraction constraints where it matters.
- Investigate: a known tightly-coupled cluster (e.g. a datapath) is spread unexpectedly wide after placement -- consider the quadratic objective's documented limitation as a likely explanation.
- Stop: a highly connected cluster's spreading is treated as an unexplainable placement anomaly, when it's actually a documented characteristic of the quadratic objective function's nonlinearity.
Common Mistake
The Trap: Assuming minimizing squared wire length is equivalent to minimizing actual (linear) wire length -- the quadratic penalty's nonlinearity is exactly what causes the spreading-out problem for highly connected clusters, a real, documented limitation, not a minor detail.
What The Interviewer Is Testing
Whether you can state both the actual formula AND its well-known limitation (spreading of highly connected clusters), not just that quadratic placement "minimizes wire length."
Practical Example
Debug Scenario: A tightly-coupled arithmetic datapath ends up spread across a wider area than expected after global placement, increasing local congestion. This is consistent with the quadratic objective's documented tendency to spread highly connected clusters -- a soft create_bound region around that datapath's cells is one practical mitigation (verify exact flags against the ICC2 guide).
Physical Design & Planning Handbook
Master ASIC Physical Design Planning & Floorplanning
Dive into 14 comprehensive chapters covering netlist sanity, FinFET grids, macro placement, power grids, CTS, and timing budgeting.
Continue practising