A Modified Two-Step Modulus-Based Matrix Splitting Iteration Method for Legalization With Macros

Mixed cell heights with macros pose significant challenges to placement in large-scale integrated circuits. In particular, the heterogeneity of cells and the segmentation of space remarkably complicate the legalization of mixed-cell-height cells and macros. To preserve the global placement results and minimize the displacement as much as possible, we propose a new approach that involves four key steps. Firstly, each macro is appropriately split so that its height is an integer multiple of the row height. Then, cells inside the locations of macros are pre-legalized by moving them outside. To eliminate the overlaps, we express the legalization problem as a quadratic programing (QP) problem, which is then converted into an implicit complementary problem (ICP). Next, the modified twostep modulus-based matrix splitting iteration method is employed to solve the ICP in a fast manner. Finally, we restore the macros to the original appearance. Experimental results demonstrate that, within the stipulated time constraints, the proposed design can minimize both the total and maximum displacement following the elimination of all overlaps effectively and swiftly. Once all the cells have been legalized according to all stipulations, the proposed design is capable of achieving a placement with smaller HPWL in less time.