A Robust Modulus-Based Matrix Splitting Iteration Method for Mixed-Cell-Height Circuit Legalization
Journal
ACM Transactions on Design Automation of Electronic Systems
Journal Volume
26
Journal Issue
2
Date Issued
2021
Author(s)
Abstract
Modern circuits often contain standard cells of different row heights to meet various design requirements. Taller cells give larger drive strengths and higher speed at the cost of larger areas and power. Multi-row height standard cells incur challenging issues for layout designs, especially the mixed-cell-height legalization problem with heterogeneous cell structures. Honoring the good cell positions from global placement, we present in this article a robust modulus-based matrix splitting iteration method (RMMSIM) to solve the mixed-cell-height legalization problem. Fixing the cell ordering from global placement and relaxing the right-boundary constraints, our proposed method first converts the problem into an equivalent linear complementarity problem (LCP), and then properly splits the matrices in the LCP so that the RMMSIM can solve the LCP optimally. The RMMSIM effectively explores the sparse characteristic of a circuit, and takes only linear time per iteration; as a result, it can solve the QP very efficiently. Finally, an allocation scheme for illegal cells is used to align such cells to placement sites on rows and fix the placement of out-of-right-boundary cells, if any. Experimental results show the effectiveness and efficiency of our proposed algorithm. In addition, the RMMSIM convergence and optimality are theoretically proved and empirically validated. In particular, this article provides a new RMMSIM formulation for various optimization problems that require solving large-scale convex quadratic programming problems efficiently. © 2020 Association for Computing Machinery.
Subjects
legalization; linear complementarity problem; modulus-based matrix splitting iteration method; multi-row height cell; Physical design; placement; quadratic programming
Other Subjects
Authentication; Cytology; Iterative methods; Matrix algebra; Quadratic programming; Timing circuits; Cell height; Global placements; Legalization; Linear complementarity problems; Mixed cells; Modulus-based matrix splitting iteration methods; Multi-row height cell; Physical design; Placement; Standard-cell; Cells
Type
journal article