A hierarchical bin-based legalizer for standard-cell designs with minimal disturbance

In this work, a hierarchical bin-based legalization approach, HiBinLegalizer, is developed to legalize standard cells with minimal movement. First, a chip is divided into several bins with equal size. Then, starting with the most crowed unlegalized bin, a merging procedure for bins is used to integrate bins into a cross-shape region or a square-shape region until the cell density in that region is less than a specific cell-density-threshold. After that, an efficient legalization method which simultaneously preserves the cell orders in each row and minimizes the weighted sum of movement distances is developed to legalize cells in that region to limit the movable scope. To improve the legalization quality, HiBinLegalizer refreshes the positions of legalized cells during legalization. The legalizing procedure is repeated until all cells are non-overlapped. Compared with the state-of-the-art method, Abacus, HiBinLegalizer can reduce the total movement of cells to be 48% in average and save the largest movement of cells to be 140% in average. Moreover, HiBinLegalizer can reduce the HPWL by 47% and obtain average 1.11× runtime speed up.