Exact solver finds optimal terminal placement in 3d chip design quickly
Provably Optimal HBT Legalization in Seconds: Certified Optima Reveal Where the Headroom Really Lies
Artificial Intelligence
Summary
Placing tiny connection points, or terminals, on 3D chips is tricky and usually done with approximate methods that can be off by a bit. The authors built a tool called GEO-Exact that finds the best possible arrangement very quickly, proving exactly how close other methods come to the ideal. They tested it on a set of real design cases and confirmed their results with mathematical proofs. This helps chip designers know how much room for improvement their current placement methods really have.
What this means in practice
- •For 3d ic physical designers: Optimize terminal placement for hybrid bonded 3D ICs with guaranteed minimal displacement, reducing design errors and improving manufacturing yield.
- •For electronic design automation teams: Integrate a certified optimal legalization solver into placement flows to benchmark and improve heuristic terminal assignment algorithms.
Authors
Kadhir Parani, Manjunath Bezawada, Divya M, Kesana Jathin, Kolli Sarath, Sm Zobaed
Abstract
Hybrid bonding terminal (HBT) legalization assigns every terminal of a face-to-face 3D IC to its own pitch-grid site with minimum total Manhattan displacement. Open3DBench reports that a reinforcement-learning (RL) legalizer reduces displacement by 19-22% relative to a sliding-window (SW) heuristic, but none of its legalizers is publicly released. We ask how much displacement any legalizer can still recover. We build an open benchmark of 21 design/pitch instances from Open3DBench placement data, with reconstructed greedy, SW (ViaLegal-style) and BTAssign-style baselines, and GEO-Exact, an exact solver that runs successive shortest augmenting paths over lazily generated spatial candidate edges. An independent dual certificate proves its assignment optimal on all 21 instances (relative primal-dual gap at most $8.2 \times 10^{-16}$). Against these optima, our SW reconstruction with ViaLegal's default configuration is on average 0.011% above optimal (worst 0.119%), while on the 16 contended instances BTAssign-style, a density-guided heuristic (DGHL) and greedy are 3.0%, 6.9% and 64.5% above. Headroom does appear outside this regime: with 2x2 windows SW reaches 34.1%, and above about 58% utilization, on three of six swept designs, it reaches 21.1% on bp, 27.5% on swerv and 8.9% on jpeg (217 further certified instances, and ten bp points checked against an independent exact solver). If the published 19-22% gain were measured on instances like ours, SW would have to be at least 24-28% above optimal on average, far more than any SW variant we tested at nominal pitch; the RL paper's own comparison with the Hungarian optimum puts its SW 3.05% above optimal on average. GEO-Exact is also about an order of magnitude faster than DGHL and SW in our harness (geometric means 8.1x and 40x; a compiled core against Python baselines on a shared server). Code, optimal values and certificates are released.