CS Paper Radar

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

Pengwen Chen, Chung-Kuan Cheng, Shao-Yun Fang, Chester Holtz, Sheng-Tan Huang, Susmita Sur-Kolay, Yucheng Wang, Ying Yuan

cs.AR ·submitted 2026-11-17 08:45 UTC · v1

Abstract

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.

Comment
14 pages, 6 figures, 5 tables. Submitted to IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD)

Closest papers

Nearest neighbours by meaning across the whole index.

Sequential Object Placement Optimization with Convex Decomposition

cs.RO ·2026-08-25 ·Yuezhe Zhang, Xiangyu Lyu, Sohan Rudra, Davide Tateo, Georgia Chalvatzaki
similarity 0.60
Abstract

Robotic object packing has been a core challenge for robotic deployment in logistics, industry, etc., due to the curse of dimensionality in combinatorial search and the difficulty of dealing with dynamic collision constraints for irregularly shaped objects. Current heuristic and learning-based methods mainly assume a limited spatial discretization resolution of space, and computation becomes extremely inefficient as discretization accuracy increases. In this work, we eliminate this assumption by introducing SOPO-CD, which frames sequential object placement as a differentiable nonlinear optimization problem with hard constraints in a decomposed free space. We formulate the constraints of placing a convex object inside a convex hull as constraining the vertices of the object to lie inside the convex hull. The constraints and their derivatives can be written in closed form and calculated efficiently. We implement a custom solver that achieves local-optimal placements within tightly constrained space in milliseconds; a $50 \times$ speedup compared to a fine-grained grid search method. We evaluate our framework on 2D Tangram, 2D Tetris, and 3D Bin Packing, and have demonstrated strong computational performance and packing utility. We also demonstrate its real-world applicability for solving the Tangram puzzle using a robot equipped with a dexterous hand.

0.33

Toward Near-Optimal Floorplanning with Complex Design Constraints for Modern SoCs

cs.AR ·2026-10-25 ·Fuxing Huang, Hao Ai, Qiyuan Chen, Hao Wu, Wenxing Zhu +2 more
publishedbenchmark similarity 0.56
Abstract · 9 pages, 7 figures, Accepted by International Conference on Computer-Aided Design (ICCAD) 2026

Modern system-on-chip (SoC) floorplanning is increasingly challenged by highly coupled complex design constraints. Existing methods often relax constraints into objectives via multi-objective optimization, leading to infeasible solutions or degraded quality. To address this, we formulate the problem as a constrained optimization task and propose a novel three-stage analytical framework integrating semidefinite programming (SDP), augmented Lagrangian method (ALM), and second-order cone programming (SOCP), which enforces constraints more rigorously and achieves higher-quality solutions. First, we adopt a two-step SDP formulation to obtain a robust initialization in the non-convex search space. Next, we incorporate differentiable objectives and constraints into an incremental ALM to jointly handle coupled design constraints during global floorplanning. Finally, an SOCP-based legalization strictly enforces feasibility while further reducing area. Experiments on the FloorSet benchmark show that our method satisfies all constraints with the fastest runtime. Compared with state-of-the-art methods, it reduces wirelength and area by 90\% and 16\% on average, and achieves near-optimal results, with wirelength and area being merely 2\% and 1\% larger than the ground-truth references, respectively.

0.51

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

cs.AR ·2026-10-20 ·Fuxing Huang, Hao Ai, Wenxing Zhu, Xinning Liu, Ziran Zhu
benchmarktheory similarity 0.54
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.

0.26

Topology optimization with buckling constraints: Adaptive eigenvalue aggregation and modality identification

cs.CE ·2026-09-17 ·Badvelu Pranay Prabha, Prabhat Kumar
similarity 0.52
Abstract · 33 pages

This paper presents novel approaches to tackle two key challenges in topology optimization problems with buckling constraints: determining how many eigenvalues to aggregate and identifying the eigenvalue modality at the optimal design. We demonstrate the mathematical inconsistencies that arise when choosing an arbitrary fixed number of eigenvalues for aggregation. Specifically, if the multiplicity of the critical eigenvalues is smaller than the chosen subset size, coalescence with higher-order eigenvalues can occur. Neglecting these during aggregation causes incorrect sensitivities, while simply increasing the preselected eigenvalue count unnecessarily raises computational costs. To resolve this issue, we propose an approach that dynamically determines the exact number of eigenvalues required at each optimization iteration. The proposed approach reduces computation time significantly while maintaining competitive performance relative to the conventional method across the numerical experiments presented. Additionally, accurately predicting modality at the optimal point is crucial for understanding the buckled mode shapes of optimized designs. A new optimization formulation is proposed using the difference between eigenvalues to capture the true eigenvalue modality. This formulation is first validated on a classical 1D clamped column, successfully predicting both the bimodal solution and the optimal eigenvectors. The approach demonstrates that the optimal solutions for the wall reinforcement and shear-loaded hinged plate problems for the given set of parameters are trimodal and tetramodal, respectively.

0.27

PlaceReasoner-Beta: Reasoning-Driven Macro Placement and Benchmarking

cs.AI ·2026-09-18 ·Qiufeng Li, Chengxuan Wang, Rongqian Chen, Quan Cheng, Yihui Ren +4 more
benchmarkcode/data similarity 0.52
Abstract · Code and benchmark are available at \url{https://github.com/fenggev56/PlaceReasoner-Beta}

Automated macro placement remains a fundamental challenge in VLSI physical design. Despite decades of research, existing approaches predominantly optimize hand-crafted proxy objectives, such as estimated wirelength, and typically produce placements through one-shot numerical optimization, limiting their ability to incorporate visual layout context, codified design expertise, and downstream physical-design feedback in a unified loop. We present PlaceReasoner-Beta, a verifier-guided multi-agent framework that reformulates macro placement as a closed-loop reasoning problem rather than black-box optimization. A vision-language model (VLM) planner generates candidate placements from the floorplan image, macro specifications, and connectivity structure; a geometric verifier enforces physical legality and expert placement principles; a physical verifier refines candidates using early implementation feedback; and a post-route optimizer further improves promising layouts using final PPA. To enable reproducible evaluation, we introduce PlaceReasoner-Bench, a fully open end-to-end benchmark built from open RTL designs, EDA tools, and technology libraries. It comprises 8 designs at two aspect ratios, yielding 16 tasks with fixed floorplans and I/O assignments, so methods differ only in macro positions and orientations and are evaluated using routed PPA and DRC rather than pre-route proxies. Across the benchmark, PlaceReasoner-Beta achieves the best timing among DRC-clean methods on all square tasks, reducing post-route TNS by 61.2% at 1:1 and 53.0% at 2:1 relative to the classical baseline field. It also shortens routed wirelength on most designs despite never explicitly optimizing it, demonstrating that reasoning over spatial structure under physical-design feedback can improve end-to-end layout quality beyond proxy-objective optimization.

0.59

S4R: Scaling for Rigid-Body Interpenetration Resolution

cs.GR cs.CGcs.RO ·2026-09-17 ·Zhiyang Dou, Ang Zhao, Chen Peng, Minghao Guo, Haixu Wu +6 more
publishedcode/data similarity 0.51
Abstract · ACM Transactions on Graphics 45(6), Article 197 (SIGGRAPH Asia 2026). Project page: https://frank-zy-dou.github.io/projects/S4R/index.html

Rigid-body interpenetration frequently occurs in procedurally assembled and generated scenes and must be removed before downstream applications such as physical simulation. We present S4R (Scaling for Rigid-Body Interpenetration Resolution), a scale-continuation method for static interpenetration repair. S4R first uniformly shrinks each body about a fixed reference center to a small initial scale, at which the layout is penetration-free, and then restores full scale through a sequence of minimum-norm convex contact quadratic programs (QPs) that target the linearized separation margin during continuation. Resolution thereby replaces one deep correction with a sequence of shallow-contact subproblems. A conservative scale-event bound and frozen-witness gap predictions cut the number of exact mesh queries; the continuation then ends with a full-scale evaluator check and bounded tail refinement. We evaluate S4R on Kubric, HY3D-Bench, and Thingi10K using a shared mesh-level evaluator and a unified per-scene timing protocol. In the main comparisons on all three benchmarks, up to N=5000 bodies, S4R reaches zero reported penetration with displacement that stays small and nearly independent of scene size, and at the lowest wall time within each hardware tier among the compared methods. A GPU implementation extends these results to large-scale scenes. Our code and data can be found on our project page: https://frank-zy-dou.github.io/projects/S4R/index.html.

0.51

Coarse-to-Fine Macro Placement via Evolutionary Search and Critical Macro Tuning

cs.AR ·2026-09-28 ·Biao Liu, Zhiping Jin, Kaixuan Sun, Zengrui Lu, Qingquan Zhang +1 more
benchmarkcode/data similarity 0.50
Abstract · 18 pages

Macro placement is a critical stage in chip physical design that substantially affects downstream implementation quality. Recent search-based methods improve existing layouts through partial reconstruction, but quality-biased or spatially restricted macro selection can limit the diversity of reconstruction proposals, potentially hindering escape from local optima. Moreover, coarse-grid representations restrict placement precision. To address these challenges, we propose C2FPlace, a \textbf{C}oarse-to-\textbf{F}ine macro \textbf{Place}ment framework that integrates population-based evolutionary search with fine-grained refinement. During coarse-grained optimization, tournament selection chooses promising parents from randomly sampled groups of layouts, and stochastic partial rip-up and re-place generates offspring by sampling macro subsets across the entire layout. A two-phase schedule samples reconstruction ratios from a higher range early in the search and a lower range later, supporting broad exploration followed by more conservative refinement. During fine-grained optimization, critical macro tuning enables positional adjustments beyond the coarse grid to obtain additional half-perimeter wirelength (HPWL) reduction. Experiments on the ISPD2005 benchmark show that C2FPlace reduces HPWL by 17.82\% over EGPlace and 17.86\% over RollPlace on average. On the ICCAD2025 benchmark, C2FPlace achieves the best average ranking among the compared methods under the evaluated power, performance, and area (PPA) metrics. Our codes are available in \href{https://github.com/lxxxxb/C2FPlace}{https://github.com/lxxxxb/C2FPlace}.

0.40

A practical DIRECT-type algorithm for medium-scale black-box global optimization

cs.LG math.NA ·2026-09-09 ·Linas Stripinis, Remigijus Paulavičius
publishedbenchmarkunusual similarity 0.50
Abstract · 46pages, 13 figures, 4 tables

The DIRECT algorithm is a deterministic global optimization method known for its versatility and balanced exploration-exploitation strategy. However, DIRECT-type algorithms are primarily effective for low-dimensional problems and often exhibit slow convergence as dimensionality increases, limiting their applicability to more complex optimization tasks. To address this limitation, this paper introduces X-DTC-GL, a novel DIRECT-type algorithm that incorporates dynamic partitioning and hybridization techniques. The dynamic partitioning approach adaptively refines the search space based on local one-dimensional surrogate models, enabling rapid subdivision of promising hyper-rectangles. The hybridization strategy selectively employs a hill-climbing method to exploit promising regions identified by the surrogate models. Extensive experiments on four diverse benchmark suites demonstrate that X-DTC-GL significantly outperforms existing DIRECT-type baselines, achieving improvements of ~12% in solvability and ~27% in solution quality. Performance-profile analyses indicate the fastest convergence on up to ~40% of instances, the best runtime performance on ~17% of problems, and competitive overall execution times. By improving performance within the partition-based framework, these advances strengthen the algorithm's competitiveness in state-of-the-art black-box optimization.

0.54