EDGE: Efficient DAG-based Global Routing Engine

Routing is one of the most time-consuming steps in the modern VLSI design flow. A well-designed global routing algorithm can effectively shrink the overall routing time and improve the quality of design after routing. Unlike many global routers that rely heavily on time-consuming path search algorithms like maze routing to resolve overflows, we propose to use directed acyclic graph (DAG) to explore the routing space more efficiently and create detours only when necessary. Experimental results on the ICCAD’19 benchmarks show that our algorithm improves the state-of-the-art quality of result by 1.4% and runs with a single thread faster than the fastest multi-threaded global router.