DpRouter: A fast and accurate dynamic-pattern-based global routing algorithm

Abstract

This paper presents a fast and accurate global routing algorithm, DpRouter, based on two efficient techniques: (1) dynamic pattern routing (Dpr), and (2) segment movement. These two techniques enable DpRouter to explore large solution space to achieve better routability with low time complexity. Compared with the state-of-the-arts, experimental results show that we consistently obtain better routing quality in terms of both congestion and wire length, while simultaneously achieving a more than 30× runtime speedup. We envision that this algorithm can be further leveraged in other routing applications, such as FPGA routing. ©2007 IEEE.