{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:24:00Z","timestamp":1770895440497,"version":"3.50.1"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"name":"TSMC, Synopsys, and NSTC of Taiwan","award":["NSTC 113-2927-I-011-502, 113-2640-E-002-001, 113-2640-E-006-001, 113-2222-E-011-005-MY3"],"award-info":[{"award-number":["NSTC 113-2927-I-011-502, 113-2640-E-002-001, 113-2640-E-006-001, 113-2222-E-011-005-MY3"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2026,5,31]]},"abstract":"<jats:p>Mixed-cell-height VLSI circuits are widely used to meet various design requirements. Due to design for manufacturability (DFM) considerations such as layout-dependent effects (LDEs), drain-to-drain abutment (DDA), and pattern coloring for multiple patterning, different spacings between adjacent cells affect performance, modeled as discrete spacing costs. A state-of-the-art dynamic programming (DP) approach can address this problem but can only handle a few cell rows simultaneously due to its high complexity. In this article, we propose a novel DP algorithm that can solve the problem optimally and more efficiently. Additionally, several optimality-preserving reduction techniques are employed to derive full-chip optimal solutions for large-scale designs. Experimental results demonstrate that the proposed approach significantly outperforms existing methods in terms of total spacing cost and total displacement.<\/jats:p>","DOI":"10.1145\/3742429","type":"journal-article","created":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T04:54:34Z","timestamp":1748580874000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Mixed-Cell-Height Detailed Placement with Discrete Spacing Costs"],"prefix":"10.1145","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5101-3439","authenticated-orcid":false,"given":"Da-Wei","family":"Huang","sequence":"first","affiliation":[{"name":"National Taiwan University of Science and Technology","place":["Taipei, Taiwan"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5052-1993","authenticated-orcid":false,"given":"Ying-Jie","family":"Jiang","sequence":"additional","affiliation":[{"name":"National Taiwan University of Science and Technology","place":["Taipei, Taiwan"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6675-2676","authenticated-orcid":false,"given":"Shao-Yun","family":"Fang","sequence":"additional","affiliation":[{"name":"Electrical Engineering, National Taiwan University of Science and Technology","place":["Taipei, Taiwan"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,2,11]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3061639.3062330"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3240765.3240828"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC18072.2020.9218513"},{"key":"e_1_3_2_5_2","first-page":"1103","article-title":"Mixed-cell-height placement with drain-to-drain abutment and region constraints","volume":"41","author":"Chen J.","year":"2021","unstructured":"J. Chen, Z. Zhu, L. Guo, Y.-W. Tseng, and Y.-W. Chang. 2021. Mixed-cell-height placement with drain-to-drain abutment and region constraints. IEEE TCAD 41, 4 (2021), 1103\u20131115.","journal-title":"IEEE TCAD"},{"key":"e_1_3_2_6_2","first-page":"4681","article-title":"NBLG: A robust legalizer for mixed-cell-height modern design","volume":"41","author":"Chen J.","year":"2022","unstructured":"J. Chen, Z. Di, J. Shi, Q. Feng, and Q. Wu. 2022. NBLG: A robust legalizer for mixed-cell-height modern design. IEEE TCAD 41, 11 (2022), 4681\u20134693.","journal-title":"IEEE TCAD"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3240765.3240772"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897937.2898038"},{"key":"e_1_3_2_9_2","volume-title":"Proc. ICCAD. 1\u20138.","author":"Han C.","unstructured":"C. Han, K. Han A. B. 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. Proc. ICCAD. 1\u20138."},{"key":"e_1_3_2_10_2","first-page":"1703","article-title":"Enhanced optimal multi-row detailed placement for neighbor diffusion effect mitigation in sub-10 nm VLSI","volume":"38","author":"Han C.","year":"2019","unstructured":"C. Han, A. B. Kahng, L.Wang, and B. Xu. 2019. Enhanced optimal multi-row detailed placement for neighbor diffusion effect mitigation in sub-10 nm VLSI. IEEE TCAD 38, 9 (2019), 1703\u20131716.","journal-title":"IEEE TCAD"},{"key":"e_1_3_2_11_2","volume-title":"Proc. DATE. 1\u20136.","author":"Heo S.","unstructured":"S. Heo, A. B. Kahng, M. Kim, L. Wang, and C. Yang. 2019. Detailed placement for IR drop mitigation by power staple insertion in sub-10nm VLSI. Proc. DATE. 1\u20136."},{"key":"e_1_3_2_12_2","volume-title":"Proc. ICCAD. 1\u20138.","author":"Huang D.-W.","year":"2023","unstructured":"D.-W. Huang, Y.-J. Jiang, and S.-Y. Fang. 2023. Spacing cost-aware optimal and efficient mixed-cell-eight detailed placement for DFM considerations. Proc. ICCAD. 1\u20138."},{"key":"e_1_3_2_13_2","volume-title":"Proc. DAC. 1\u20136.","author":"Li H.","unstructured":"H. Li, W.-K. Chow, G. Chen, E. F. Y. Young, and B. Yu. 2018. Routability-driven and fence-aware legalization for mixed-cell-height circuits. Proc. DAC. 1\u20136."},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299902.3309750"},{"key":"e_1_3_2_15_2","first-page":"143","article-title":"Pin-accessible legalization for mixed-cell-height circuits","volume":"41","author":"Li H.","year":"2022","unstructured":"H. Li, W.-K. Chow, G. Chen, B. Yu, and E. F. Y. Young. 2022. Pin-accessible legalization for mixed-cell-height circuits. IEEE TCAD 41, 1 (2022), 143\u2013154.","journal-title":"IEEE TCAD"},{"key":"e_1_3_2_16_2","volume-title":"Proc. ASP-DAC. 1\u20136.","author":"Lin Y.","unstructured":"Y. Lin, B. Yu, Y. Zou, Z. Li, C. J. Alpert, and D. Z. Pan. 2016. Stitch aware detailed placement for multiple e-beam lithography. Proc. ASP-DAC. 1\u20136."},{"key":"e_1_3_2_17_2","first-page":"1237","article-title":"MrDP: Multiple-row detailed placement of heterogeneous-sized cells for advanced nodes","volume":"37","author":"Lin Y.","year":"2018","unstructured":"Y. Lin, B. Yu, X. Xu, J.-R. Gao, N. Viswanathan, W.-H. Liu, Z. Li, C. J. Alpert, and D. Z. Pan. 2018. MrDP: Multiple-row detailed placement of heterogeneous-sized cells for advanced nodes. IEEE TCAD 37, 6 (2018), 1237\u20131250.","journal-title":"IEEE TCAD"},{"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":"Proc. ASP-DAC. 1\u20136.","author":"Wang C.-H.","unstructured":"C.-H. Wang, Y.-Y. Wu, J. Chen, Y.-W. Chang, S.-Y. Kuo, W. Zhu, and G. Fan. 2017. An effective legalization algorithm for mixed-cell-height standard cells. Proc. ASP-DAC. 1\u20136."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.23919\/DATE56975.2023.10137236"},{"key":"e_1_3_2_21_2","first-page":"1569","article-title":"Detailed placement algorithm for VLSI design with double-row height standard cells","volume":"35","author":"Wu G.","year":"2016","unstructured":"G. Wu and C. Chu. 2016. Detailed placement algorithm for VLSI design with double-row height standard cells. IEEE TCAD 35, 9 (2016), 1569\u20131573.","journal-title":"IEEE TCAD"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCAD.2017.8203761"},{"key":"e_1_3_2_23_2","volume-title":"Proc. DATE. 1\u20136.","author":"Yang H.","unstructured":"H. Yang, K. Fung, Y. Zhao, Y. Lin, and B. Yu. 2022. Mixed-cell-height legalization on CPU-GPU heterogeneous systems. Proc. DATE. 1\u20136."},{"key":"e_1_3_2_24_2","volume-title":"Proc. DAC. 1\u20136.","author":"Yu T.-C.","unstructured":"T.-C. Yu, S.-Y. Fang, H.-S. Chiu, K.-S. Hu, P. H.-Y. Tai, C.-F. C. Shen, and H. Sheng. 2019. Pin accessibility prediction and optimization with deep learning-based pin pattern recognition. Proc. DAC. 1\u20136."},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3240765.3240826"},{"key":"e_1_3_2_26_2","unstructured":"ICCAD-2017 CAD Contest in Multi-Deck Standard-Cell Legalization. Retrieved from http:\/\/iccad-contest.org\/2017\/index.html"},{"key":"e_1_3_2_27_2","unstructured":"Cadence Innovus Implementation System. Retrieved from https:\/\/www.cadence.com\/zhTW\/home\/tools\/digital-designand-signoff\/soc-implementation-and-floorplanning\/innovus-implementation-system.html"},{"key":"e_1_3_2_28_2","unstructured":"OpenDP: Open-Source Detailed Placement Engine. Retrieved from https:\/\/openroad.readthedocs.io\/en\/latest\/main\/src\/dpl\/README.html"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3742429","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T10:38:19Z","timestamp":1770892699000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3742429"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,11]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,31]]}},"alternative-id":["10.1145\/3742429"],"URL":"https:\/\/doi.org\/10.1145\/3742429","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,11]]},"assertion":[{"value":"2024-08-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-13","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}