Obstacle-avoiding rectilinear Steiner tree construction in sequential and parallel approach

• A new router is developed to solve obstacle-avoiding RSMT problem.
• A multi-pin based maze routing method is developed to handle the routing of the multi-pin nets.
• A simplified Hanan grid with a heap data structure is applied to reduce the problem complexity.
• Parallel algorithm is applied to speed up the runtime to solve the problem; it is the first work to apply parallel algorithm on this problem.

The Rectilinear Steiner Minimum Tree (RSMT) problem is a fundamental one in VLSI physical design. In this paper, we present a maze routing based heuristics to solve the obstacle-avoiding RSMT (OARSMT) problem. Our approach can handle multi-pin nets in good quality and reasonable running time. We also present an implementation of the heuristics in parallel approach with the aid of graphic processing units (GPU). The parallel algorithm is implemented by using CUDA and has been tested on a NVIDIA graphic card. Our experimental results show that our parallel algorithm has promising speedups over our sequential approach. This work demonstrates that we can apply a parallel algorithm to solve the OARSMT problem with the aid of GPU.