Efficient multilayer routing based on obstacle-avoiding preferred direction Steiner tree

In IC design, rectilinear Steiner trees have been used to route signal nets by global and detail routers for a long time. Recently, there are more complicated processing conditions for routing to be considered, such as multiple routing layers, obstacles, and preferred directions. Furthermore, routability is also an important issue for modern routing which handles more than ten thousand signal nets. As a result, how to meet the processing conditions and consider the routability at the same time is becoming important. In this paper, we formulate a routing problem, called the obstacle-avoiding preferred direction Steiner tree (OAPDST) problem, which can deal with more practical processing conditions and achieve acceptable routability. To the best of our knowledge, this is the first attempt to formulate this problem. Then, we propose a routing graph, called preferred direction evading graph (PDEG), for this problem, and prove that at least one optimal solution can be found on PDEG. As a result, by using PDEG as the solution space, more efficient and effective methods can be found for the OAPDST problem. Based on PDEG, we also construct an approximation algorithm for the OAPDST problem to provide stable and effective solutions. Experimental results show that our method can perform well for the OAPDST problem.