{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:13:40Z","timestamp":1750220020359,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2023,9,8]],"date-time":"2023-09-08T00:00:00Z","timestamp":1694131200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>\n            In Placement Legalization, it is often assumed that (almost) all standard cells possess the same height and can therefore be aligned in\n            <jats:italic>cell rows<\/jats:italic>\n            , which can then be treated independently. However, this is no longer true for recent technologies, where a substantial number of cells of double- or even arbitrary multiple-row height is to be expected. Due to interdependencies between the cell placements within several rows, the legalization task becomes considerably harder. In this article, we show how to optimize squared cell movement for pairs of adjacent rows comprising cells of single- as well as double-row height with a fixed left-to-right ordering in time \ud835\udcaa(\n            <jats:italic>n \u00b7<\/jats:italic>\n            log (\n            <jats:italic>n<\/jats:italic>\n            )), where\n            <jats:italic>n<\/jats:italic>\n            denotes the number of cells involved. Opposed to prior works, we do not artificially bound the maximum cell movement and can guarantee to find an optimum solution. Our approach also allows us to include gridding and movebound constraints for the cells. Experimental results show an average percental decrease of over 26% in the total squared movement when compared to a legalization approach that fixes cells of more than single-row height after Global Placement.\n          <\/jats:p>","DOI":"10.1145\/3579844","type":"journal-article","created":{"date-parts":[[2023,1,21]],"date-time":"2023-01-21T11:44:56Z","timestamp":1674301496000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Fast Optimal Double-row Legalization Algorithm"],"prefix":"10.1145","volume":"28","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8656-3418","authenticated-orcid":false,"given":"Stefan","family":"Hougardy","sequence":"first","affiliation":[{"name":"Research Institute for Discrete Mathematics, University of Bonn, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3664-3687","authenticated-orcid":false,"given":"Meike","family":"Neuwohner","sequence":"additional","affiliation":[{"name":"Research Institute for Discrete Mathematics, University of Bonn, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0796-1969","authenticated-orcid":false,"given":"Ulrike","family":"Schorr","sequence":"additional","affiliation":[{"name":"Cadence Design Systems Inc., Germany"}]}],"member":"320","published-online":{"date-parts":[[2023,9,8]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2253834"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/343647.343716"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2004.836733"},{"key":"e_1_3_2_5_2","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1145\/2717764.2723572","volume-title":"Proceedings of the International Symposium on Physical Design (ISPD\u201915)","author":"Bustany I.","year":"2015","unstructured":"I. Bustany, D. Chinnery, J. Shinnerl, and V. Yutsis. 2015. ISPD 2015 benchmarks with fence regions and routing blockages for detailed-routing-driven placement. In Proceedings of the International Symposium on Physical Design (ISPD\u201915). 157\u2013164."},{"key":"e_1_3_2_6_2","volume-title":"Proceedings of the 54th Annual Design Automation Conference (DAC\u201917)","author":"Chen J.","year":"2017","unstructured":"J. Chen, Z. Zhu, W. Zhu, and Y. Chang. 2017. Toward Optimal Legalization for Mixed-Cell-Height Circuit Designs. In Proceedings of the 54th Annual Design Automation Conference (DAC\u201917). 6."},{"key":"e_1_3_2_7_2","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918)","author":"Cheng Y.","year":"2018","unstructured":"Y. Cheng, D. Huang, W. Mak, and T. Wang. 2018. A Practical Detailed Placement Algorithm under Multi-Cell Spacing Constraints. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918). 8."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897937.2898038"},{"key":"e_1_3_2_9_2","first-page":"867","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201917)","author":"Darav N.","year":"2017","unstructured":"N. Darav, I. Bustany, A. Kennings, and R. Mamidi. 2017. ICCAD-2017 CAD Contest in Multi-deck Standard-cell Legalization and Benchmarks. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201917). 867\u2013871. Retrieved from http:\/\/iccad-contest.org\/2017\/Problem_C\/default.html."},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322090"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/2786290.2786299"},{"key":"e_1_3_2_12_2","first-page":"667","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201917)","author":"Han C.","year":"2017","unstructured":"C. Han, K. Han, A. Kahng, H. Lee, L. Wang, and B. Xu. 2017. Optimal Multi-Row Detailed Placement for Yield and Model-Hardware Correlation Improvements in Sub-10nm VLSI. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201917). 667\u2013674."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2859266"},{"key":"e_1_3_2_14_2","article-title":"Method and system for high speed detailed placement of cells within an integrated circuit design","author":"Hill D.","year":"2002","unstructured":"D. Hill. 2002. Method and system for high speed detailed placement of cells within an integrated circuit design. U.S. Patent 6370673. (2002).","journal-title":"U.S. Patent 6370673"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3439706.3447044"},{"key":"e_1_3_2_16_2","first-page":"149","volume-title":"Proceedings of the Great Lakes Symposium on VLSI","author":"Hung C.","year":"2017","unstructured":"C. Hung, P. Chou, and W. Mak. 2017. Mixed-cell-height Standard-cell Placement Legalization. In Proceedings of the Great Lakes Symposium on VLSI. 149\u2013154."},{"key":"e_1_3_2_17_2","first-page":"241","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference","author":"Kahng A.","year":"1999","unstructured":"A. Kahng, P. Tucker, and A. Zelikovsky. 1999. Optimization of Linear Placements for Wirelength Minimization with Free Sites. In Proceedings of the Asia and South Pacific Design Automation Conference. 241\u2013244."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/JPROC.2006.889373"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3195970.3196107"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3053223"},{"key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/3299902.3309750","volume-title":"Proceedings of the International Symposium on Physical Design (ISPD\u201919)","author":"Li X.","year":"2019","unstructured":"X. Li, J. Chen, W. Zhu, and Y. Chang. 2019. Analytical mixed-cell-height legalization considering average and maximum movement minimization. In Proceedings of the International Symposium on Physical Design (ISPD\u201919). 27\u201334."},{"key":"e_1_3_2_22_2","first-page":"1","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201916)","author":"Lin Y.","year":"2016","unstructured":"Y. Lin, B. Yu, X. Xu, J. Gao, N. Viswanathan, W. Liu, Z. Li, C. Alpert, and D. Pan. 2016. MrDP: Multiple-row Detailed Placement of Heterogeneous-sized Cells for Advanced Nodes. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201916). 1\u20138."},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/1353629.1353640","volume-title":"Proceedings of the International Symposium on Physical Design (ISPD\u201908)","author":"Spindler P.","year":"2008","unstructured":"P. Spindler, U. Schlichtmann, and F. Johannes. 2008. Abacus: Fast Legalization of Standard-cell Circuits with Minimal Movement. In Proceedings of the International Symposium on Physical Design (ISPD\u201908). 47\u201353."},{"key":"e_1_3_2_24_2","volume-title":"Row-Placement in VLSI Design: The Clumping Algorithm and a generalization","author":"Suhl U.","year":"2010","unstructured":"U. Suhl. 2010. Row-Placement in VLSI Design: The Clumping Algorithm and a generalization. Diploma thesis, University of Bonn, Research Institute for Discrete Mathematics."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.5555\/3485"},{"key":"e_1_3_2_26_2","first-page":"450","volume-title":"Proceedings of the 22nd Asia and South Pacific Design Automation Conference","author":"Wang C.","year":"2017","unstructured":"C. Wang, Y. Wu, J. Chen, Y. Chang, S. Kuo, W. Zhu, and G. Fan. 2017. An Effective Legalization Algorithm for Mixed-cell-height Standard Cells. In Proceedings of the 22nd Asia and South Pacific Design Automation Conference. 450\u2013455."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2015.2511141"},{"key":"e_1_3_2_28_2","volume-title":"Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918)","author":"Zhu Z.","year":"2018","unstructured":"Z. Zhu, X. Li, Y. Chen, J. Chen, W. Zhu, and Y. Chang. 2018. Mixed-Cell-Height Legalization Considering Technology and Region Constraints. In Proceedings of the IEEE\/ACM International Conference on Computer-Aided Design (ICCAD\u201918). 8."}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579844","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3579844","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:51:27Z","timestamp":1750182687000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3579844"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,8]]},"references-count":27,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3579844"],"URL":"https:\/\/doi.org\/10.1145\/3579844","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2023,9,8]]},"assertion":[{"value":"2022-08-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-12-25","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}