Differentiable wirelength model speeds global chip placement using GPU
DiffRMST: A GPU-Accelerated Fully Differentiable Rectilinear Minimum Spanning Tree Wirelength Model for Global Placement
Hardware Architecture
Summary
Placing components on computer chips is tricky because you want to keep connections short, but figuring out the shortest paths between many points is very complex. The authors developed a new way to estimate these shortest connection paths that can be smoothly adjusted by a computer during placement design. Their method uses math tricks to look at many possible connection shapes at once, making it both accurate and fast. They also made their code run much faster using graphics processors, helping create better chip designs more quickly.
What this means in practice
- •For chip design engineers: Optimize global placement in integrated circuit design with a differentiable and efficient wirelength estimator that improves routing accuracy and runtime.
- •For hardware layout software developers: Integrate a GPU-accelerated, fully differentiable wirelength model to speed up and enhance chip placement tools.
Authors
Fuxing Huang, Hao Ai, Wenxing Zhu, Xinning Liu, Ziran Zhu
Abstract
Analytical global placement requires a differentiable wirelength objective that accurately reflects routed interconnect cost. The widely used half-perimeter wirelength (HPWL) is efficient but overlooks the internal topology of multi-pin nets. The rectilinear Steiner minimum tree (RSMT) provides higher fidelity, but its underlying decision problem is NP-complete, and its discrete construction precludes direct use in gradient-based optimization. The rectilinear minimum spanning tree (RMST) offers a polynomial-time alternative, but remains nondifferentiable because of minimization over discrete spanning trees. To address these limitations, we present DiffRMST, a fully differentiable RMST wirelength model for analytical global placement. DiffRMST combines spatial smoothing with a log-sum-exp relaxation to define a continuous distribution over spanning trees. Based on the Kirchhoff matrix-tree theorem, the partition function and edge marginals can be computed without explicit tree enumeration, enabling a closed-form topology-aware gradient for placement optimization. For efficient integration into analytical placement, we further develop a fused forward-backward operator with parallel CPU and GPU implementations. On the ISPD2019 benchmark suite, our method reduces RMST, RSMT, and routed wirelength by an average of 5.0%, 3.2%, and 3.5%, respectively, compared with the weighted-average baseline, while maintaining acceptable runtime. Furthermore, the GPU implementation achieves an average $14.7\times$ speedup in global placement over its eight-thread CPU counterpart.