FH-OAOS: A Fast Four-Step Heuristic for Obstacle-Avoiding Octilinear Steiner Tree Construction

With the sharp increase of very large-scale integrated (VLSI) circuit density, we are faced with many knotty issues. Particularly in the routing phase of VLSI physical design, the interconnection effects directly relate to the final performance of circuits. However, the optimization capability of traditional rectilinear architecture is limited; thus, both academia and industry have been devoted to nonrectilinear architecture in recent years, especially octilinear architecture, which is the most promising because it can greatly improve the performance of modern chips. In this article, we design FH-OAOS, an obstacle-avoiding algorithm in octilinear architecture, by constructing an obstacle-avoiding the octilinear Steiner minimal tree (OAOSMT). Our approach first constructs an obstacle-free Euclidean minimal spanning tree (OFEMST) on the given pins based on Delaunay triangulation (DT). Then, two lookup tables about OFEMST's edge are generated, which can be seen as the information center of FH-OAOS and can provide information support for algorithm operation. Next, an efficient obstacle-avoiding strategy is proposed to convert the OFEMST into an obstacle-avoiding octilinear Steiner tree (OAOST). Finally, the generated OAOST is refined to construct the final OAOSMT by applying three effective strategies. Experimental results on various benchmarks show that FH-OAOS achieves 66.39 times speedup on average, while the average wirelength of the final OAOSMT is only 0.36% larger than the best existing solution.