{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,25]],"date-time":"2026-04-25T14:57:34Z","timestamp":1777129054774,"version":"3.51.4"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T00:00:00Z","timestamp":1726617600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Jiangsu Government Scholarship, National Natural Science Foundation of China","award":["#92373207, #12401700, and #12471354"],"award-info":[{"award-number":["#92373207, #12401700, and #12471354"]}]},{"name":"JSPS Grant-in-Aid for Scientific Research","award":["#21H03411"],"award-info":[{"award-number":["#21H03411"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2024,11,30]]},"abstract":"<jats:p>\n            The evolution of advanced technology nodes has prompted a shift toward mixed-cell-height circuit design, while the introduction of technology and fence region constraints further increases the complexity of placement. In this article, we innovatively transform the mixed-cell-height circuit legalization problem into a generalized absolute value equation (GAVE) and propose a novel and effective robust Newton (RN) iteration method to address the challenge of the legalization problem.\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n            First, the window-based cell insertion technique is applied to obtain the initial cell row allocation and cell order, and the cells are allocated to the matching region based on the R-tree structure. Then, the legalization problem of cells within the region is transformed into a GAVE, and an RN iteration method is proposed to solve the GAVE. Finally, the maximum displacement cells and technology violation cells are optimized based on a greedy method. Experimental results confirm the efficiency and robustness of the proposed method compared with the state-of-the-art methods.\n          <\/jats:p>","DOI":"10.1145\/3689436","type":"journal-article","created":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T11:39:02Z","timestamp":1724326742000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Robust Newton Iteration Method for Mixed-Cell-Height Circuit Legalization Under Technology and Region Constraints"],"prefix":"10.1145","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1620-3705","authenticated-orcid":false,"given":"Chencan","family":"Zhou","sequence":"first","affiliation":[{"name":"Nantong University, Nantong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5519-5197","authenticated-orcid":false,"given":"Yang","family":"Cao","sequence":"additional","affiliation":[{"name":"Nantong University, Nantong China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4614-1023","authenticated-orcid":false,"given":"Quan","family":"Shi","sequence":"additional","affiliation":[{"name":"Nantong University, Nantong China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6460-5322","authenticated-orcid":false,"given":"Luxin","family":"Wang","sequence":"additional","affiliation":[{"name":"Nantong University, Nantong China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8305-604X","authenticated-orcid":false,"given":"Xiaoqing","family":"Wen","sequence":"additional","affiliation":[{"name":"Kyushu Institute of Technology, Kitakyushu, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,9,18]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"Proceedings of the International Symposium of Electronics Design Automation.","author":"Zhou Chen-Can","year":"2023","unstructured":"Chen-Can Zhou, Yang Cao, Quan Shi, and Lu-Xin Wang. 2023. A robust Newton-type iteration method for mixed-cell-height legalization. In Proceedings of the International Symposium of Electronics Design Automation."},{"key":"e_1_3_2_3_2","volume-title":"Proceedings of the ACM International Symposium on Physical Design. 9\u201316","author":"Khasawneh M.","unstructured":"M. Khasawneh and P. H. Madden. 2020. Hill climbing with trees: Detail placement for large windows. In Proceedings of the ACM International Symposium on Physical Design. 9\u201316."},{"key":"e_1_3_2_4_2","volume-title":"Filed","author":"Hill D.","year":"2002","unstructured":"D. Hill. 2002. Method and system for high speed detailed placement of cells within integrated circuit designs. U.S. Patent No. 6370673, Filed March 22, 1999, Issued April 9, 2002."},{"key":"e_1_3_2_5_2","volume-title":"Proceedings of the ACM International Symposium on Physical Design. 47\u201353","author":"Spindler Peter","unstructured":"Peter Spindler, Ulf Schlichtmann, and Frank M. Johannes. 2008. Abacus: Fast legalization of standard cell circuits with minimal movement. In Proceedings of the ACM International Symposium on Physical Design. 47\u201353."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2511141"},{"key":"e_1_3_2_7_2","volume-title":"Proceedings of the ACM\/IEEE Design Automation Conference.","author":"Chow Wing-Kai","unstructured":"Wing-Kai Chow, Chak-Wa Pui, and Evangeline F. Y. Young. 2016. Legalization algorithm for multiple-row height standard cell design. In Proceedings of the ACM\/IEEE Design Automation Conference."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2017.2748025"},{"key":"e_1_3_2_9_2","volume-title":"Proceedings of the IEEE Design, Automation, and Test in Europe Conference and Exhibition. 321\u2013324","author":"Vygen Jens","year":"1998","unstructured":"Jens Vygen. 1998. Algorithms for detailed placement of standard cells. In Proceedings of the IEEE Design, Automation, and Test in Europe Conference and Exhibition. 321\u2013324."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3505170.3506724"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3061639.3062330"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3423326"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1002\/nla.680"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.vlsi.2022.08.010"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1142\/S0218126623501293"},{"key":"e_1_3_2_16_2","volume-title":"Proceedings of the ACM International Symposium on Physical Design. 27\u201334","author":"Li Xingquan","year":"2019","unstructured":"Xingquan Li, Jianli Chen, Wenxing Zhu, and Yao-Wen Chang. 2019. Analytical mixed-cell-height legalization considering average and maximum movement minimization. In Proceedings of the ACM International Symposium on Physical Design. 27\u201334."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2017.8203870"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3240765.3240827"},{"key":"e_1_3_2_19_2","volume-title":"Proceedings of the IEEE Design, Automation, and Test in Europe Conference and Exhibition.","author":"Heo Sun Ik","year":"2019","unstructured":"Sun Ik Heo, Andrew B. Kahng, Minsoo Kim, Lutong Wang, and Chutong Yang. 2019. Detailed placement for IR drop mitigation by power staple insertion in sub-10nm VLSI. In Proceedings of the IEEE Design, Automation, and Test in Europe Conference and Exhibition."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158215"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3137007"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3053223"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.2976674"},{"key":"e_1_3_2_24_2","volume-title":"Stone","author":"Cottle Richard W.","year":"2009","unstructured":"Richard W. Cottle, Jong-Shi Pang, and Richard E. Stone. 2009. The Linear Complementarity Problem. SIAM, Philadelphia, PA."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.05.004"},{"key":"e_1_3_2_26_2","volume-title":"Matrix Analysis and Computations","author":"Bai Zhong-Zhi","unstructured":"Zhong-Zhi Bai and Jian-Yu Pan. 2021. Matrix Analysis and Computations. SIAM, Philadelphia, PA."},{"key":"e_1_3_2_27_2","volume-title":"Proceedings of the ACM Conference on Management of Data. 47\u201357","author":"Guttman A.","year":"1984","unstructured":"A. Guttman. 1984. R-trees: A dynamic index structure for spatial searching. In Proceedings of the ACM Conference on Management of Data. 47\u201357."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2014.05.017"},{"key":"e_1_3_2_29_2","volume-title":"Convex Optimization","author":"Boyd Stephen","unstructured":"Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press, Cambridge."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-008-0094-5"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2010.08.036"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-018-1439-6"},{"key":"e_1_3_2_33_2","volume-title":"Johnson","author":"Horn Roger A.","year":"2012","unstructured":"Roger A. Horn and Charles R. Johnson. 2012. Matrix Analysis. Cambridge University Press, New York, NY."},{"key":"e_1_3_2_34_2","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\u2013164","author":"Bustany Ismail S.","year":"2015","unstructured":"Ismail S. Bustany, David Chinnery, Joseph R. Shinnerl, and Vladimir Yutsis. 2015. 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\u2013164."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689436","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3689436","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:05:45Z","timestamp":1750291545000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3689436"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,18]]},"references-count":33,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,11,30]]}},"alternative-id":["10.1145\/3689436"],"URL":"https:\/\/doi.org\/10.1145\/3689436","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,18]]},"assertion":[{"value":"2023-12-21","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-09-18","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}