OASALT: On the Construction of Obstacle-Avoiding Steiner shAllow-Light Tree

In routing tree generation, two important metrics are introduced to evaluate the quality. Wirelength (WL) is directly related to power consumption, routing resource usage and wire delay while pathlength (PL) is indicative of the wire delay. SALT [1] and PD-II [2] are the leading algorithms for the construction of shallow-light routing trees. However, they cannot handle the real designs with blockages. In this paper, we extended the SALT to be Obstacle-Avoiding Steiner shAllow-Light Tree (OASALT) to handle obstacles. First, we improve the time complexity of Lin’s [3] Obstacle-Avoiding Spanning Graph (OASG) from O(n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>logn) to O(n<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>). In addition, we extended the CL [4] algorithm to generate Obstacle-Avoiding Rectilinear Steiner Minimum Arborescence (OARSMA). The experiment shows that OASALT can achieve a better tradeoff between WL and PL under the cases with obstacles, by combining Obstacle-Avoiding Rectilinear Steiner Minimum Tree (OARSMT) and OARSMA. Compared to performance-driven Obstacle-Avoiding Rectilinear Steiner Tree (PDOARST) [5], OASALT improves the worst delay by 15% and WL by 10% on average.