Analytical Mixed-Cell-Height Legalization Considering Average and Maximum Movement Minimization

Modern circuit designs often contain standard cells of different row heights to meet various design requirements. Due to the higher interference among heterogeneous cell structures, the legalization problem for mixed-cell-height standard cells becomes more challenging. In this paper, we present an analytical legalization algorithm for mixed-cell-height standard cells to simultaneously minimize the average and the maximum cell movements. We formulate it as a mixed integer quadratic programming problem (MIQP), which allows cell spreading concurrently in both the horizontal and vertical directions. By relaxing its discrete constraints to linear ones, we convert the MIQP into a quadratic programming problem (QP). To solve the QP efficiently, we further reformulate it as a linear complementarity problem (LCP), and solve the LCP by a modulus-based matrix splitting iteration method (MMSIM). To guarantee the convergence of the MMSIM and the equivalence between the QP and the LCP, we use a series of operations to ensure that its induced objective matrix is symmetric positive definite and its constraint matrix is of full row rank. Experimental results demonstrate the effectiveness of our algorithm in reducing both the average and the maximum cell movements for mixed-cell-height legalization.