{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,7]],"date-time":"2026-11-07T03:31:42Z","timestamp":1794022302908,"version":"4.8.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,2,6]],"date-time":"2025-02-06T00:00:00Z","timestamp":1738800000000},"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":["62372109"],"award-info":[{"award-number":["62372109"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Foreign Experts Program","award":["H20240911"],"award-info":[{"award-number":["H20240911"]}]},{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"crossref","award":["2023J06017 and 2024J01984"],"award-info":[{"award-number":["2023J06017 and 2024J01984"]}],"id":[{"id":"10.13039\/501100003392","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":[[2025,3,31]]},"abstract":"<jats:p>\n            Routability has always been a significant challenge in Very Large Scale Integration (VLSI) design. To overcome the potential mismatch between the global routing results and the detailed routing requirements, track assignment is introduced to achieve an efficient routability estimation. Moreover, with the increasing scale of circuits, the intricate interconnections among the components on the chip lead to increased timing delay in signal transmission, thereby significantly impacting the performance and reliability of the circuit. Thus, to further improve the routability of the circuit, it is also critical to realize an accurate estimation of the timing delay within the track assignment stage. Existing heuristic track assignment algorithms, however, are prone to local optimality, and thus fail to provide accurate routability estimations. In this article, we propose an enhanced scalable parallel track assignment algorithm called\n            <jats:italic>SPTA 2.0<\/jats:italic>\n            for VLSI design, employing a two-stage partition strategy and considering timing delay. First, the proposed algorithm achieves efficient assignment of all wires by considering the routing information from both the global and local nets. Second, the overlap cost, the blockage cost, and the wirelength cost can be minimized to significantly improve the routability. Third, a critical wire controlling strategy is proposed to optimize signal timing delays inside nets. Finally, a two-stage partition strategy and a panel-subpanel-level parallelism are designed to further reduce the runtime, improving the scalability of the proposed methodology. Experimental results on multiple benchmarks demonstrate that the proposed method provides better routability estimations, and leads to superior track assignment solutions compared with existing algorithms.\n          <\/jats:p>","DOI":"10.1145\/3712009","type":"journal-article","created":{"date-parts":[[2025,1,14]],"date-time":"2025-01-14T11:24:53Z","timestamp":1736853893000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["SPTA 2.0: Enhanced Scalable Parallel Track Assignment Algorithm with Two-Stage Partition Considering Timing Delay"],"prefix":"10.1145","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0009-0003-7876-9944","authenticated-orcid":false,"given":"Huayang","family":"Cai","sequence":"first","affiliation":[{"name":"Fuzhou University, Fuzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-2939-2961","authenticated-orcid":false,"given":"Pengcheng","family":"Huang","sequence":"additional","affiliation":[{"name":"Fuzhou University, Fuzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3099-4371","authenticated-orcid":false,"given":"Genggeng","family":"Liu","sequence":"additional","affiliation":[{"name":"Fuzhou University, Fuzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5396-110X","authenticated-orcid":false,"given":"Xing","family":"Huang","sequence":"additional","affiliation":[{"name":"Northwestern Polytechnical University, Xi'an, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-1768-1116","authenticated-orcid":false,"given":"Yidan","family":"Jing","sequence":"additional","affiliation":[{"name":"Fuzhou University, Fuzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-7533-2497","authenticated-orcid":false,"given":"Wenhao","family":"Liu","sequence":"additional","affiliation":[{"name":"Hsinchu, NVIDIA, Hsinchu, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3435-0418","authenticated-orcid":false,"given":"Ting-Chi","family":"Wang","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Hsinchu, Taiwan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,2,6]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"1","volume-title":"Proceedings of the International Conference on Very Large Scale Integration.","author":"Jing Yidan","year":"2022","unstructured":"Yidan Jing, Liliang Yang, Zhen Zhuang, Genggeng Liu, Xing Huang, Wen-Hao Liu, and Ting-Chi Wang. 2022. SPTA: A scalable parallel ilp-based track assignment algorithm with two-stage partition. In Proceedings of the International Conference on Very Large Scale Integration.1\u20136."},{"key":"e_1_3_2_3_2","volume-title":"Electronic Design Automation: Synthesis, Verification, and Test","author":"Wang Laung-Terng","year":"2009","unstructured":"Laung-Terng Wang, Yao-Wen Chang, and Kwang-Ting Tim Cheng. 2009. Electronic Design Automation: Synthesis, Verification, and Test. Morgan Kaufmann."},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1497561.1497575"},{"key":"e_1_3_2_5_2","first-page":"59","volume-title":"Proceedings of the International Conference on Computer-Aided Design","author":"Batterywala Shabbir","year":"2002","unstructured":"Shabbir Batterywala, Narendra Shenoy, William Nicholls, and Hai Zhou. 2002. Track assignment: A desirable intermediate step between global routing and detailed routing. In Proceedings of the International Conference on Computer-Aided Design. 59\u201366."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/1929943.1929951"},{"issue":"5","key":"e_1_3_2_7_2","first-page":"872","article-title":"Track routing and optimization for yield","volume":"27","author":"Cho Minsik","year":"2007","unstructured":"Minsik Cho, Hua Xiang, Ruchir Puri, and David Z Pan. 2007. Track routing and optimization for yield. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 27, 5 (2007), 872\u2013882.","journal-title":"IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems"},{"key":"e_1_3_2_8_2","first-page":"381","volume-title":"Proceedings of the IEEE International SOC Conference","author":"Lai Bi-Ting","year":"2012","unstructured":"Bi-Ting Lai, Tai-Hung Li, and Tai-Chen Chen. 2012. Native-conflict-avoiding track routing for double patterning technology. In Proceedings of the IEEE International SOC Conference. 381\u2013386."},{"key":"e_1_3_2_9_2","first-page":"515","volume-title":"Proceedings of the Great Lakes Symposium on VLSI","author":"Chen Xinda","year":"2023","unstructured":"Xinda Chen, Rongliang Fu, Junying Huang, Huawei Cao, Zhimin Zhang, Xiaochun Ye, Tsung-Yi Ho, and Dongrui Fan. 2023. JRouter: A multi-terminal hierarchical length-matching router under planar manhattan routing model for RSFQ circuits. In Proceedings of the Great Lakes Symposium on VLSI. 515\u2013520."},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1145\/3380446.3430629","volume-title":"Proceedings of the ACM\/IEEE Workshop on Machine Learning for CAD","author":"Liao Haiguang","year":"2020","unstructured":"Haiguang Liao, Qingyi Dong, Weiyi Qi, Elias Fallon, and Levent Burak Kara. 2020. Track-assignment detailed routing using attention-based policy model with supervision. In Proceedings of the ACM\/IEEE Workshop on Machine Learning for CAD. 105\u2013110."},{"key":"e_1_3_2_11_2","first-page":"1","volume-title":"Proceedings of the International VLSI Symposium on Technology, Systems and Applications","author":"Chen Hung-Ming","year":"2023","unstructured":"Hung-Ming Chen, Cheng-Li Hsiao, Wei-Tung Chao, and I-Chun Hsieh. 2023. On generating cell library in advanced nodes: Efforts and challenges. In Proceedings of the International VLSI Symposium on Technology, Systems and Applications. 1\u20134."},{"key":"e_1_3_2_12_2","first-page":"1","volume-title":"Proceedings of the Design Automation Conference","author":"Li Yih-Lang","year":"2019","unstructured":"Yih-Lang Li, Shih-Ting Lin, Shinichi Nishizawa, Hong-Yan Su, Ming-Jie Fong, Oscar Chen, and Hidetoshi Onodera. 2019. NCTUcell: A DDA-aware cell library generator for FinFET structure with implicitly adjustable grid map. In Proceedings of the Design Automation Conference. 1\u20136."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/1950815.1950939"},{"key":"e_1_3_2_14_2","first-page":"1156","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conference","author":"Wu Di","year":"2005","unstructured":"Di Wu, R. Mahapatra, Jiang Hu, and Min Zhao. 2005. Timing driven track routing considering coupling capacitance. In Proceedings of the Asia and South Pacific Design Automation Conference. 1156\u20131159."},{"key":"e_1_3_2_15_2","first-page":"382","volume-title":"Proceedings of the International Conference on Computer Aided Design.","author":"Ho Tsung-Yi","year":"2003","unstructured":"Tsung-Yi Ho, Yao-Wen Chang, Sao-Jie Chen, and Der-Tsai Lee. 2003. A fast crosstalk-and performance-driven multilevel routing system. In Proceedings of the International Conference on Computer Aided Design.382\u2013387."},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1145\/1531542.1531625","volume-title":"Proceedings of the ACM Great Lakes Symposium on VLSI","author":"Chen Mingjing","year":"2009","unstructured":"Mingjing Chen and Alex Orailoglu. 2009. Deflecting crosstalk by routing reconsideration through refined signal correlation estimation. In Proceedings of the ACM Great Lakes Symposium on VLSI. 369\u2013374."},{"key":"e_1_3_2_17_2","first-page":"55","volume-title":"Proceedings of the Design Automation Conference","author":"Cho Minsik","year":"2007","unstructured":"Minsik Cho, Hua Xiang, Ruchir Puri, and David Z. Pan. 2007. TROY: Track router with yield-driven wire planning. In Proceedings of the Design Automation Conference. 55\u201358."},{"key":"e_1_3_2_18_2","first-page":"506","volume-title":"Proceedings of the IEEE International Conference on Computer Design","author":"Zhao Qiong","year":"2012","unstructured":"Qiong Zhao and Jiang Hu. 2012. Track assignment considering crosstalk-induced performance degradation. In Proceedings of the IEEE International Conference on Computer Design. 506\u2013507."},{"key":"e_1_3_2_19_2","first-page":"378","volume-title":"Proceedings of the Asia and South Pacific Design Automation Conferencee","author":"Wong Man-Pan","year":"2016","unstructured":"Man-Pan Wong, Wen-Hao Liu, and Ting-Chi Wang. 2016. Negotiation-based track assignment considering local nets. In Proceedings of the Asia and South Pacific Design Automation Conferencee. 378\u2013383."},{"issue":"8","key":"e_1_3_2_20_2","first-page":"758","article-title":"A track assignment algorithm based on hybrid discrete particle swarm optimization","volume":"32","author":"Guo Wenzhong","year":"2019","unstructured":"Wenzhong Guo, Xiaohua Chen, Genggeng Liu, and Guolong Chen. 2019. A track assignment algorithm based on hybrid discrete particle swarm optimization. Pattern Recognition and Artificial Intelligence (in Chinese) 32, 8 (2019), 758\u2013770.","journal-title":"Pattern Recognition and Artificial Intelligence (in Chinese)"},{"key":"e_1_3_2_21_2","first-page":"1","volume-title":"Proceedings of the Design Automation Conference","author":"Shi Daohang","year":"2017","unstructured":"Daohang Shi and Azadeh Davoodi. 2017. TraPL: Track planning of local congestion for global routing. In Proceedings of the Design Automation Conference. 1\u20136."},{"key":"e_1_3_2_22_2","first-page":"315","volume-title":"Proceedings of the Great Lakes Symposium on VLSI","author":"Liu Genggeng","year":"2019","unstructured":"Genggeng Liu, Zhen Zhuang, Wenzhong Guo, and Ting-Chi Wang. 2019. RDTA: An efficient routability-driven track assignment algorithm. In Proceedings of the Great Lakes Symposium on VLSI. 315\u2013318."},{"key":"e_1_3_2_23_2","volume-title":"Proceedings of the 2022 Design, Automation and Test in Europe Conference and Exhibition .766\u2013771","author":"Zhuang Zhen","year":"2022","unstructured":"Zhen Zhuang, Genggeng Liu, Tsung-Yi Ho, Bei Yu, and Wenzhong Guo. 2022. TRADER: A practical track-assignment-based detailed router. In Proceedings of the 2022 Design, Automation and Test in Europe Conference and Exhibition .766\u2013771."},{"issue":"9","key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"1655","DOI":"10.1109\/TVLSI.2012.2214491","article-title":"RegularRoute: An efficient detailed router applying regular routing patterns","volume":"21","author":"Zhang Yanheng","year":"2012","unstructured":"Yanheng Zhang and Chris Chu. 2012. RegularRoute: An efficient detailed router applying regular routing patterns. IEEE Transactions on Very Large Scale Integration Systems 21, 9 (2012), 1655\u20131668.","journal-title":"IEEE Transactions on Very Large Scale Integration Systems"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Markus Ahrens Dorothee Henke Stefan Rabenstein and Jens Vygen. 2024. Faster goal-oriented shortest path search for bulk and incremental detailed routing. Mathematical Programming 206 1 (2024) 3\u201332.","DOI":"10.1007\/s10107-023-01962-4"},{"key":"e_1_3_2_26_2","first-page":"955","volume-title":"Proceedings of the Design Automation Conference","author":"Nie Szu-Ru","year":"2022","unstructured":"Szu-Ru Nie, Yen-Ting Chen, and Yao-Wen Chang. 2022. Y-architecture-based flip-chip routing with dynamic programming-based bend minimization. In Proceedings of the Design Automation Conference. 955\u2013960."},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","unstructured":"Ziran Zhu Zhipeng Huang Jianli Chen and Longkun Guo. 2021. Topology-aware bus routing in complex networks of very-large-scale integration with nonuniform track configurations and obstacles. Complexity 2021 1 (2021) 1\u201312.","DOI":"10.1155\/2021\/8843271"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2007.907003"},{"key":"e_1_3_2_29_2","first-page":"25","volume-title":"Proceedings of the IEEE Computer Society Annual Symposium on VLSI","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. In Proceedings of the IEEE Computer Society Annual Symposium on VLSI. 25\u201330."},{"key":"e_1_3_2_30_2","first-page":"772","volume-title":"Proceedings of the Design, Automation Test in Europe Conference Exhibition","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. In Proceedings of the Design, Automation Test in Europe Conference Exhibition. 772\u2013777."},{"key":"e_1_3_2_31_2","first-page":"61","volume-title":"Proceedings of the International Symposium on Physical Design","author":"Kay Rony","year":"2000","unstructured":"Rony Kay and Rob A. Rutenbar. 2000. Wire packing: A strong formulation of crosstalk-aware chip-level track\/layer assignment with an efficient integer programming solution. In Proceedings of the International Symposium on Physical Design. 61\u201368."},{"key":"e_1_3_2_32_2","first-page":"245","volume-title":"Proceedings of the Design, Automation Test in Europe Conference Exhibition","author":"Lu Hsueh-Ju","year":"2016","unstructured":"Hsueh-Ju Lu, En-Jang Jang, Ang Lu, Yu Ting Zhang, Yu-He Chang, Chi-Hung Lin, and Rung-Bin Lin. 2016. Practical ILP-based routing of standard cells. In Proceedings of the Design, Automation Test in Europe Conference Exhibition. 245\u2013248."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035464"},{"key":"e_1_3_2_34_2","first-page":"715","volume-title":"Proceedings of the Design Automation Conference","author":"Ismail Yehea I.","year":"1999","unstructured":"Yehea I. Ismail, Eby G. Friedman, and Jose L. Neves. 1999. Equivalent Elmore delay for RLC trees. In Proceedings of the Design Automation Conference. 715\u2013720."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/0205051"},{"issue":"1","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/1024022","article-title":"Computers and intractability: A guide to the theory of np-completeness","volume":"24","author":"Garey Michael R.","year":"1982","unstructured":"Michael R. Garey and David S. Johnson. 1982. Computers and intractability: A guide to the theory of np-completeness. Siam Review 24, 1 (1982), 90.","journal-title":"Siam Review"},{"key":"e_1_3_2_37_2","first-page":"200","volume-title":"Proceedings of the Design Automation Conference","author":"Liu Wen-Hao","year":"2010","unstructured":"Wen-Hao Liu, Wei-Chun Kao, Yih-Lang Li, and Kai-Yuan Chao. 2010. Multi-threaded collision-aware global routing with bounded-length maze routing. In Proceedings of the Design Automation Conference. 200\u20132058."},{"key":"e_1_3_2_38_2","first-page":"1","volume-title":"Proceedings of the Design Automation Conference","author":"Hsu Meng-Kai","year":"2013","unstructured":"Meng-Kai Hsu, Yi-Fang Chen, Chau-Chin Huang, Tung-Chieh Chen, and Yao-Wen Chang. 2013. Routability-driven placement for hierarchical mixed-size circuit designs. In Proceedings of the Design Automation Conference. 1\u20136."},{"key":"e_1_3_2_39_2","first-page":"774","volume-title":"Proceedings of the Design Automation Conference","author":"Viswanathan Natarajan","year":"2012","unstructured":"Natarajan Viswanathan, Charles Alpert, Cliff Sze, Zhuo Li, and Yaoguang Wei. 2012. The DAC 2012 routability-driven placement contest and benchmark suite. In Proceedings of the Design Automation Conference. 774\u2013782."},{"issue":"4","key":"e_1_3_2_40_2","doi-asserted-by":"crossref","first-page":"830","DOI":"10.1109\/TPDS.2021.3107775","article-title":"LB4OMP: A dynamic load balancing library for multithreaded applications","volume":"33","author":"Kornd\u00f6rfer Jonas H. M\u00fcller","year":"2021","unstructured":"Jonas H. M\u00fcller Kornd\u00f6rfer, Ahmed Eleliemy, Ali Mohammed, and Florina M. Ciorba. 2021. LB4OMP: A dynamic load balancing library for multithreaded applications. IEEE Transactions on Parallel and Distributed Systems 33, 4 (2021), 830\u2013841.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"}],"container-title":["ACM Transactions on Design Automation of Electronic Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712009","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3712009","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:10Z","timestamp":1750295890000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3712009"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,6]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,3,31]]}},"alternative-id":["10.1145\/3712009"],"URL":"https:\/\/doi.org\/10.1145\/3712009","relation":{},"ISSN":["1084-4309","1557-7309"],"issn-type":[{"value":"1084-4309","type":"print"},{"value":"1557-7309","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,6]]},"assertion":[{"value":"2024-04-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-06","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}