{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:46Z","timestamp":1750309186743,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,2,15]],"date-time":"2024-02-15T00:00:00Z","timestamp":1707955200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62204111"],"award-info":[{"award-number":["62204111"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Des. Autom. Electron. Syst."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Placement is a critical step in the physical design for digital application specific integrated circuits (ASICs), as it can directly affect the design qualities such as wirelength and timing. For many domain specific designs, the demands for high performance parallel computing result in repetitive hardware instances, such as the processing elements in the neural network accelerators. As these instances can dominate the area of the designs, the runtime of the complete design\u2019s placement can be traded for optimizing and reusing one instance\u2019s placement to achieve higher quality. Therefore, this work proposes a mixed integer programming (MIP)-based placement refinement algorithm for the repetitive instances. By efficiently modeling the rectilinear steiner tree wirelength, the placement can be precisely refined for better quality. Besides, the MIP formulations for timing-driven placement are proposed. A theoretical proof is then provided to show the correctness of the proposed wirelength model. For the instances in various popular fields, the experiments show that given the placement from the commercial placers, the proposed algorithm can perform further placement refinement to reduce 3.76%\/3.64% detailed routing wirelength and 1.68%\/2.42% critical path delay under wirelength\/timing-driven mode, respectively, and also outperforms the state-of-the-art previous work.<\/jats:p>","DOI":"10.1145\/3639365","type":"journal-article","created":{"date-parts":[[2024,1,3]],"date-time":"2024-01-03T21:33:33Z","timestamp":1704317613000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Mixed Integer Programming based Placement Refinement by RSMT Model with Movable Pins"],"prefix":"10.1145","volume":"29","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6461-3314","authenticated-orcid":false,"given":"Ke","family":"Tang","sequence":"first","affiliation":[{"name":"Nanjing University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9943-0550","authenticated-orcid":false,"given":"Lang","family":"Feng","sequence":"additional","affiliation":[{"name":"Sun Yat-sen University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7227-4786","authenticated-orcid":false,"given":"Zhongfeng","family":"Wang","sequence":"additional","affiliation":[{"name":"Nanjing University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,2,15]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3590962"},{"key":"e_1_3_1_3_2","first-page":"772","article-title":"CR&P: An efficient co-operation between routing and placement","author":"Aghaeekiasaraee Erfan","year":"2022","unstructured":"Erfan Aghaeekiasaraee, Aysa Fakheri Tabrizi, Tiago Augusto Fontana, Renan Netto, Sheiny Fabre Almeida, Upma Gandhi, Jos\u00e9 Lu\u00eds G\u00fcntzel, David Westwick, and Laleh Behjat. 2022. CR&P: An efficient co-operation between routing and placement. Design, Automation and Test in Europe Conference and Exhibition (2022), 772\u2013777.","journal-title":"Design, Automation and Test in Europe Conference and Exhibition"},{"key":"e_1_3_1_4_2","first-page":"1","article-title":"Improving linear programming approaches for the steiner tree problem","author":"Althaus Ernst","year":"2003","unstructured":"Ernst Althaus, Tobias Polzin, and Siavash Vahdati Daneshmand. 2003. Improving linear programming approaches for the steiner tree problem. International Conference on Experimental and Efficient Algorithms (2003), 1\u201314.","journal-title":"International Conference on Experimental and Efficient Algorithms"},{"key":"e_1_3_1_5_2","unstructured":"ASAP 7nm Predictive PDK. 2017. Retrieved from http:\/\/asap.asu.edu\/asap\/"},{"key":"e_1_3_1_6_2","unstructured":"BIKE. 2023. Retrieved from https:\/\/bikesuite.org\/"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2008.923063"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2859220"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907068"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2018.2801231"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12691-3_46"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/TVLSI.2022.3197282"},{"key":"e_1_3_1_13_2","first-page":"25","article-title":"ILP-based global routing optimization with cell movements","author":"Fontana Tiago Augusto","year":"2021","unstructured":"Tiago Augusto Fontana, Erfan Aghaeekiasaraee, Renan Netto, Sheiny Fabre Almeida, Upma Gandh, Aysa Fakheri Tabrizi, David Westwick, Laleh Behjat, and Jos\u00e9 Lu\u00eds G\u00fcntzel. 2021. ILP-based global routing optimization with cell movements. IEEE Computer Society Annual Symposium on VLSI (2021), 25\u201330.","journal-title":"IEEE Computer Society Annual Symposium on VLSI"},{"key":"e_1_3_1_14_2","unstructured":"Gurobi Optimizer. 2023. Retrieved from https:\/\/www.gurobi.com\/"},{"key":"e_1_3_1_15_2","first-page":"141","article-title":"Timing-driven placement based on dynamic net-weighting for efficient slack histogram compression","author":"Guth Chrystian","year":"2015","unstructured":"Chrystian Guth, Vinicius Livramento, Renan Netto, Renan Fonseca, Jos\u00e9 Lu\u00eds G\u00fcntzel, and Luiz Santos. 2015. Timing-driven placement based on dynamic net-weighting for efficient slack histogram compression. Symposium on International Symposium on Physical Design (2015), 141\u2013148.","journal-title":"Symposium on International Symposium on Physical Design"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/1735023.1735035"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/0130013"},{"key":"e_1_3_1_18_2","unstructured":"ISPD 2018 Contest. 2018. Retrieved from https:\/\/www.ispd.cc\/contests\/18\/"},{"key":"e_1_3_1_19_2","unstructured":"ISPD 2019 Contest. 2019. Retrieved from https:\/\/www.ispd.cc\/contests\/19\/"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-018-0135-8"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2002.1013891"},{"key":"e_1_3_1_22_2","first-page":"172","article-title":"A novel net weighting algorithm for timing-driven placement","author":"Kong Tim","year":"2002","unstructured":"Tim Kong. 2002. A novel net weighting algorithm for timing-driven placement. IEEE\/ACM International Conference on Computer Aided Design (2002), 172\u2013176.","journal-title":"IEEE\/ACM International Conference on Computer Aided Design"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2020.2992747"},{"key":"e_1_3_1_24_2","unstructured":"Ratnesh Kumar Wai Kit Leong Robert and J.R. Heath. 2000. An integer programming approach to placement and routing in circuit layout. (2000) 1\u201322."},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2021.3053223"},{"key":"e_1_3_1_26_2","first-page":"1","article-title":"PDPU: An open-source posit dot-product unit for deep learning applications","author":"Li Qiong","year":"2023","unstructured":"Qiong Li, Chao Fang, and Zhongfeng Wang. 2023. PDPU: An open-source posit dot-product unit for deep learning applications. IEEE International Symposium on Circuits and Systems (2023), 1\u20135.","journal-title":"IEEE International Symposium on Circuits and Systems"},{"key":"e_1_3_1_27_2","first-page":"87","article-title":"Mixed integer programming models for detailed placement","author":"Li Shuai","year":"2012","unstructured":"Shuai Li and Cheng-Kok Koh. 2012. Mixed integer programming models for detailed placement. ACM International Symposium on International Symposium on Physical Design (2012), 87\u201394.","journal-title":"ACM International Symposium on International Symposium on Physical Design"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.3003843"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.2971531"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2699873"},{"key":"e_1_3_1_31_2","article-title":"Reconfigurable and high-efficiency polynomial multiplication accelerator for CRYSTALS-kyber","author":"Minghao Li","year":"2023","unstructured":"Li Minghao, Tian Jing, Hu Xiao, and Zhongfeng Wang. 2023. Reconfigurable and high-efficiency polynomial multiplication accelerator for CRYSTALS-kyber. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 42, 8 (2023), 2540\u20132551.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"e_1_3_1_32_2","unstructured":"OpenDP. 2019. Retrieved from https:\/\/github.com\/sanggido\/OpenDP"},{"issue":"7","key":"e_1_3_1_33_2","first-page":"1970","article-title":"Mr.Wolf: An energy-precision scalable parallel ultra low power soc for IoT edge processing","volume":"54","author":"Pullini Antonio","year":"2019","unstructured":"Antonio Pullini, Davide Rossi, Igor Loi, Giuseppe Tagliavini, and Luca Benini. 2019. Mr.Wolf: An energy-precision scalable parallel ultra low power soc for IoT edge processing. IEEE Transactions on Very Large Scale Integration Systems 54, 7 (2019), 1970\u20131981.","journal-title":"IEEE Transactions on Very Large Scale Integration Systems"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-021-01757-5"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(92)90053-6"},{"key":"e_1_3_1_36_2","first-page":"179","article-title":"Fast and robust quadratic placement combined with an exact linear net model","author":"Spindler Peter","year":"2006","unstructured":"Peter Spindler and Frank M. Johannes. 2006. Fast and robust quadratic placement combined with an exact linear net model. IEEE\/ACM International Conference on Computer Aided Design (2006), 179\u2013186.","journal-title":"IEEE\/ACM International Conference on Computer Aided Design"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2021.3131850"},{"key":"e_1_3_1_38_2","first-page":"65","article-title":"Mixed-cell-height detailed placement considering complex minimum-implant-area constraints","author":"Wu Yen-Yi","year":"2017","unstructured":"Yen-Yi Wu and Yao-Wen Chang. 2017. Mixed-cell-height detailed placement considering complex minimum-implant-area constraints. IEEE\/ACM International Conference on Computer-Aided Design (2017), 65\u201372.","journal-title":"IEEE\/ACM International Conference on Computer-Aided Design"},{"key":"e_1_3_1_39_2","first-page":"230","article-title":"An efficient CNN training accelerator leveraging transposable block sparsity","author":"Xu Mingyang","year":"2022","unstructured":"Mingyang Xu, Jinming Lu, Zhongfeng Wang, and Jun Lin. 2022. An efficient CNN training accelerator leveraging transposable block sparsity. IEEE International Conference on Artificial Intelligence Circuits and Systems (2022), 230\u2013233.","journal-title":"IEEE International Conference on Artificial Intelligence Circuits and Systems"},{"issue":"1","key":"e_1_3_1_40_2","doi-asserted-by":"crossref","first-page":"328","DOI":"10.46586\/tches.v2021.i2.328-356","article-title":"A compact hardware implementation of CCA-secure key exchange mechanism CRYSTALS-KYBER on FPGA","volume":"2021","author":"Yufei Xing","year":"2021","unstructured":"Xing Yufei and Li Shuguo. 2021. A compact hardware implementation of CCA-secure key exchange mechanism CRYSTALS-KYBER on FPGA. IACR Transactions on Cryptographic Hardware and Embedded Systems 2021, 1 (2021), 328\u2013356.","journal-title":"IACR Transactions on Cryptographic Hardware and Embedded Systems"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/OJCAS.2020.3019403"},{"key":"e_1_3_1_42_2","first-page":"253","article-title":"FPGA-based key generator for the niederreiter cryptosystem using binary goppa codes","author":"Zhu Danyang","year":"2017","unstructured":"Danyang Zhu, Siyuan Lu, Meiqi Wang, Jun Lin, and Zhongfeng Wang. 2017. FPGA-based key generator for the niederreiter cryptosystem using binary goppa codes. Cryptographic Hardware and Embedded Systems (2017), 253\u2013274.","journal-title":"Cryptographic Hardware and Embedded Systems"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSII.2020.3002564"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639365","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639365","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:11Z","timestamp":1750287251000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639365"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,15]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1145\/3639365"],"URL":"https:\/\/doi.org\/10.1145\/3639365","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"type":"print","value":"1084-4309"},{"type":"electronic","value":"1557-7309"}],"subject":[],"published":{"date-parts":[[2024,2,15]]},"assertion":[{"value":"2023-06-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}