arXiv cs.AI· Kadhir Parani, Manjunath Bezawada, Divya M, Kesana Jathin, Kolli Sarath, Sm Zobaed·· 1 小时前AI 评分48
GEO-Exact 求解器在数秒内证明 HBT 合法化最优解，揭示优化空间真实所在
Provably Optimal HBT Legalization in Seconds: Certified Optima Reveal Where the Headroom Really Lies
AI 导读
研究者基于 Open3DBench 布局数据构建包含 21 个设计/pitch 实例的开源基准，并提出精确求解器 GEO-Exact，通过对偶证书证明全部 21 个实例的解最优（原始-对偶间隙至多 8.2×10⁻¹⁶）。
正文 · 原文
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.
| Subjects: | Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.14928 [cs.AI] |
| (or arXiv:2611.14928v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2611.14928 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Sm Zobaed [view email]
[v1]
Wed, 11 Nov 2026 02:32:50 UTC (981 KB)
来源：arXiv cs.AI · arxiv.org