LEGALM 2.0: A Versatile Augmented Lagrangian Method-Based Methodology for Mixed-Cell-Height Legalization

Legalization is a crucial step in VLSI physical design, ensuring design rule compliance while minimizing disruptions to global placement. With the rise of multi-row-height cells in advanced nodes, mixed-cell-height legalization poses significant challenges due to complex cell shapes and design constraints. In this work, we present LEGALM 2.0, a versatile legalization methodology that efficiently handles routability and hybrid region constraints. Our approach introduces a linearized augmented Lagrangian formulation, a scanline-based initial legalization algorithm, and a connectivity-based local optimum escape strategy to enhance convergence. Additionally, we propose a block gradient descent method and a GPU-optimized triplefold partitioning strategy for improved parallelism. Experimental results show that LEGALM 2.0 outperforms state-of-the-art legalizers, achieving 6-36% better quality scores on ICCAD2017 benchmarks and 1.61-4.30W speedup on large-scale designs. For hybrid region constraints, it reduces displacement by 25% and wirelength perturbation by 21%, demonstrating its effectiveness in modern physical design.