A Robust Modulus-Based Matrix Splitting Iteration Method for Mixed-Cell-Height Circuit Legalization
Authors:
Open Access
- 10 December 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Design Automation of Electronic Systems
- Vol. 26 (2) , 1-28
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.Keywords
Funding Information
- AnaGlobe, IBM, MediaTek, TSMC, and MOST of Taiwan (MOST 103-2221-E-002-259-MY3, MOST 104-2221-E-002-132-MY3, MOST 105-2221-E-002-190-MY3, MOST 106-2911-I-002-511, and MOST 106-2221-E-002-203-MY3)
- NTU (NTU-ERP-104R8951, and NTU-ERP-105R8951)
- National Science Foundation of China (61672005 and 61977017)
- Fujian Science Fund for Distinguished Young Scholars (2019J06010)
This publication has 18 references indexed in Scilit:
- Mixed-Cell-Height Standard Cell Placement Legalization2017
- An effective legalization algorithm for mixed-cell-height standard cells2017
- A novel unified dummy fill insertion framework with SQP-based optimization method2016
- Detailed Placement Algorithm for VLSI Design With Double-Row Height Standard CellsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2015
- A heuristic algorithm for the strip packing problemJournal of Heuristics, 2012
- Modulus-based matrix splitting iteration methods for linear complementarity problemsNumerical Linear Algebra with Applications, 2010
- On generalized successive overrelaxation methods for augmented linear systemsNumerische Mathematik, 2005
- Standard Cell Layout With Regular Contact PlacementIEEE Transactions on Semiconductor Manufacturing, 2004
- Object-oriented software for quadratic programmingACM Transactions on Mathematical Software, 2003
- A quadratic programming approach to simultaneous buffer insertion/sizing and wire sizingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999