FastGR: Global Routing on CPU–GPU With Heterogeneous Task Graph Scheduler

Running time is a key metric across the standard physical design flow stages. However, with the rapid growth in design sizes, routing runtime has become the runtime bottleneck in the physical design flow. As a result, speeding routing becomes a critical and pressing task for IC design automation. Aside from the running time, we need to evaluate the quality of the global routing solution since a poor global routing engine degrades the solution performance after the entire routing stage. This work takes both of them into consideration. We propose a global routing framework with GPU-accelerated routing algorithms and a heterogeneous task graph scheduler, called FastGR, to accelerate the procedure of the modern global router and improve its effectiveness. Its runtime-oriented version <inline-formula> <tex-math notation="LaTeX">$\text {FastGR}^{\text {L}}$ </tex-math></inline-formula> achieves <inline-formula> <tex-math notation="LaTeX">$2.489\times $ </tex-math></inline-formula> speedup compared with the state-of-the-art global router. Furthermore, the GPU-accelerated L-shape pattern routing algorithm used in <inline-formula> <tex-math notation="LaTeX">$\text {FastGR}^{\text {L}}$ </tex-math></inline-formula> can contribute to <inline-formula> <tex-math notation="LaTeX">$9.324\times $ </tex-math></inline-formula> speedup over the sequential algorithm on CPU. Its quality-oriented version <inline-formula> <tex-math notation="LaTeX">$\text {FastGR}^{\text {H}}$ </tex-math></inline-formula> offers a 27.855% improvement of the number of shorts over the runtime-oriented version and still gets <inline-formula> <tex-math notation="LaTeX">$1.970\times $ </tex-math></inline-formula> faster than the most advanced global router.