{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T20:33:53Z","timestamp":1771706033448,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,12,10]],"date-time":"2020-12-10T00:00:00Z","timestamp":1607558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"AnaGlobe, IBM, MediaTek, TSMC, and MOST of Taiwan","award":["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"],"award-info":[{"award-number":["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"]}]},{"name":"NTU","award":["NTU-ERP-104R8951, and NTU-ERP-105R8951"],"award-info":[{"award-number":["NTU-ERP-104R8951, and NTU-ERP-105R8951"]}]},{"DOI":"10.13039\/501100001809","name":"National Science Foundation of China","doi-asserted-by":"crossref","award":["61672005 and 61977017"],"award-info":[{"award-number":["61672005 and 61977017"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fujian Science Fund for Distinguished Young Scholars","award":["2019J06010"],"award-info":[{"award-number":["2019J06010"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2021,3,31]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/3423326","type":"journal-article","created":{"date-parts":[[2020,12,10]],"date-time":"2020-12-10T18:45:07Z","timestamp":1607625907000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["A Robust Modulus-Based Matrix Splitting Iteration Method for Mixed-Cell-Height Circuit Legalization"],"prefix":"10.1145","volume":"26","author":[{"given":"Jianli","family":"Chen","sequence":"first","affiliation":[{"name":"Fuzhou University, Fuzhou, China"}]},{"given":"Ziran","family":"Zhu","sequence":"additional","affiliation":[{"name":"Fuzhou University, Fuzhou, China"}]},{"given":"Wenxing","family":"Zhu","sequence":"additional","affiliation":[{"name":"Fuzhou University, Fuzhou, China"}]},{"given":"Chang","family":"Yao-Wen","sequence":"additional","affiliation":[{"name":"National Taiwan University, Taipei, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2020,12,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1117\/12.813462"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/nla.680"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-005-0643-0"},{"key":"e_1_2_1_4_1","volume-title":"Convex Optimization","author":"Boyd Stephen"},{"key":"e_1_2_1_5_1","volume-title":"ISPD 2015 benchmarks with fence regions and routing blockages for detailed-routing-driven placement. In Proceedings of the ACM International Symposium on Physical Design. 157--164","author":"Bustany Ismail S.","year":"2015"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240765.3240828"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-012-9203-9"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3061639.3062330"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference.","author":"Chow Wing-Kai"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/43.766728"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2017.8203870"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/641876.641880"},{"key":"e_1_2_1_13_1","unstructured":"D. Hill. 2002. Method and system for high speed detailed placement of cells within integrated circuit designs. In U.S. Patent 6370673.  D. Hill. 2002. Method and system for high speed detailed placement of cells within integrated circuit designs. In U.S. Patent 6370673."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3060403.3060473"},{"key":"e_1_2_1_15_1","volume-title":"Efficient implementations of minimum-cost flow algorithms. Arxiv Preprint Arxiv:1207.6381","author":"Kir\u00e1ly Zolt\u00e1n","year":"2012"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference.","author":"Li Haocheng","year":"2018"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299902.3309750"},{"key":"e_1_2_1_18_1","first-page":"1","article-title":"MrDP: Multiple-row detailed placement of heterogeneous-sized cells for advanced nodes","volume":"7","author":"Lin Yibo","year":"2016","journal-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design."},{"key":"e_1_2_1_20_1","volume-title":"Wright","author":"Nocedal Jorge","year":"2006"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the ACM International Symposium on Physical Design. 47--53","author":"Spindler Peter"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2966986.2966994"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240765.3240827"},{"key":"e_1_2_1_24_1","volume-title":"Stability of an analog optimization circuit for quadratic programming. Systems 8 Control Letters 88","author":"Vichik Sergey","year":"2016"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference. 453--458","author":"Viswanathan Natarajan"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASPDAC.2017.7858364"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSM.2004.831522"},{"key":"e_1_2_1_28_1","volume-title":"Stone","author":"Cottle Richard W.","year":"1992"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2511141"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2017.8203761"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3240765.3240826"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3423326","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3423326","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:57Z","timestamp":1750195497000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3423326"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12,10]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3,31]]}},"alternative-id":["10.1145\/3423326"],"URL":"https:\/\/doi.org\/10.1145\/3423326","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12,10]]},"assertion":[{"value":"2020-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}