A Global Routing Algorithm Based on Multistage Rip-up and Reroute

Global routing is a crucial step in very large scale integration(VLSI) physical design, which will affect routability, wirelength and the number of vias of a chip. In this paper, a multistage rip-up and reroute based global routing algorithm is presented to reduce the probability of getting stuck in local optima of traditional rip-up and reroute routing algorithms. In each rip-up and reroute stage, the proposed method focuses on different aspects of overflow minimization and wirelength minimization. It constructs different cost functions, determines different orderings for rip-up and reroute, and selects different routing models and algorithms to rip-up and reroute the marked nets. Using the strategies above, the multistage rip-up and reroute based global routing algorithm can escape local optima effectively, and improve routing quality and speed. Experimental results on ISPD 2008 global routing contest benchmarks show that the proposed global routing algorithm can obtain less total overflow than those of NTUgr, NTHU-Route2.0 and NCTU-GR2.0 by 1.4%, 2.4% and 21.5%, respectively; and runs 10.4 times, 1.6 times and 1.3 times faster than NTUgr, NTHU-Route2.0 and NCTU-GR2.0, respectively.