GAMER: GPU-Accelerated Maze Routing

Maze routing is usually the most time-consuming step in global routing and detailed routing. A commonly used maze routing method is to start from one pin and iteratively connect the current route to the closest unconnected pin. This method reduces the maze routing problem to multiple multisource-multidestination shortest path problems. The shortest path problem in VLSI routing has: 1) rectilinear routing directions and 2) preferably small via usage. By utilizing these two characteristics, we propose a novel parallel algorithm called GAMER to accelerate the multisource-multidestination shortest path problem for VLSI routing. GAMER decomposes the shortest path search into alternating vertical and horizontal sweep operations, and two parallel algorithms are proposed to accelerate a sweep operation from O(n2) to O(log2n) on a grid graph of n×n. Several techniques of applying GAMER on irregular routing regions are also introduced. Experiments are conducted by integrating GAMER into the state-of-the-art academic global router CUGR. CUGR adopts a two-level maze routing scheme, including coarse-grained routing and fine-grained routing, and they can be accelerated by 19.85× and 2.59×, respectively, with GAMER, achieving an overall speedup of 2.7× without quality degradation.