CS Paper Radar

DiffRMST: A GPU-Accelerated Fully Differentiable Rectilinear Minimum Spanning Tree Wirelength Model for Global Placement

Fuxing Huang, Hao Ai, Wenxing Zhu, Xinning Liu, Ziran Zhu

cs.AR ·submitted 2026-10-20 14:07 UTC · v1
benchmarktheory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Differentiable Partitioning With Dual-Max 3D Wirelength Model and Hybrid Bonding Terminal Awareness for Optimized 3D Placement

cs.ET ·2026-09-06 ·Liwen Jiang, Xu Shi, Rufeng Xiao, Changhao Yan, Rujun Jiang +2 more
similarity 0.60
Abstract

Research on 3D integrated circuits (3D-ICs) physical design has expanded rapidly in recent years, driven by the increasing adoption of hybrid bonding and the demand for higher integration density. Continued scaling of hybrid-bonding pitch supports higher vertical interconnect density and finer-grained circuit partitioning in 3D-ICs. Hybrid bonding-enabled 3D-ICs offer substantial benefits in interconnect scaling and system integration, yet tier assignment remains challenging because it jointly determines 3D wirelength and hybrid bonding terminal (HBT) assignment. This paper presents a differentiable partitioning framework that directly optimizes placement-aware tier assignment for 3D-ICs through gradient-based optimization. Discrete tier assignment is relaxed to continuous probabilities, and a Dual-Max 3D wirelength model is introduced as a placement-aware surrogate for tier-specific half-perimeter wirelength (HPWL). In addition, a terminal-aware cutsize penalty gives higher weights to cross-die nets with predicted HBT overlaps, and a local balance penalty discourages regional area overflow on each tier. On ten OpenROAD benchmarks, our method reduces final die-to-die (D2D) HPWL by 8.05% and 14.81% on average relative to hMETIS and TritonPart, respectively. On the seven benchmarks with available CoPlace results, the average HPWL reduction is 10.33%. The source code for the differentiable partitioner and the integrated 3D placement flow is publicly available to support reproducibility.

0.43

Buy-at-Bulk Facility Location on Trees

cs.DS ·2026-08-26 ·Shamisa Nematollahi, Daniel Vaz
similarity 0.59
Abstract · Presented at WAOA 2025

We consider the buy-at-bulk facility location problem (BBFL), a problem combining the classic facility location problem with buy-at-bulk network design, which finds motivation in telecommunication networks. In it, we are given a graph with edge lengths, opening costs and demands for each vertex, and a monotone and subadditive capacity-cost function, and our task is to open facilities on a subset of the vertices and route the demand from each vertex to these facilities. The cost of a solution (which we want to minimize) is given by the opening costs of the chosen facilities, plus the cost on each edge, which is given by its length times the cost of providing enough capacity for the demands through the edge, given by the capacity-cost function. A common variant of the problem, the $k$-cable facility location problem (kCFL), considers the case where capacity is provided by buying copies of given cable types, each with a certain capacity and cost. We study BBFL on tree instances and show, for the unit-demand and splittable variants, that the problem admits a PTAS (a $(1+ε)$-approximation for any $ε> 0$). We also consider kCFL in the new setting of cable-unsplittable demands, where the demand of a vertex cannot be split among multiple cables. We show that the problem is NP-hard to approximate to a factor better than $3/2$ on stars, and then provide an algorithm for tree instances that outputs a solution with optimal cost, but which exceeds the capacity on each cable by a factor of $1+ε$. As a consequence, we show that the problem has a $2$-approximation algorithm on trees.

0.28

Pairwise Reconnection for Cost-Distance Steiner Trees

cs.DS ·2026-11-06 ·Edgar Perner
theory similarity 0.58
Abstract

The Uniform Cost-Distance Steiner Tree Problem asks for a rooted tree that minimizes the connection cost plus a weighted sum of root-to-terminal distances. We develop an algorithm that constructs two candidate trees: one based on direct connections to the root and another that pairs selected vertices and connects each pair to the root. The algorithm selects the tree with the smaller objective value. The resulting randomized algorithm achieves expected approximation factors of $1.698$ in the spanning case and $2.041$ in the general case, and it can be derandomized in polynomial time. The pairwise matching analysis charges part of the augmentation cost directly to the connection and delay costs of an optimal solution, rather than only to the separated lower bound used in previous analyses. This allows the $1.698$ factor to fall below the maximum multiplicative gap of $1+1/\sqrt{2}$ between the optimum value and that lower bound. We give instance families with approximation-ratio lower bounds approaching $1+1/\sqrt{2}$ for cut-and-reconnect algorithms that start from a minimum spanning tree and $3/2$ for the present algorithm. Finally, we show that the Uniform Cost-Distance Steiner Tree Problem and the Steiner-tree version of the Cable-Trench Problem are approximation equivalent up to an arbitrarily small additive loss.

0.20

Dynamic Steiner Tree under Edge Updates

cs.DS ·2026-11-03 ·Jeff Giliberti, MohammadTaghi Hajiaghayi, Mohammad Mahdavi, Xinchen Yang
hot direction similarity 0.55
Abstract

The Steiner tree problem is the canonical generalization of minimum spanning tree (MST). When connectivity is required only among a fixed subset of vertices (terminals), the goal is to maintain a minimum-cost tree connecting these terminals as the graph undergoes edge updates. While dynamic MST has been studied since the 1980s~[Frederickson, STOC'83, SICOMP'85], and the first sublinear-in-$n$ dynamic MST algorithm dates back almost thirty-five years to Eppstein, Galil, Italiano, and Nissenzweig~[FOCS'92, JACM'97], achieving sublinear-in-$n$ update time for dynamic Steiner tree has long remained open, as a single edge update can invalidate many routes in the underlying terminal metric closure. We present the first fully dynamic algorithm for Steiner tree that achieves a constant-factor approximation with sublinear-in-$n$ update time. For any fixed $0<ζ<1/2$, our deterministic algorithm maintains an $O_ζ(1)$-approximate Steiner tree for undirected graphs with polynomially bounded edge weights in $\widetilde O(n^{1/2+ζ})$ amortized update time, answering cost queries in $O(1)$ time, and reporting an explicit tree in $\widetilde O(n^{1+ζ})$ time. Our approach combines periodic terminal-metric rebuilds on a dynamic spanner with a top-tree dynamic program that localizes edge deletions and reconnects surviving components through a dynamic distance sparsifier. Along the way, we give a simpler randomized insertion-only algorithm with a better, explicit approximation ratio.

0.25

Mixed-Size Placement Initialization via Stiefel-Manifold Sequential Subspace Optimization

cs.AR ·2026-11-17 ·Pengwen Chen, Chung-Kuan Cheng, Shao-Yun Fang, Chester Holtz, Sheng-Tan Huang +3 more
similarity 0.54
Abstract · 14 pages, 6 figures, 5 tables. Submitted to IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)

Mixed-size global placement simultaneously optimizes the locations of large macros and millions of standard cells in modern very-large-scale integration (VLSI) physical design. State-of-the-art analytical placers achieve strong scalability, but their nonlinear objectives and density handling make them sensitive to the initial placement. This paper presents a geometry-driven framework that formulates placement initialization as a Quadratically Constrained Quadratic Program (QCQP) with first-order centroid and second-order spreading constraints. Explicit mixed-size spreading targets are derived from the die geometry and object sizes, to obtain stable constraint values even under extreme size variation. A utilization-aware rescaling of the constraint matrix prevents pathological spreading when fixed objects occupy significant die area. The QCQP is then transformed into a Stiefel-manifold optimization through metric equalization and centering projection, making the underlying geometric structure explicit. The resulting Stiefel-constrained quadratic objective admits efficient large-scale optimization via a Riemannian sequential subspace method (SSM). An angle-sorted cycle sparsification for multi-pin nets periodically keeps the Laplacian approximation sparse yet geometry-consistent. As a drop-in initializer for existing analytical placers, our method yields improvements in weighted half-perimeter wirelength (wHPWL): 13.8% average under RePlAce on the four TILOS benchmarks supported by its flow, 3.5% under DREAMPlace on all 20 benchmarks, and 4.8% under AutoDMP on 19 benchmarks with converged baselines. Post-route evaluation shows that these pre-route improvements carry through to routed designs: routed wirelength decreases by 1.1 to 2.3% on all three benchmarks. Standard-cell area and power also decrease on all three. Design-rule-check (DRC) violations decrease on two of the three.

0.27

Budget-Constrained Graph Augmentation for Robust Network Design via Kirchhoff Index Minimization

cs.SI math.OCeess.SP ·2026-09-24 ·Omkar Bhoite, V Sateeshkrishna Dhuli, Stefan Werner, Kimmo Kansanen
benchmarktheory similarity 0.52
Abstract · 12 pages, 7 figures, 3 tables. Submitted to IEEE Transactions on Network Science and Engineering. A preliminary version of this work was pre…

Enhancing the robustness of deployed networks against failures and disruptions is critical for reliable operation. This requires deciding which new links to install and how strongly to weight them under limited resources. We study this problem through the Kirchhoff index, or total effective resistance, a spectral measure of global connectivity. The resulting augmentation problem couples discrete candidate-edge selection with continuous weight allocation under heterogeneous per-unit deployment costs, a total budget, and an exact-cardinality constraint. For a fixed weighted base graph, this yields a mixed-integer formulation and a semidefinite relaxation whose optimum lower-bounds the mixed-integer optimum. We cast the relaxation as a cone program and solve it numerically using a homogeneous self-dual embedding and first-order operator splitting. Feasible discrete designs are recovered through rounding-and-repair procedures and assessed by \emph{a posteriori} gap estimates relative to the numerical semidefinite program (SDP) benchmark. As a scalable alternative, we develop an exact-$k$, budget-feasible greedy heuristic built on rank-one Laplacian updates and biharmonic-distance caching, and interpret its progress through a Bellman value-to-go benchmark with a conservative spectral lower bound on the local policy ratio. Experiments on synthetic and real infrastructure networks across graph sizes, budgets, weight distributions, and cost regimes show that, under fixed budgets, distance-proportional costs limit the achievable resistance reduction and shift installed conductance toward shorter links relative to uniform per-unit costs.

0.21

A Framework for Enterprise Network Dimensioning

cs.IT ·2026-08-19 ·Gourab Ghatak
top venue similarity 0.52
Abstract

We study radio node (RN) placement for indoor enterprise networks. Using stochastic geometry (SG), we derive the meta-distribution (MD) of the SINR for a test user equipment (UE), with and without cooperation from outdoor macro base stations (MBSs), and compare these results with an integer linear programming (ILP) approach. SG provides an estimate of the required number of RNs but not their locations, while ILP can yield inaccurate local optima and requires high computational power. To address this, we investigate clustering-based algorithms for initializing RN locations using UE location distributions. Along with standard methods, we propose a weighted $k$-harmonic means (WKHM) clustering strategy tailored to maximize SINR. We then introduce a constrained sequential minimum cut algorithm, \texttt{SeqMinCut}, to merge multiple RNs into larger cells and further improve SINR. This is the first work that integrates SG-based statistical analysis, optimization, and clustering to obtain system design insights, dimensioning rules, and planning strategies for enterprise 5G.

0.37

APPlace: Co-Optimizing Device Locations and Access Points for Routing-Aware Analog Placement

cs.AR ·2026-10-29 ·Bingyang Liu, Xiaohan Gao, Souradip Poddar, David Z. Pan
top venuecode/data similarity 0.52
Abstract · Accepted to ASP-DAC 2027. 8 pages, 6 figures, 4 tables. Code: https://github.com/bingyang1132/applace

Analog layout automation remains challenging in Analog/Mixed-Signal circuit design, because parasitics and mismatches introduced during layout strongly affect circuit performance. Placement is especially critical among the layout stages, as it constrains the routing solution space and the achievable post-layout performance. Existing analytical placement methods optimize device coordinates under center-based wirelength proxies and leave access point (AP) selection to routing. In analog circuits, however, a routing pin is an extended piece of terminal metal rather than a fixed point, and the best AP on it depends on where the other connected devices are placed, so a coordinate-only placement optimizes for connection points that the router will not use. We present APPlace, a routing-aware analog placement framework that co-optimizes device locations and AP selections during global placement, followed by a legalization stage that preserves the structure established by global placement. Experimental results on four real-world analog benchmarks show that APPlace achieves better overall post-layout performance than representative baselines at comparable layout area. Ablation studies further show that removing AP co-optimization causes up to a 13 dB CMRR loss among the OTA benchmarks and a 23% increase in comparator delay.

0.87