Fast Obstacle-Avoiding Octilinear Steiner Minimal Tree Construction Algorithm for VLSI Design

Xing Huang,  Wenzhong Guo,  Guolong Chen
Fuzhou university


With advance in manufacturing technology, 45ºand 135º diagonal segments can be permitted in an octilinear routing model. In this article, we present the first heuristic algorithm to solve obstacle-avoiding octilinear Steiner minimal tree (OAOSMT) construction problem. We first constructs an obstacle-free Euclidean minimal spanning tree (OFEMST). Then two lookup tables about OFEMST are generated, which can provide fast information inquire for subsequent steps. Next, an obstacle-avoiding strategy is proposed to convert OFEMST into an obstacle-avoiding octilinear Steiner tree (OAOST). Finally, we design an excellent refinement technique, which can further reduce the wirelengh. Multiple sets of standard test cases have been tested in C language. Experimental results show that the proposed algorithm achieves the best results in terms of both wirelengh and runtime. It is extremely practical and useful in the process of VLSI routing.