SPTA 2.0: Enhanced Scalable Parallel Track Assignment Algorithm with Two-Stage Partition Considering Timing Delay

作     者：Cai, Huayang Huang, Pengcheng Liu, Genggeng Huang, Xing Jing, Yidan Liu, Wenhao Wang, Ting-Chi 

作者机构：Fuzhou Univ Fuzhou Fujian Peoples R China Northwestern Polytech Univ Xian Peoples R China Hsinchu NVIDIA Hsinchu Taiwan Natl Tsing Hua Univ Hsinchu Taiwan 

出 版 物：《ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS》 (ACM Trans. Design Autom. Electron. Syst.)

年 卷 期：2025年第30卷第2期

页      面：1-23页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Natural Science Foundation of China National Foreign Experts Program [H20240911] Natural Science Foundation of Fujian Province [2023J06017, 2024J01984] 

主　　题：Integer linear programming track assignment very large scale integra-tion timing delay routability parallelism 

摘      要：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 SPTA 2.0 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.