https://scholars.lib.ntu.edu.tw/handle/123456789/632274
標題: | A Robust Modulus-Based Matrix Splitting Iteration Method for Mixed-Cell-Height Circuit Legalization | 作者: | Chen J Zhu Z Zhu W YAO-WEN CHANG |
關鍵字: | legalization; linear complementarity problem; modulus-based matrix splitting iteration method; multi-row height cell; Physical design; placement; quadratic programming | 公開日期: | 2021 | 卷: | 26 | 期: | 2 | 來源出版物: | ACM Transactions on Design Automation of Electronic Systems | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85124146101&doi=10.1145%2f3423326&partnerID=40&md5=86b440ef4ff4d66586b9cffbcd3b592a https://scholars.lib.ntu.edu.tw/handle/123456789/632274 |
ISSN: | 10844309 | DOI: | 10.1145/3423326 | SDG/關鍵字: | 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 |
顯示於: | 電信工程學研究所 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。