DiffRMST: A GPU-Accelerated Fully Differentiable Rectilinear Minimum Spanning Tree Wirelength Model for Global Placement
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.