Graph Steiner Minimal Tree Construction And Its Routing Applications

With the rapid development of the integrated circuit manufacturing process technology and the decrease of the feature size of VLSI, the interconnect structure becomes more complex. Interconnect RC delay mainly leads to the chip delay, thus greatly influences the performance of the chip. The traditional Manhattan interconnect structure is limited to horizontal or vertical routing directions so that it fails to make full use of all routing resources and further optimize the interconnect RC delay. Hence, some new non-orthogonal interconnect structures are proposed, especially X interconnect structure attracts a wide range of research interest because of its wire length reduction potential.Our study mainly focuses on the fast heuristic routing algorithms of X interconnect structure. Because the practical chip routing problem can be very complex, we simplify the X-routing problem to the computational geometry problem of constructing obstacle-avoiding octilinear Steiner minimal tree (OAOSMT). By studying the related research achievements, we propose a new heuristic algorithm to solve the graph Steiner minimal tree problem (GSMT). Then we use this method and several simple geometric transformations to fulfill the construction of OAOSMT.We propose a new heuristic algorithm with four steps to solve the classic GSMT problem. Firstly, the original input graph is decomposed into several connected sub-graphs and we simplify them to reduce the scale of problem. Then for each connected sub-graph, Steiner tree is constructed by the three source shortest path extending method. We use the Steiner point insertion and edge conversion operations to further optimize these Steiner trees. Finally, we merge these Steiner trees to get the complete Steiner minimal tree of the original input graph. Experimental results show that our new heuristic algorithm can obtain better Steiner tree, compared to the traditional GSMT heuristic algorithms. Compared with the optimal Steiner tree, our method can obtain approximate optimal Steiner tree with less than 1% error for 67% of the test cases.We apply this GSMT algorithm to the routing problem of X interconnect structure and propose a new heuristic algorithm to construct obstacle-avoiding octilinearSteiner minimal tree (OAOSMT). Firstly, we introduced the concept of the improved Escape graph. Then we convert the obstacle-avoiding rectilinear Steiner minimal tree problem (OARSMT) to the GSMT of the improved Escape graph and solve it. Finally, we propose five geometric transformations to construct OAOSMT from OARSMT. Experimental results show that our method to construct OAOSMT can reduce total wire length by 8%-17%, compared with the wire length of OARSMT. It shows the potential of X interconnect structure on wire length reduction.