An Improved Heuristic Function for A∗-Based Path Search in Detailed Routing
Stèphano M. M. Gonçalves, Leomar Soares da Rosa Júnior, Felipe de Souza Marques · 2019
One approach to solve detailed routing is net-by-net using a fast A∗-based path search algorithm to handle long connections. Such path search algorithms usually rely on the manhattan distance to implement their heuristic function, providing a poor lower bound since the search is constrained by the global routing guide. This work proposes a new technique to provide a more realistic lower bound in this scenario. We precompute some lower bounds before the path search by applying a modified version of Dijkstra's algorithm on tunnels (sections of the global routing guide). This information is used during the search, reducing the runtime by 58% in average, in comparison to the classic manhattan distance, on ISPD 2018 benchmarks. We also show an improvement of our technique over existing work [10]. Our preprocessing method runtime is negligible, maximizing the benefit of using the improved heuristic function during the path search.