Quality-Preserving Legalization for Analytical Floorplanning

Yunqi He, You Li, Ruofan Huang, Hai Zhou

Northwestern University · NuLogiCS Research Group

Abstract

Floorplanning is a crucial step in VLSI physical design. Analytical floorplanning, which determines macro positions through electrostatic-based mixed-size placement, has become the most prevalent paradigm. However, the resulting floorplan contains inter-macro overlaps that must be resolved by a legalization step. Existing methods minimize displacement from the analytical floorplan without effective topological guidance, leading to inconsistent downstream quality. In this paper, we propose a new legalization workflow that preserves the high quality of analytical floorplanning. We leverage twin binary trees to capture the relation between adjacent blocks, and build a differentiable model to optimize their coordinates. Experiments on TILOS MacroPlacement benchmarks show that our method enables analytical floorplanning to match or surpass commercial and open-source macro placement tools in post-route timing and wirelength.

Why topology matters

Electrostatics-based analytical placers such as ePlace, RePlAce, and DREAMPlace produce high-quality floorplans, but the macros overlap and a legalizer has to resolve that. An analytical floorplan carries two kinds of information: the macro positions, and the topology, i.e. which macro sits left of, right of, above, or below which. Both determine post-route PPA. Existing legalizers minimize displacement only and leave the topology to chance.

Method

The legalizer never reorders macros. It fixes the topology once with twin binary trees, then runs gradient descent on the only free variables left, the sizes of the filler blocks between macros.

• Twin binary trees. Mosaic floorplans correspond one-to-one with pairs of binary trees (Yao et al.). Unlike sequence pairs or B*-trees the representation is non-redundant and captures the complete adjacency information. The trees are extracted once with MFTB and held fixed, so the topology is invariant by construction.
• Preparation and mosaic construction. Macro padding (an AutoDMP-style halo in the LEF) makes the analytical floorplan spacing-aware; uniform shrinking removes all overlaps with the largest common scale factor; an incremental mosaic builder inserts filler blocks so that every internal boundary ends in a T-junction, never a cross.
• TBMF as a differentiable forward model. Reconstructing coordinates from the trees is a longest-path computation on horizontal and vertical constraint graphs, i.e. only additions and max operations. Coordinates are therefore piecewise linear in the block sizes, and each max routes the gradient to its current longest predecessor, like a ReLU. Macros keep their real sizes; filler widths and heights are the only variables; the loss is the squared displacement of macro centers from the analytical floorplan, minimized with Adam.
• Guarantees. For any non-negative sizes the reconstructed floorplan has no overlaps (Theorem 1) and the relative positions of all blocks are unchanged (Theorem 2). Every iterate is a legal, topology-preserving floorplan, with no die expansion.

Results

• Against other legalizers (OpenROAD, all 8 macro-containing Nangate45 designs, identical RePlAce input): the lowest mean displacement on 7 of 8 designs with consistent post-route timing. Greedy legalization flips orders and breaks the downstream flow on black_parrot; LP keeps orders but needs a larger die on 6 of 8 designs, up to +44%.
• End to end in OpenROAD: RePlAce + our legalization reaches best or tied-best WNS and TNS on 7 of 8 designs and the shortest routed wirelength on 6 of 8 against Hier-RTLMP and TritonMacroPlace, 63–74× faster than TritonMacroPlace on ariane133 and ariane136.
• Commercial flow (Cadence Genus + Innovus, TILOS MacroPlacement ariane133 and bp_quad on Nangate45 and ASAP7): PPA comparable to Cadence CMP and shorter wirelength than Circuit Training in all four configurations, in 1–12 minutes on one CPU.
• Ablation: macro padding plus the incremental mosaic builder cut mean displacement on ariane133 from 78.6 µm to 12.7 µm and the maximum from 311.9 µm to 80.9 µm. One Adam setting (learning rate 1.0, gradient clipping at 100, early stop at 0.1%) converges in a few hundred iterations on all ten benchmarks.

Talk at ICCAD 2026

Citation

@inproceedings{he2026qplegalization,
  title     = {Quality-Preserving Legalization for Analytical Floorplanning},
  author    = {He, Yunqi and Li, You and Huang, Ruofan and Zhou, Hai},
  booktitle = {Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD)},
  year      = {2026},
  doi       = {10.1145/3831252.3833939}
}

Contact: yunqi.he@u.northwestern.edu