A New Technique Using Tunnel Shape Information to Improve Path Search in Detailed Routing

摘要

One approach to solve detailed routing is net-by-net using a fast A*-based path search algorithm to handle long connections. The path search is restricted to certain areas imposed by the global router, which we call tunnels. Since a tunnel forces the path to follow its shape, a tunnel with many detours produces a path whose cost is far higher than the distance. This makes the path search algorithm to suffer heavy performance penalties. Thus, this work proposes new methods to preprocess the tunnels and use the gathered information during the search, providing a more realistic lower bound for the heuristic function of the path search algorithm. The experiments compared Hetzel's algorithm [1] using distance and our method. The results showed a time improvement of 64% in average.