WorksComputer Science
Mixed-Size Placement Initialization via Stiefel-Manifold Sequential Subspace Optimization
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.
Introduction
Placement is a central step in very-large-scale integration (VLSI) physical design: given a circuit netlist and a fixed die region, placement assigns locations to circuit components to enable subsequent routing and timing closure. Modern benchmarks and industrial designs are increasingly mixed-size, containing millions of standard cells together with tens to hundreds of macros (e.g., SRAMs, analog blocks, IPs) whose sizes may differ by orders of magnitude. This disparity in size, coupled with geometric feasibility, density control, and wirelength optimization, exacerbates numerical scaling issues in large-scale optimization [1].
Recent analytical placers formulate global placement as a large-scale continuous optimization that balances smooth wirelength approximations with density control and design constraints. Representative engines include ePlace [2] and RePlAce [3] for electrostatics-based density formulations, ePlace-MS [4] for explicit mixed-size handling, DREAMPlace [5] for GPU-accelerated placement, and AutoDMP [6] for automated parameter tuning in concurrent macro and standard-cell placement.
Although most of these engines scale to very large instances, the overall objective remains nonconvex and sensitive to modeling choices, numerical conditioning, and starting points [1, 7]. Prior work explicitly notes that variable initialization plays a critical role, especially for quality-focused placement [8]. Learning-assisted flows also report substantial sensitivity to random seeding and parameter settings [6]. A high-quality initial placement can place the optimizer in a favorable basin of attraction, and under the fixed iteration budgets used by practical placers, this can improve the final placement quality without changing the downstream flow.
Many existing initialization methods for placement can be grouped into two categories. Graph-spectral methods exploit Laplacian-based approximations derived from the circuit netlist, including the constrained spectral optimization via Quadratically Constrained Quadratic Programs (QCQP) introduced by Chen et al. [8] and the spectral filtering approach of Liu et al. [9]. Learning-based methods use reinforcement learning or graph neural networks for macro-level layout planning [10, 11]. Our work belongs to the first category and targets a specific gap in constrained spectral initialization for mixed-size circuits.
We investigate whether a structure-aware and constraint-preserving initializer can improve half-perimeter wirelength (HPWL) outcomes over common heuristic initializations in large-scale mixed-size placement. We build on QCQP formulations, but target stable mixed-size use in the presence of fixed objects and widely varying macro sizes. Our key observation is that QCQP equality constraints used in area-aware initialization already define a rich geometric structure: after metric equalization, the quadratic spreading equalities become an orthonormality condition on a Stiefel manifold [12]. Once this structure is made explicit, one can apply Riemannian optimization tools and sequential subspace methods (SSMs) for scalable optimization on the constraint set [12], [13].
Figure 1 gives a high-level overview. Starting from a mixed-size netlist, we build a sparse Laplacian approximation and a QCQP. The QCQP’s first-order constraints fix the area-weighted centroid. Its second-order constraints enforce area-weighted spreading, preventing degenerate solutions such as collapse to a single point. We then derive explicit mixed-size spreading constants, construct a well-conditioned constraint matrix, and transform the QCQP into a Stiefel-constrained optimization via metric equalization and centering projection. We solve the resulting Stiefel problem by SSM with Riemannian second-order steps, coupled with periodic angle-sorted cycle sparsification for multi-pin nets.
Figure 1. Pipeline of the proposed mixed-size Stiefel-based initialization, which outputs coordinates as a drop-in for downstream analytical placers.
Section § 2 details the specific challenges and gaps that
motivate each contribution. Our main contributions are:
Explicit mixed-size spreading targets derived from the die geometry and object sizes, which remain valid under extreme size variation (Section IV-A2);
Stable constraint construction that accounts for fixed objects, centering, and utilization-aware rescaling, preventing pathological spreading in early iterations and preserving feasibility (Sections IV-A3–IV-A4);
A Stiefel transformation that makes the QCQP constraint geometry explicit through metric equalization and projection, enabling scalable Riemannian optimization by SSM with second-order steps. (Section IV-B);
Geometry-consistent sparse modeling for multi-pin nets by integrating an update loop with an angle-sorted cycle sparsification to keep the Laplacian sparse while maintaining net geometry during initialization (Section IV-C);
Evaluation of our initializer as a drop-in replacement for common heuristic initializations, with downstream weighted HPWL (wHPWL) improvements across RePlAce [3], DREAMPlace [5], and AutoDMP [6] on 20 benchmarks (§ 5).
Relation to prior work. Chen et al. [12] develop the abstract Stiefel-SSM framework and its convergence theory for quadratic objectives on . This paper uses that solver framework after deriving a placement-specific Stiefel problem from a mixed-size QCQP. The required modeling steps include mixed-size spreading-target construction, fixed-object and utilization corrections, metric equalization of the movable-variable QCQP, and geometry-updated sparse Laplacian modeling. Compared with the sphere-constrained initializer of Chen et al. [8], the present formulation removes the averaged-size spreading simplification, incorporates fixed objects and centering directly into the movable-variable constraints, and uses the Stiefel-SSM solver with periodic angle-sorted-cycle updates.
The remainder of the paper is organized as follows. Section II discusses why mixed-size initialization is challenging and identifies gaps in existing approaches. Section III reviews placement notation, wirelength metrics, and Stiefel manifold basics. Section IV presents our mixed-size QCQP formulation, Stiefel transformation, and the Stiefel sequential subspace solver with update-loop sparsification. Section V reports experimental results on both industry and academic benchmarks, and Section VI concludes.
Motivation
Challenges of Mixed-Size Initialization
Mixed-size initialization is harder than its standard-cell-only counterpart for three related reasons.
Area-Aware Modeling: Mixed-size instances contain macros whose footprints differ by orders of magnitude from standard cells. Moreover, macros themselves vary widely in size, which further complicates the construction of spreading constraints. Ignoring object sizes causes severe overlap or collapse. Overcompensating causes over-expansion beyond the die. Effective initialization therefore requires size-aware spreading targets that account for each object’s individual dimensions [4, 7].
Initialization Sensitivity: Global placement objectives are highly nonconvex, and under finite iteration budgets different initializations converge to different basins, producing different wHPWL outcomes (see § 3-B for the formal definition). This motivates quality-focused initializers that provide a well-spread, structure-aware initial placement.
Normalization Difficulty: Large area disparities create ill-conditioned constraints, and fixed objects shift the free region and bias the centroid. A robust mixed-size initializer requires careful normalization, centering, and feasibility checks to avoid pathologies such as over-expansion or constraint indefiniteness (Section IV-A4 presents our solution).
Gaps in Existing QCQP Initialization
A prominent approach to constrained spectral initialization is to minimize a quadratic Laplacian wirelength approximation subject to first-order centroid and second-order spreading equalities, i.e., a QCQP. Despite strong empirical results, the mixed-size QCQP initialization still faces two practical difficulties.
Spreading-Target Construction Fragility: The most fragile part of QCQP initialization is often not the Laplacian objective but the spreading-target construction: building a feasible, well-conditioned constraint set when fixed objects, mixed sizes, and nontrivial utilization are present. Even when prior work demonstrates mixed-size experiments, the derivation and implementation of spreading targets are frequently simplified, leaving the constraint constants and matrix construction inadequate for varying macro sizes [8].
Quadratic Equality Constraints: Large-scale QCQP solvers for placement initialization can be numerically delicate, because quadratic equality constraints define a low-dimensional feasible set and amplify scaling issues in the presence of large area disparities [7]. These spreading-target construction issues are especially pronounced in industry-scale designs where a small number of macros dominate area and connectivity while interacting with a massive standard-cell population and multiple classes of fixed objects.
Stiefel Formulation: The two difficulties above share a common geometric root: the quadratic spreading equalities that enforce global spread define a generalized orthogonality constraint in the space of placement coordinates. After a metric-equalization step that absorbs the area weights and the spreading targets , this constraint reduces to the standard orthonormality condition , i.e., the feasible set becomes a Stiefel manifold. Making this structure explicit brings three practical benefits. First, feasibility is maintained by construction at every iteration, eliminating the fragile penalty-based or projection-based enforcement needed by generic QCQP solvers. Second, the smooth manifold geometry enables Riemannian Newton conjugate-gradient (Newton-CG) updates on tangent spaces. By incorporating local curvature information, these updates can improve convergence behavior under the ill-conditioning caused by large area disparities. Third, the Stiefel viewpoint decouples the centroid constraint from the spreading constraint via a rank-one projector, simplifying the overall problem without sacrificing sparsity. Section IV presents the details.
Background and Preliminaries
This section reviews the notation and background needed for the proposed method. We introduce mixed-size placement conventions, the wirelength metrics used for evaluation, and basic definitions for the Stiefel manifold. Table I summarizes the notation used throughout Sections III and IV.
| Symbol | Description |
| Netlist hypergraph | |
| Set of objects, set of nets | |
| Fixed and movable object sets | |
| Total and movable object counts | |
| Die / object width and height | |
| Area weight; diagonal weight matrix | |
| Coordinate matrix | |
| Graph Laplacian, adjacency and degree | |
| Spreading constraint matrix | |
| Mixed-size spreading-target constants | |
| Utilization ratio for rescaling | |
| Equalized Laplacian, Eq. (21) | |
| Rank-one centroid projector, Eq. (23) | |
| Projected Laplacian and linear term, Eq. (24) | |
| Spectrally shifted , Eq. (27) | |
| SSM subspace basis; reduced variable | |
| Reduced operator and linear term on | |
| Stiefel Lagrange multiplier (symmetric) | |
| Stiefel manifold | |
| Stiefel variable (post-equalization) |
Table I. Summary of key notations
Mixed-Size Placement Notation
A placed circuit is represented by a netlist hypergraph , where is the set of placement objects and is the set of nets connecting multiple pins. Mixed-size placement refers to instances in which contains both standard cells and much larger macros, often with footprint disparities of orders of magnitude [1, 4, 7].
Die and Coordinate Variables
Die and Coordinate Variables: We denote the placement region (die) by an axis-aligned rectangle of width and height . For objects, let denote the vectors of object center coordinates. We write
so that row of is , the center coordinates of object . Initialization is a global placement stage: the coordinates are continuous and overlaps are allowed, with the goal of producing a well-spread initial placement for downstream density-driven refinement and legalization.
Fixed and Movable Objects
Fixed and Movable Objects: We partition objects into a fixed set (preplaced blocks and I/O terminals) and a movable set (standard cells and macros), with
Accordingly, we split the coordinate vectors and other related vectors into fixed and movable blocks,
where are the vectors for the fixed objects and are the vectors for the movable objects, which are initialized by the proposed method.
Object Sizes and Area Weights
Object Sizes and Area Weights: Each object has width and height . We denote its area weight by , and assemble the area-weight vector as . The corresponding diagonal area matrix is
With the fixed/movable partition,
where
HPWL and Quadratic Wirelength Approximation
For a net with pins , HPWL is
and wHPWL aggregates nets with optional weights to reflect their degree:
We report wHPWL as the main quality metric.
For initialization, we use a quadratic Laplacian energy. We first reduce the netlist hypergraph to a sparse weighted graph with adjacency . The nonzero off-diagonal entries of correspond to the pairwise edges selected from each net; for multi-pin nets, these edges are formed by the angle-sorted cycle model in Section IV-C. The graph Laplacian is
where is the corresponding weighted degree matrix. The quadratic objective is
This sparse quadratic form supports fast iterative solvers and underpins the QCQP initialization in Section IV-A1. It captures connectivity through squared pairwise distances on the reduced graph.
Stiefel Manifold
For integers , the Stiefel manifold is the set (endowed with a manifold structure) of all matrices whose columns are orthonormal, that is,
We next recall the Riemannian tools [13, 14] on the Stiefel manifold (Eq. (3)) needed for our proposed optimization method. The central idea is to optimize directly on the manifold that represents the feasible set. Instead of enforcing the quadratic spreading equalities through penalty terms or generic Euclidean projections, we change variables so that the feasible set becomes the search space itself. In our setting, the quadratic spreading equalities of the QCQP, after metric equalization, reduce to the orthonormality constraint , and the search space becomes the Stiefel manifold (Eq. (3)). This enables the use of Riemannian optimization tools that maintain feasibility by construction.
Tangent Space and Projection
Tangent Space and Projection: The tangent space at is
For any , its orthogonal projection onto is given by
The symmetric-part operator , equivalently , returns for a square matrix .
Riemannian Gradient
Riemannian Gradient: For a smooth restricted to ,
A first-order critical point on the Stiefel manifold satisfies for some symmetric [13, 14].
Retraction
The polar (metric-projection) retraction maps tangent vectors back to the manifold:
where is the thin singular-value decomposition of [12], [13].
Rank-One Projector
For a nonzero ,
enforces for any in its range while preserving sparsity up to a rank-one correction.
Section IV-B describes our solver, which combines these Riemannian tools with SSM [12] tailored to the Stiefel-constrained QCQP, using the manifold’s smooth geometry for scalable Riemannian Newton-CG optimization.
Proposed Method
We address the challenges and gaps of § 2 by making the geometric structure of the QCQP constraints explicit. After metric equalization, the quadratic spreading equalities become an orthonormality condition on a Stiefel manifold, enabling the use of Riemannian optimization with feasibility-preserving steps and stable second-order solvers. Combined with careful mixed-size spreading-target construction and utilization-aware rescaling, this provides a robust initialization framework for mixed-size placement.
We propose a mixed-size placement initializer that is formulated as a constrained quadratic program with first- and second-order constraints. We make its quadratic equality constraints explicitly geometric via a Stiefel manifold transformation, and solve the resulting problem with a Riemannian sequential subspace method. The output is a continuous initial placement of center coordinates for movable objects that can be passed as a drop-in initialization to downstream placers along with the coordinates of the fixed objects.
Mixed-Size QCQP Formulation
QCQP Formulation
We start from the constrained QCQP formulation of [8] and reformulate the constraints to expose their geometric structure, minimizing the quadratic Laplacian energy (Eq. (2)) subject to global first- and second-order constraints under area weights.
a) First- and second-order constraints: A representative constrained spectral initializer is
The first-order constraints are linear and fix the area-weighted centroid, removing the global translation ambiguity inherent in Laplacian energies. The second-order constraints are quadratic and control the global spread and orientation of the embedding.
b) Compact matrix form: By stacking and , and defining
the constraints can be written compactly as
The constraint matrix specifies target spreading statistics of the placement distribution: choosing to match the geometry of the available placement region enforces physically meaningful spreading.
c) Reduction to movable variables: While fixed objects contribute to the objective through net connections, they are not decision variables. Partitioning conformally with and dropping constants independent of yields the reduced objective
The spreading constraints are similarly restricted to the movable blocks by replacing with and adjusting the right-hand sides to account for the fixed contribution [8].
Mixed-Size Spreading Targets
The QCQP formulation (Eq. (9)) requires target values . We set the coordinate origin at the die center, hence . We also set , which enforces axis-aligned spreading with zero cross-correlation between the and coordinates. This is appropriate for centered rectangular dies with axis-aligned objects. Extending the formulation to non-axis-aligned placement regions or rotated objects would require computing the full second-moment matrix, including the term when it is nonzero. This extension is left as future work. We then compute mixed-size targets and that account for varying rectangle sizes as follows.
Let the die be the axis-aligned rectangle . For a uniform distribution over , the second moments about the origin follow by direct integration. Along the -axis,
Symmetric reasoning along the -axis, together with by symmetry of the centered rectangle, gives
We relate these continuous target values to discrete placement variables as follows. For an axis-aligned rectangle object with center , width , height , area , and occupied region , the -second-moment contribution decomposes as
Similarly,
Because each rectangle is axis-aligned and referenced to its own center, the internal cross term vanishes: . Therefore, if the union of all rectangles is intended to match the die-level target values, the center terms should satisfy
Substituting Eq. (12) and the internal-contribution formulas gives the mixed-size spreading targets
The expressions in Eq. (13) give closed-form targets, require no numerical integration, and yield size-aware spreading targets because each object’s internal contribution is subtracted with its own width and height . The sphere-constrained formulation of [8] uses a simplified spreading-target construction based on averaged object dimensions. Here, each object’s width and height are subtracted individually. Our formulation computes size-aware spreading targets that subtract each object’s internal contribution using its own width and height, remaining stable even when macro sizes vary widely.
Centering and Constraint Matrix Construction
The most delicate part of QCQP initialization in mixed-size settings is the stable construction of a feasible, well-conditioned spreading constraint under fixed objects and nontrivial utilization. We present the centering and the resulting right-hand side in a form that matches the implementation.
a) Centering transformation: The centroid constraints in Eq. (9), restricted to the movable block, read as
Let and define the weighted shifts
We recenter the movable coordinates as
so that and hold identically. Substituting into Eq. (11) preserves the quadratic term and produces a shifted linear term. The centered objective is
with the explicit expression
where with and .
b) Constraint matrix: Let be the target spreading matrix formed from Eq. (13):
The spreading constraint on the full variables is
Restricting this constraint to the movable block and substituting the centered variables (Eq. (15)) yields
where the right-hand side is
The first subtraction removes the center contributions of the fixed objects from the global target. The rank-one term is the centering correction induced by shifting the movable coordinates so that . Here is the fixed-object-adjusted centroid target. It is distinct from the raw target defined earlier.
Utilization-Aware Rescaling
In mixed-size benchmarks, the free region available to movable objects can differ significantly from the total movable area due to fixed obstacles and whitespace. If one enforces from Eq. (19) directly, the initializer can over-spread the movable coordinates when utilization is below one, leading to extreme excursions that subsequent iterations cannot easily correct. We mitigate this by rescaling according to the ratio between movable area and free-region area.
We use the following area quantities:
We assume so that the movable objects fit within the free region. Over-utilized instances are outside the present scope. Define
If movable objects uniformly cover a sub-region of similar in shape to with area , the linear factor is . Under this similarity assumption, all linear dimensions scale by . Because a second moment integrates a degree-two coordinate term over area, each entry of scales by , giving the rescaling . Next, we numerically verify that is symmetric positive definite (SPD). If the check fails, the algorithm aborts. This check did not fail for any benchmark in our evaluation.
Stiefel Transformation and Solver
We apply Riemannian tools on the Stiefel manifold (Eq. (3)) from § 3-C to present the transformation and our solver.
Metric Equalization and Stiefel Transformation
We now convert the quadratic equalities into a Stiefel constraint by converting Eq. (16) with constraint Eq. (18) into an optimization on the Stiefel manifold. Geometrically, the constraint is a generalized orthogonality condition whose geometry is determined by the area weights and the spreading targets . The metric equalization below absorbs these weights into a change of variables, converting the constraint to the standard orthonormality condition on the Stiefel manifold . This step bridges QCQP-based initialization and Riemannian optimization. The transformation is well-defined whenever and are symmetric positive definite, which holds because all movable-object areas satisfy and because is verified to be SPD after rescaling in Section IV-A4.
a) Equalization of the quadratic constraint: Define the equalized operator and linear term
and introduce the Stiefel variable
Note that is distinct from the physical coordinate matrix of § 3-A. The relation is given by Eq. (22). Then the quadratic equality becomes , i.e., (Eq. (3)).
b) Centroid projector: The centered centroid constraint becomes with . We enforce this constraint implicitly by the rank-one projector (Eq. (8)):
We then form the projected equalized Laplacian and projected linear term
and obtain the transformed Stiefel problem
Because differs from the identity by rank one, Eq. (25) preserves the sparsity of up to low-rank corrections. All required operator applications can therefore be implemented using sparse matrix–vector products and rank-one updates. By construction, the initial iterate and every subspace-basis column lie in , so the trajectory remains in throughout the optimization.
c) Back-mapping to physical coordinates: Given a solution of Eq. (25), we recover the centered movable coordinates by inverting Eq. (22):
We then undo centering via Eq. (15):
and concatenate to obtain a full initial placement.
Stiefel-SSM Solver
The transformed Stiefel problem in Eq. (25) has for the large-scale regime, and the Stiefel iterate has columns corresponding to the - and -coordinates. We solve it by SSM on the Stiefel manifold, using sparse operator evaluations in the ambient space and small dense solves in an adaptively built low-dimensional subspace.
a) SSM iteration: Large-scale Stiefel problems with very large but small are well suited to SSMs, which alternate between (i) building a low-dimensional subspace that captures locally important directions, and (ii) solving a reduced Stiefel problem in that subspace. A typical iteration constructs an orthonormal basis , where , and solves , then sets . The subspace is enriched with the current iterate, the Euclidean gradient direction , curvature-informed directions (Newton-CG step), and low-frequency eigenvectors of the quadratic operator [12].
b) Quadratic structure and gradients: For symmetric matrices and , the Euclidean gradient of Eq. (25) is
The Riemannian gradient and first-order conditions then follow from Eqs. (6)–(7).
c) Ground subspace and spectral shift [12]: A key numerical issue in large graph-based Stiefel problems is the presence of very small nonzero eigenvalues in , which correspond to low-frequency graph modes. Since the projector removes the trivial mode, we compute a small “ground” subspace of the smallest nontrivial eigenvectors of with eigenvalues . We then define a spectrally shifted operator
which lifts the smallest eigenvalues within to match the -th eigenvalue , while leaving the operator unchanged outside that subspace. This construction improves conditioning without destroying sparsity, since differs from by a rank-at-most- update. The rank is exactly when . We follow the formulation of [12], which targets the indefinite region inside . This is more selective than the global multiplier-dependent identity shift used in the earlier sphere-constrained formulation [8], which adds a constant-magnitude shift to the entire operator.
At iterate , we form the consistent linear term from the matched-stationarity condition
i.e.,
so that the surrogate based on has the same gradient as the original objective at .
d) Subspace formation for reduced solve: Each outer iteration first computes a tangent-space direction by a safeguarded Newton-CG solve. The safeguarding combines two ingredients of [12]: (i) the spectral shift that lifts the ground eigenvalues to , and (ii) a multiplier safeguard that clips the generalized eigenvalues of the Stiefel multiplier.
At outer iteration , let
For a symmetric multiplier , define the safeguard map by the eigendecomposition
and
By construction,
The Newton-CG operator uses in the multiplier term. Together with the constraint on the Newton step, this safeguard keeps the projected Newton system positive semidefinite and suitable for conjugate-gradient solution.
We then form a small basis by orthonormalizing the columns of
following [12]: the current iterate, the Euclidean gradient direction , the ground eigenvectors, and the Newton direction, each contributing columns. We use the Euclidean rather than the Riemannian gradient here because adding the projection would only contribute a column already in , leaving the subspace unchanged. The resulting subspace dimension is . With this gives , so the reduced solve in Eq. (31) operates on matrices of size at most . We then solve the reduced Stiefel problem
using a small number of Riemannian Newton steps with polar retraction (Eq. (7)), and update the full iterate by
e) Algorithm summary: The full SSM iteration is summarized in Algorithm 1, and the inner Riemannian Newton solver used in the reduced subspace is detailed in Algorithm 2. The pre-computation of from the netlist hypergraph follows the construction in Sections IV-A1–IV-B: the sparse Laplacian is partitioned into and the spreading targets are computed via Eq. (13). The linear term (Eq. (17)) and constraint matrix in Eq. (19) are then formed, is rescaled by in Eq. (20), and metric equalization in Eq. (21) together with the rank-one projector in Eq. (23) yields and in Eq. (24).
Algorithm 1 implements the Stiefel-SSM iteration with periodic Laplacian updates. Lines 1–7 perform a one-time setup: lines 1–2 compute the ground subspace , lines 3–4 form the spectrally shifted operator , and lines 5–7 initialize the Stiefel iterate via singular value decomposition (SVD) of . The outer loop (lines 8–27) runs until the Riemannian-gradient norm falls below . Lines 10–11, executed every iterations, periodically rebuild the reduced graph using the multi-pin sparsification of Section IV-C and reassemble the operator pieces. Each iteration then updates the consistent linear term matched to the spectral shift (lines 13–14), computes the safeguard value and a Newton-CG tangent direction orthogonal to the ground subspace (lines 15–17), assembles the SSM subspace basis (lines 18–19), forms the reduced operator and linear term with initial point (line 21), and invokes Algorithm 2 with on the reduced subspace (line 22). The full Stiefel iterate is updated in line 23. Lines 28–30 map the converged Stiefel iterate back to physical coordinates.
Algorithm 2 implements the inner Riemannian Newton solve on the reduced subproblem (Eq. (31)). Lines 1–2 define the safeguard map and initialize the raw symmetric Lagrange multiplier ; the raw multiplier itself is not clipped. Each Newton iteration (lines 3–15) computes the stationarity residual using the raw multiplier (lines 4–5), solves the projected Newton system for the tangent step using in the multiplier term (lines 6–7), takes a line-searched polar-retraction step to obtain (lines 8–9), updates the raw symmetric multiplier at the new point (lines 10–11), and checks convergence (lines 12–14). The final reduced iterate is returned in line 16. This separation keeps the residual tied to the current symmetric multiplier, while the Newton-CG operator uses a safeguarded multiplier satisfying .
Multi-Pin Geometric Sparsification
This subsection describes how the sparse Laplacian is constructed and periodically updated from multi-pin nets. The Laplacian is obtained by reducing multi-pin nets to sparse graph edges. To keep sparse while reflecting current geometry, we use an angle-sorted cycle model for each multi-pin net and rebuild the graph periodically.
For a multi-pin net with pin locations , compute its centroid
compute angles , sort pins by , and connect the sorted pins into a cycle. Each two-pin net is a unit-weight edge, and each cycle edge has weight . This uses edges per net, compared to for the clique model and for the star model but without adding a star-center node [8]. The cycle model captures local geometric proximity through the cyclic neighborhood and naturally adapts to the current pin configuration when the graph is rebuilt. Figure 2 illustrates the construction.
Figure 2. Angle-sorted cycle sparsification for a multi-pin net. (a) Compute centroid and angles from centroid to each pin. (b) Sort pins by angle and form a cycle, producing edges (vs. for the clique model). The cycle is rebuilt every iterations to reflect updated geometry.
Algorithm 1 Stiefel-SSM solver
Require: Projected equalized operator $\widehat{L}$, projected linear term $B$, constraint matrix $C$; update period $T_{\mathrm{upd}}$; outer tolerance $\varepsilon$, inner tolerance $\varepsilon_{\mathrm{in}}$, maximum inner Newton iterations $j_{\max}$; back-mapping data $G_M,\Delta_x,\Delta_y$
Ensure: $\widetilde{X} \in \operatorname{St}(n_{\mathrm{free}},2)$, $X_M$
1: // Ground subspace
2: $(V_g,d_1,\ldots,d_r) \leftarrow$ ground-eigenpairs of $\widehat{L}$
3: // Spectral shift, {xref}`Eq. (28)`
4: $\widehat{L}_e \leftarrow \widehat{L}+V_g(d_rI-\operatorname{diag}(d_1,\ldots,d_r))V_g^{\mathsf{T}}$
5: // Initialize Stiefel iterate via SVD
6: $U_E\Sigma V_E^{\mathsf{T}} \leftarrow \operatorname{svd}(V_g^{\mathsf{T}}B)$
7: $\widetilde{X}_0 \leftarrow -V_gU_EV_E^{\mathsf{T}}$
8: **for** $k=0,1,2,\ldots$ **do**
9: **if** $k>0$ and $k\bmod T_{\mathrm{upd}}=0$ **then**
10: // Periodic Laplacian update ({xref}`Section IV-C`)
11: reassemble $(\widehat{L},B,V_g,d_r,\widehat{L}_e)$ from $\widetilde{X}_k$
12: **end if**
13: // Matched linear term, {xref}`Eq. (29)`
14: $B_k \leftarrow B-(\widehat{L}_e-\widehat{L})\widetilde{X}_kC$
15: // Tangent direction via Newton-CG
16: $\sigma_k \leftarrow \sigma_{\min}(V_g^{\mathsf{T}}B_kC^{-1})$
17: $Z_k \leftarrow \operatorname{Newton\text{-}CG}(\widehat{L}_e,B_k,C,\widetilde{X}_k,d_r,\sigma_k)$ with $V_g^{\mathsf{T}}Z_k=0$
18: // SSM subspace, {xref}`Eq. (30)`
19: $V_k \leftarrow \operatorname{qr}([\widetilde{X}_k,\widehat{L}\widetilde{X}_kC+B,V_g,Z_k])$
20: // Inner Newton + update full iterate
21: $\overline{L}_k \leftarrow V_k^{\mathsf{T}}\widehat{L}_eV_k,\ \overline{B}_k \leftarrow V_k^{\mathsf{T}}B_k,\ Y_{1,k}\leftarrow V_k^{\mathsf{T}}\widetilde{X}_k$
22: $\breve{X}\leftarrow\text{Algorithm 2}(\overline{L}_k,\overline{B}_k,C,Y_{1,k},d_r,\sigma_k,\varepsilon_{\mathrm{in}},j_{\max})$
23: $\widetilde{X}_{k+1}\leftarrow V_k\breve{X}$
24: **if** $\lVert\operatorname{grad} f(\widetilde{X}_{k+1})\rVert_F\leq\varepsilon$ **then**
25: **break**
26: **end if**
27: **end for**
28: // Back-mapping to physical coordinates
29: $\widetilde{X}_M\leftarrow G_M^{-1/2}\widetilde{X}_{k+1}C^{1/2}$
30: $X_M\leftarrow\widetilde{X}_M+\mathbf{1}[\Delta_x\ \Delta_y]$
Because the cycle depends on current coordinates, we couple it with an update loop. Every outer iterations, we rebuild the reduced graph, update , and reassemble , , , and the projected operator pieces . Between updates, we optimize Eq. (25) using the Stiefel-SSM iterations above. This loop differs from the iterative reweighting of [8], which adjusts edge weights as a function of current distance to drive the squared-wirelength approximation toward HPWL minimization. Our update instead rebuilds the cycle topology by angle order while keeping uniform edge weights, targeting the squared-wirelength approximation without explicit relaxation.
Experimental Results
This section evaluates the proposed Stiefel-constrained initialization as a drop-in initializer for three state-of-the-art mixed-size placers: RePlAce [3], DREAMPlace 4.1 [5], [15], and AutoDMP [6]. We report pre-route placement quality on 20 benchmarks (§ 5-B) and post-route physical-design quality on three benchmarks (§ 5-C).
Experimental Setup
Benchmarks
Benchmarks: Tables II and III summarize the benchmark suite and pre-route results. We adopt the same benchmark collection as [15]: the 16 MMS benchmarks [7] (as bundled with DREAMPlace [5]) and the four TILOS MacroPlacement benchmarks [16]. The TILOS repository provides netlists for Ariane133 (ASAP7) [17], Mempool tile (ASAP7), NVDLA (NanGate45) [18], and BlackParrot (NanGate45).
For the post-route study (§ 5-C) we use a separate benchmark set from the updated assessment by Cheng et al. [19]: Ariane133, BlackParrot, and Mempool group, all targeting the ASAP7 technology node. Mempool tile and Mempool group are distinct benchmark configurations: Mempool tile is used in the pre-route TILOS evaluation, whereas Mempool group is used only in the post-route study from [19].
I/O pins are treated as fixed objects in (§ 3-A). The benchmark suite spans a range of I/O configurations: some benchmarks place I/O pins on the die boundary, others outside the boundary, and others in the interior. Figure 3–Figure 5 show representative examples. The proposed formulation handles all such cases uniformly: coordinates of fixed objects enter the reduced objective through their net connections to movable objects, while fixed-object subtraction and centering correction are incorporated into the movable-variable QCQP constraints (Section IV-A). Thus, boundary, exterior, and interior I/O pins require no case-specific handling.
Figure 3. Macro placement for Ariane133 (98K cells, 133 SRAM macros). (a) Random initialization, (b) our initialization, (c) final placement under DREAMPlace without our initialization, (d) final placement under DREAMPlace with our initialization. Orange – macros, blue – standard cells, green – I/O pins.
Figure 5. Macro placement for newblue3 (483K cells, 51 macros). (a) Random initialization, (b) our initialization, (c) final placement under DREAMPlace without our initialization, (d) final placement under DREAMPlace with our initialization. Macros are colored by size class (large, medium, small), with legend dimensions in Bookshelf grid units. Blue – standard cells, green – I/O pins.
Pre-Route Flow
a) Placement engines: We integrate the proposed initialization into three analytical placers. (1) RePlAce [3]: an
electrostatics-based global placer that supports mixed-size instances natively. In our flow, RePlAce supports the four TILOS benchmarks. The MMS benchmark format used here is not accepted by the RePlAce mixed-size flow without conversion. (2) DREAMPlace 4.1 [5, 15]: In our mixed-size experiments, we use the Barzilai-Borwein (BB)-step-enabled mixed-size flow from DREAMPlace 4.1. This flow is paired with the default two-stage macro placement and legalization flow. (3) AutoDMP [6]: an automated hyperparameter tuning framework built on top of DREAMPlace. In every experiment the proposed initializer replaces only the default initial placement. All subsequent global-placement and detailed-placement stages remain unchanged.
b) Metric: We measure pre-route quality by wHPWL after detailed placement. For each placer, we report the wHPWL with and without the proposed initialization and the resulting percentage improvement. Positive values denote wHPWL reduction.
Hardware Environment
We run all experiments on a workstation equipped with a 13th-generation Intel Core i9-13900K processor (24 cores, 5.8 GHz max turbo), 128 GB system memory, and an NVIDIA GeForce RTX 4090 GPU. For the experiments reported in this paper, the initializer runs primarily on the CPU, with GPU acceleration limited to the computation of the ground eigenvectors .
Initialization Parameters
4) Initialization Parameters: The Stiefel-SSM initializer uses an outer loop of 20 iterations with Laplacian reconstruction period across all benchmarks. The Init-time column in Table II and Table III reports the wall-clock runtime of the initializer at these settings.
| Benchmark | Cells | Macros | Nets | RePlAce [3] w/o | w/ | Impr. | DREAMPlace [5, 15] w/o | w/ | Impr. | AutoDMP [6] w/o | w/ | Impr. | Init (min) |
| Ariane133 | 98K | 133 | 101K | 10.46 | 9.31 | 11.0 | 9.84 | 9.04 | 8.1 | 9.11 | 8.60 | 5.6 | 2.4 |
| Mempool tile | 132K | 20 | 135K | 11.19 | 10.52 | 6.0 | 10.96 | 10.63 | 3.0 | 11.05 | 10.67 | 3.4 | 3.2 |
| NVDLA | 153K | 128 | 208K | 102.31 | 65.25 | 36.2 | 36.24 | 34.09 | 6.0 | 38.29 | 34.50 | 9.9 | 3.8 |
| BlackParrot | 1.28M | 220 | 1.5M | 158.73 | 155.42 | 2.1 | 143.36 | 130.00 | 9.3 | 130.93 | 122.90 | 6.1 | 29.6 |
| Avg. | 13.8 | 6.6 | 6.3 | 9.8 |
Table II. Benchmark characteristics and pre-route wHPWL () on the four TILOS benchmarks [16], lower is better. “w/o” / “w/” denote results without / with the proposed initialization. Impr. (%) is the wHPWL reduction. Init (min) is the wall-clock runtime of the initializer. Best per benchmark is in bold.
| Benchmark | Cells | Macros | Nets | DREAMPlace [5, 15] w/o | w/ | Impr. | AutoDMP [6] w/o | w/ | Impr. | Init (min) |
| adaptec1 | 211K | 63 | 221K | 65.22 | 63.86 | 2.1 | 70.26 | 64.93 | 7.6 | 5.1 |
| adaptec2 | 254K | 127 | 266K | 75.12 | 71.18 | 5.2 | 75.26 | 71.12 | 5.5 | 6.5 |
| adaptec3 | 451K | 58 | 467K | 152.70 | 152.20 | 0.3 | N/C | 152.27 | N/C | 12.4 |
| adaptec4 | 495K | 69 | 516K | 141.56 | 140.08 | 1.0 | 143.40 | 141.43 | 1.4 | 13.3 |
| adaptec5 | 842K | 76 | 868K | 309.24 | 301.20 | 2.6 | 261.10 | 248.85 | 4.7 | 24.8 |
| bigblue1 | 278K | 32 | 284K | 85.43 | 84.41 | 1.2 | 90.51 | 84.85 | 6.3 | 6.9 |
| bigblue2 | 535K | 959 | 577K | 124.98 | 124.35 | 0.5 | 127.40 | 125.32 | 1.6 | 15.0 |
| bigblue3 | 1.09M | 2549 | 1.12M | 271.86 | 263.35 | 3.1 | 286.11 | 265.84 | 7.1 | 35.6 |
| bigblue4 | 2.17M | 199 | 2.23M | 644.87 | 641.56 | 0.5 | 669.22 | 656.18 | 1.9 | 87.8 |
| newblue1 | 330K | 64 | 339K | 59.78 | 56.62 | 5.3 | 58.92 | 57.72 | 2.0 | 9.4 |
| newblue2 | 437K | 3748 | 465K | 150.96 | 149.77 | 0.8 | 154.66 | 150.32 | 2.8 | 13.3 |
| newblue3 | 483K | 51 | 552K | 297.72 | 256.07 | 14.0 | 305.38 | 256.25 | 16.1 | 13.4 |
| newblue4 | 643K | 81 | 637K | 230.81 | 227.54 | 1.4 | 183.35 | 179.92 | 1.9 | 18.3 |
| newblue5 | 1.23M | 91 | 1.28M | 403.12 | 390.36 | 3.2 | 336.31 | 328.80 | 2.2 | 39.9 |
| newblue6 | 1.25M | 74 | 1.29M | 407.81 | 404.02 | 0.9 | 401.19 | 389.35 | 3.0 | 41.2 |
| newblue7 | 2.48M | 161 | 2.64M | 883.72 | 869.51 | 1.6 | 897.71 | 871.98 | 2.9 | 62.8 |
| Avg. | 2.7 | 4.5 | 25.3 |
Table III. Benchmark characteristics and pre-route wHPWL () on the 16 MMS benchmarks [7], which are bundled with DREAMPlace [5, 15], lower is better. “w/o” / “w/” denote results without / with the proposed initialization. Impr. (%) is the wHPWL reduction. Init (min) is the wall-clock runtime of the initializer. Best per benchmark in bold. Designs marked N/C did not converge and are excluded from averages. RePlAce is omitted because its mixed-size flow does not accept the MMS benchmark format.
Post-Route Flow
5) Post-Route Flow: We run the complete routing flow using Cadence Innovus 21.10, which performs clock-tree synthesis (CTS), routing, and routing optimization. We select DREAMPlace as the representative open-source placer for the post-route comparison. RePlAce is excluded because its mixed-size flow does not accept the MMS benchmark format and supports only the four TILOS benchmarks. AutoDMP adds an automated tuning loop and has one non-convergent default run (Table II and Table III). Therefore, we use DREAMPlace for controlled open-source comparisons because, apart from the initial coordinates, the downstream placement and routing flow is identical with and without the proposed initialization. This makes the post-route comparison directly attributable to the initialization. We report metrics after post-route optimization: standard-cell area, routed wirelength (rWL), power, worst negative slack (WNS), total negative slack (TNS), and DRC violations. We compare two configurations: (1) DREAMPlace without the proposed initialization, and (2) DREAMPlace with the proposed initialization.
Pre-Route Placement Quality
Tables II and III report the per-design pre-route wHPWL on the four TILOS and 16 MMS benchmarks, respectively, with and without the proposed initialization across the three placers. Table IV summarizes the averages by placer and benchmark scope. RePlAce is averaged only over the four TILOS benchmarks supported by its mixed-size flow. DREAMPlace is averaged over all 20 benchmarks. AutoDMP is averaged over the 19 benchmarks with converged baselines. The adaptec3 benchmark is reported separately because the default AutoDMP flow does not converge there.
| Placer | TILOS Avg. | MMS Avg. | All Avg. |
| RePlAce | 13.8 | N/A | N/A |
| DREAMPlace | 6.6 | 2.7 | 3.5 |
| AutoDMP | 6.3 | 4.5 | 4.8 |
Table IV. Pre-route wHPWL improvement (%) averaged by placer, summarizing Table II and Table III. RePlAce runs only on the four TILOS benchmarks. AutoDMP averages exclude adaptec3 (default AutoDMP flow does not converge): the MMS avg is over 15 designs and the all avg over 19, given in bold.
The initialization consistently reduces wHPWL on every converged run. DREAMPlace achieves a 3.5% average improvement across all 20 benchmarks, with a peak gain of 14.0% on newblue3. AutoDMP achieves an average improvement of 4.8% across the 19 converged baselines, with a peak gain of 16.1% on newblue3, and additionally converges on adaptec3 when initialized by the proposed method. RePlAce achieves an average improvement of 13.8% on the four TILOS benchmarks, driven by a gain of 36.2% on NVDLA where the default initialization produces highly suboptimal macro positions. The improvement is stable across all three placer backends, confirming the generality of the proposed initialization.
On BlackParrot, the largest TILOS benchmark (1.28M cells, 220 macros), the proposed initialization improves wHPWL across all three placers, including a 2.1% gain under RePlAce and 9.3% under DREAMPlace, confirming that the method scales to million-cell instances.
A noteworthy case is adaptec3 under AutoDMP: the default flow fails to converge (N/C in Table III), while AutoDMP with
the proposed initialization converges successfully, producing a wHPWL comparable to that of DREAMPlace. The adaptec3 result suggests that the proposed initialization can improve robustness for some hyperparameter-tuned flows on challenging designs by providing a better-conditioned starting point.
Beyond the aggregate wHPWL numbers, three representative designs reveal how the proposed initialization improves macro arrangement at the design level.
Representative Cases
1) Representative Cases:
**a) Ariane133: I/O–macro separation: ** Ariane133 has 133 SRAM macros and concentrates I/O pins on the left edge. The default DREAMPlace initialization (Figure 3(c)) pulls some macros toward the left edge, competing with standard cells for the I/O-adjacent area. Our initialization (Figure 3(d)) pushes macros toward the interior, freeing the I/O-adjacent periphery for the cells that require short wires to the pins. Wirelength decreases by 8.1%.
**b) BlackParrot: Tile locality: ** BlackParrot (1.28M cells, 220 macros) is a 2×2 tiled multicore processor. Each tile has 55 macros with dense intra-tile and minimal cross-tile connectivity. The default initialization (Figure 4(c)) intermixes macros from different tiles. For example, a Tile (0,0) DCache SRAM may end up adjacent to a Tile (1,1) L2 SRAM despite no connectivity between them. Our initialization (Figure 4(d)) clusters macros from the same tile spatially. This pattern is consistent with the design intuition of keeping each tile’s macros close to its own logic and reduces inter-tile wirelength.
Figure 4. Macro placement for BlackParrot (1.28M cells, 220 macros). (a) Random initialization, (b) our initialization, (c) final placement under DREAMPlace without our initialization, (d) final placement under DREAMPlace with our initialization. Macros are colored by tile membership (Tile (0,0)/(0,1)/(1,0)/(1,1)) in the 2×2 multicore layout. Blue – standard cells, green – I/O pins.
**c) newblue3: Balanced macro distribution: ** Newblue3 is dominated by 18 large horizontal macros that confine standard cells to a narrow vertical channel. The remaining area holds 32 medium and one small macro. The default initialization (Figure 5(c)) concentrates the medium macros in the lower half, producing an asymmetric density distribution. Our initialization (Figure 5(d)) distributes them evenly across both halves, balancing channel density and yielding 14.0% wHPWL improvement under DREAMPlace and 16.1% under AutoDMP, the largest gains on any MMS benchmark.
Solver Convergence
Solver Convergence: Figure 6 shows the convergence of Stiefel-SSM on representative designs during the pre-route initialization stage, run for 40 outer iterations as a diagnostic. Tables II and III use the standard 20-iteration setting. The Stiefel objective decreases within each fixed-Laplacian interval, with controlled jumps at the periodic Laplacian reconstruction points (every outer iterations), where the operator changes and the objective can change abruptly. The Riemannian gradient norm trends downward between reconstructions, consistent with the SSM convergence guarantee [12] that the gradient asymptotically vanishes (), indicating that the placement coordinates returned to downstream placers come from a low-gradient initializer.
Figure 6. Convergence of Stiefel-SSM on representative designs. (Left) Normalized objective of the Stiefel manifold, . (Right) Norm of the Riemannian gradient. Vertical dashed lines mark Laplacian reconstruction points.
Post-Route Physical Design Quality
Following the post-route setup of § 5-A, Table V reports post-route optimization power, performance, and area (PPA) metrics from Cadence Innovus, including remaining DRC violations.
| Benchmark | Configuration | Area () | rWL () | Pwr (mW) | WNS (ns) | TNS (ns) | DRC |
| Ariane133 | DREAMPlace w/o init | 16392 | 982089 | 505.1 | −0.175 | −276.2 | 157 |
| DREAMPlace w/ init | 16374 | 959926 | 504.0 | −0.263 | −472.7 | 93 | |
| BlackParrot | DREAMPlace w/o init | 122960 | 7013052 | 1542.7 | −0.091 | −277.0 | 4 |
| DREAMPlace w/ init | 122063 | 6926938 | 1541.3 | −0.103 | −366.1 | 4 | |
| Mempool group | DREAMPlace w/o init | 336631 | 24499970 | 1363.0 | −0.127 | −678.6 | 32576 |
| DREAMPlace w/ init | 335528 | 24233201 | 1355.7 | −0.150 | −440.2 | 32449 |
Table V. POST-ROUTE POWER, PERFORMANCE, AND AREA (PPA) FROM CADENCE INNOVUS ON ASAP7. AREA DENOTES STANDARD-CELL AREA; rWL = ROUTED WIRELENGTH; PWR = TOTAL POWER; WNS / TNS = WORST / TOTAL NEGATIVE SLACK; DRC = DRC VIOLATIONS. “W/O” / “W/” DENOTE RESULTS WITHOUT / WITH THE PROPOSED INITIALIZATION. BEST RESULT PER (BENCHMARK, METRIC) IN BOLD.
Detailed PPA Analysis
a) Ariane133: DREAMPlace w/ init reduces routed wirelength by 2.3% relative to w/o init (959,926 vs. 982,089 µm), confirming that the pre-route wHPWL gain carries through routing. After DRC fixing, w/ init leaves 93 remaining violations compared to 157 for w/o init, indicating that the proposed initialization produces a placement with fewer DRC violations.
b) BlackParrot: On the largest benchmark (1.28M standard cells), DREAMPlace w/ init reduces routed wirelength by 1.2% compared to w/o init (6,926,938 vs. 7,013,052 µm), demonstrating that the initialization benefit persists through detailed placement and routing even at million-instance scale.
Timing Discussion
Mempool group is the most challenging routing scenario. DREAMPlace w/ init reduces routed wirelength by 1.1% compared to w/o init (24,233,201 vs. 24,499,970 ), with comparable power savings (1355.7 vs. 1363.0 mW). Timing improves in TNS (−440.2 vs. −678.6 ns) while WNS is comparable (−0.150 vs. −0.127 ns). DRC violations also decrease slightly, by approximately 0.4% (32,449 vs. 32,576).
While the proposed initialization consistently improves routed wirelength, timing metrics do not always improve in parallel. On Ariane133, DREAMPlace w/ init achieves lower wirelength but worse WNS (−0.263 ns vs. −0.175 ns for w/o init). This timing trade-off is expected: the initializer optimizes a wirelength approximation and does not model timing paths directly. Wirelength reduction benefits congestion and routability but does not guarantee timing improvement, which depends on path-specific delays affected by cell placement relative to clock domains.
Summary of Findings
The experimental results support three conclusions. (1) The proposed Stiefel-constrained initialization consistently reduces pre-route wHPWL across three placement flows: 3.5% with DREAMPlace across all 20 benchmarks, 4.8% with AutoDMP across its 19 converged baselines, and up to 36.2% with RePlAce on individual designs. This supports its generality as an initializer across downstream placement tools. All converged runs show positive wHPWL improvement. (2) Pre-route improvements carry through the full place-and-route flow: DREAMPlace w/ init reduces post-route routed wirelength by 1.1–2.3% relative to w/o init on all three post-route benchmarks, and also reduces standard-cell area and power on all three. DRC violations decrease on Ariane133 and Mempool group and remain unchanged on BlackParrot. Timing is mixed because the initializer optimizes a wirelength approximation and does not model timing paths. (3) The initialization can stabilize hyperparameter-tuned analytical flows on challenging designs. On adaptec3, AutoDMP fails to converge with its default initialization (N/C in Table III), but converges successfully when initialized by the proposed method, producing a wHPWL comparable to DREAMPlace.
Conclusion
This paper presented a placement initialization method for mixed-size VLSI designs that formulates initialization as a QCQP with explicit first- and second-order constraints. The key insight is that the quadratic equality constraints defining area-weighted spreading already encode a Stiefel geometry. Making this structure explicit via metric equalization transforms the problem to a Stiefel manifold and enables feasibility-preserving Riemannian optimization with Newton-CG second-order steps. Combined with angle-sorted cycle sparsification and periodic Laplacian updates, the method produces high-quality initial placements that serve as a drop-in initializer for existing analytical placers.
Experiments across three state-of-the-art placers confirm improvements on every converged benchmark. On the TI-LOS benchmarks, the proposed initialization reduces wHPWL by 13.8% on average under RePlAce, with a 36.2% peak improvement on NVDLA. DREAMPlace achieves a 3.5% average improvement across all 20 benchmarks (14.0% peak on newblue3). AutoDMP achieves a 4.8% average improvement across the 19 benchmarks with converged baselines (16.1% peak on newblue3) and additionally stabilizes the non-convergent adaptec3 baseline. All converged runs show positive improvement. Post-route evaluation confirms that pre-route gains carry through: routed wirelength decreases by 1.1–2.3% on all three post-route benchmarks, and standard-cell area and power decrease on all three. DRC violations decrease on Ariane133 (40% reduction) and Mempool group, and remain unchanged on BlackParrot. Timing is mixed because the initializer optimizes a wirelength approximation and does not model timing paths.
Future directions focus on improving scalability and scope. For the implementation used in the reported experiments, initialization runtime ranges from 2.4 to 87.8 minutes on the 20-benchmark pre-route suite (Table II and Table III) and reaches about two hours on the Mempool group, motivating further optimization, including broader GPU acceleration beyond the current partial SSM support. Future work will incorporate congestion and timing terms into the initialization objective to target end-to-end PPA. Additional directions include adaptive subspace selection for faster convergence on large designs, post-route co-optimization with congestion- and timing-aware objectives, and extensions to three-dimensional placement.
Acknowledgments
This work was supported in part by the National Science Foundation under Grant CCF-2110419.
References
Biographies
Pengwen Chen
Pengwen Chen is currently a Professor in the Mathematics Department of National Tsing Hua University, Hsinchu, Taiwan. His research interests include numerical analysis, optimization, and mathematical imaging science. He received his Ph.D. in Mathematics from the University of Florida.
Chung-Kuan Cheng
Chung-Kuan Cheng is a Distinguished Professor in the CSE Department and an Adjunct Professor in the ECE Department of the University of California, San Diego. His research interests include computer-aided design for machine learning and design automation in microelectronic circuits. He received his Ph.D. degree in Electrical Engineering and Computer Sciences from the University of California, Berkeley.
Shao-Yun Fang
Shao-Yun Fang received a B.S. degree in electrical engineering from the National Taiwan University (NTU), Taipei, Taiwan, in 2008 and a Ph.D. degree from the Graduate Institute of Electronics Engineering, NTU, in 2013. She is currently a Professor of the Department of Electrical Engineering, National Taiwan University of Science and Technology, Taipei, Taiwan. Her research interests focus on physical design and design for manufacturability for integrated circuits. She is serving as an Associate Editor of IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems and ACM Transactions on Design Automation of Electronic Systems.
Chester Holtz
Chester Holtz is a Postdoctoral Scholar at the Halıcıoğlu Data Science Institute. He earned his Ph.D. in Computer Science from the University of California, San Diego where he was advised by Professor Chung-Kuan Cheng. His research interests include machine learning and optimization, in particular on graph-structured data.
Sheng-Tan Huang
Sheng-Tan Huang received a B.S. degree in Electrical Engineering from National Taiwan University of Science and Technology (NTUST), Taipei, Taiwan, in 2022. He is currently pursuing a Ph.D. degree in Electrical Engineering at National Taiwan University of Science and Technology, Taipei, Taiwan. His current research interests focus on quantum layout synthesis and large-scale placement.
Susmita Sur-Kolay
Susmita Sur-Kolay is a Fulbright Academic Excellence Fellow in the CSE Department of the University of California, San Diego and has been a Professor at Indian Statistical Institute. Her research interests include design automation for microelectronic and quantum circuits, hardware security and in-memory neuromorphic computation. She received her Ph.D. degree in Computer Science and Engineering from Jadavpur University, and from 1980 to 1985, she was at Massachusetts Institute of Technology. She is a Fellow of Indian National Science Academy and Indian National Academy of Engineering, a recipient of the President of India Gold Medal and Distinguished Alumnus Award of IIT Kharagpur, and Women in Technology Leadership Award of the VLSI Society of India.
Yucheng Wang
Yucheng Wang is a Ph.D. student in the Department of Computer Science and Engineering, University of California, San Diego. He received his bachelor’s degree in Computer Science from Purdue University, West Lafayette, in 2021. His research interests include standard-cell layout automation, design technology co-optimization strategies, and graph visualization.
Ying Yuan
Ying Yuan is a Ph.D. student in the Department of Computer Science and Engineering, University of California, San Diego. She received her bachelor’s degree in Computer Science from Purdue University, West Lafayette, in 2021, and her master’s degree in Computer Science and Engineering from the University of Michigan, Ann Arbor, in 2023. Her research interests include 2D and 3D placement and routing. Her work integrates machine learning and optimization.
References
- [1]I. L. Markov, J. Hu, and M.-C. Kim, “Progress and challenges in VLSI placement research,” Proceedings of the IEEE, vol. 103, no. 11, pp. 1985–2003, 2015.
- [2]J. Lu et al., “ePlace: Electrostatics-based placement using fast fourier transform and Nesterov’s method,” ACM Transactions on Design Automation of Electronic Systems, vol. 20, no. 2, pp. 17:1–17:34, 2015. [Online]. Available: https://doi.org/10.1145/2699873
- [3]C. Cheng, A. B. Kahng, I. Kang, and L. Wang, “RePlAce: Advancing solution quality and routability validation in global placement,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 38, no. 9, pp. 1717–1730, 2019. [Online]. Available: https://doi.org/10.1109/TCAD.2018.2859220
- [4]J. Lu et al., “ePlace-MS: Electrostatics-based placement for mixed-size circuits,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 34, no. 5, pp. 685–698, 2015.DOI
- [5]Y. Lin, S. Dhar, W. Li, H. Ren, B. Khailany, and D. Z. Pan, “DREAMPlace: Deep learning toolkit-enabled GPU acceleration for modern VLSI placement,” in Proceedings of the 56th Annual Design Automation Conference (DAC), ACM, 2019. [Online]. Available: https://doi.org/10.1145/3316781.3317803
- [6]A. Agnesina et al., “AutoDREAMPlace: Automated DREAMPlace-based macro placement,” in Proceedings of the 2023 International Symposium on Physical Design (ISPD). ACM, 2023, pp. 149–157. [Online]. Available: https://doi.org/10.1145/3569052.3578923
- [7]J. Z. Yan, N. Viswanathan, and C. Chu, “Handling complexities in modern large-scale mixed-size placement,” in 2009 46th ACM/IEEE Design Automation Conference, 2009, pp. 436–441.
- [8]P. Chen, C. Cheng, A. Chern, C. Holtz, A. Li, and Y. Wang, “Placement initialization via sequential subspace optimization with sphere constraints,” in Proceedings of the 2023 International Symposium on Physical Design (ISPD). ACM, 2023. [Online]. Available: https://doi.org/10.1145/3569052.3571877
- [9]Y. Liu, H. Zhou, J. Wang, F. Yang, X. Zeng, and L. Shang, “The power of graph signal processing for chip placement acceleration,” in 2024 ACM/IEEE International Conference On Computer Aided Design (ICCAD), 2024, pp. 1–8.arxiv.org/abs/2502.17632
- [10]A. Mirhoseini et al., “A graph placement methodology for fast chip design,” Nature, vol. 594, no. 7862, pp. 207–212, 2021. [Online]. Available: https://doi.org/10.1038/s41586-021-03544-w
- [11]Y. Liu et al., “GraphPlanner: Floorplanning with graph neural network,” ACM Transactions on Design Automation of Electronic Systems, vol. 28, no. 2, pp. 21:1–21:24, 2023. [Online]. Available: https://doi.org/10.1145/3555804
- [12]P. Chen, C. Cheng, and C. Holtz, “Sequential subspace methods on Stiefel manifold optimization,” arXiv preprint arXiv:2404.13301, 2024.arxiv.org/abs/2404.13301
- [13]P. Absil, R. E. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds. Princeton University Press, 2008.DOI
- [14]A. Edelman, T. A. Arias, and S. T. Smith, “The geometry of algorithms with orthogonality constraints,” SIAM Journal on Matrix Analysis and Applications, vol. 20, no. 2, pp. 303–353, 1998. [Online]. Available: https://doi.org/10.1137/S0895479895290954
- [15]Y. Chen, Z. Wen, Y. Liang, and Y. Lin, “Stronger mixed-size placement backbone considering second-order information,” in 2023 IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2023, pp. 1–9.DOI
- [16]TILOS AI Institute, “MacroPlacement,” https://github.com/TILOS-AI-Institute/MacroPlacement, 2023, accessed: 2026-04-30.
- [17]T. L. Clark et al., “ASAP7: A 7-nm finfet predictive process design kit,” Microelectronics Journal, vol. 53, pp. 105–115, 2016.DOI
- [18]NanGang Inc., “NanGate FreePDK45 Open Cell Library,” https://si2.org/open-cell-library/, 2008, accessed: 2026-05-04.
- [19]C.-K. Cheng, A. B. Kahng, S. Kundu, Y. Wang, and Z. Wang, “An updated assessment of reinforcement learning for macro placement,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, pp. 1–1, 2025.arxiv.org/abs/2302.11014





