00000cab a22000003a 4500 UP-99796217609500600 Buklod 20231007234342.0 m |o d | ta 101013s xx d | ||r ||||| || DENGII eng Jiang Hu A timing-constrained simultaneous global routing algorithm. pp. 1025-1036 Proposed in this paper is a new approach for VLSI interconnect global routing that can optimize both congestion and delay, which are often competing objectives. The authors' approach provides a general framework that may use any single-net routing algorithm and any delay model in global routing. It is based on the observation that there are several routing topology flexibilities that can be exploited for congestion reduction under timing constraints. These flexibilities are expressed through the concepts of a soft edge and a slideable Steiner node. Starting with an initial solution where timing-driven routing is performed on each net without regard to congestion constraints, this algorithm hierarchically bisects a routing region and assigns soft edges to the cell boundaries along the bisector line. The assignment is achieved through a network flow formulation so that the amount of timing slack used to reduce congestions; is adaptive to the congestion distributions. Finally, a timing-constrained rip-up-and-reroute process is performed to alleviate the residual congestions. Experimental results on benchmark circuits are quite promising and the run time is between 0.02 s and 0.15 s per two-pin net 0.02 to 0.15 s. VLSI. Benchmark circuits. Bisector line. Cell boundaries. Congestion. Delay. Interconnect global routing. Network flow formulation. Rip-up-and-reroute process. Routing region. Single-net routing algorithm. Slideable Steiner node. Soft edge. Timing constraints. Timing slack. IEEE Transactions on computer-aided design of integrated circuits and systems 21, 9 (2002). FO Article