An O(nlogn) edge-based algorithm for obstacle-avoiding rectilinear steiner tree construction

ABSTRACT

Obstacle-avoiding Steiner tree construction is a fundamental problem in VLSI physical design. In this paper, we provide a new approach for rectilinear Steiner tree construction in the presence of obstacles. We propose a novel algorithm, which generates sparse obstacle-avoiding spanning graphs efficiently. We design a fast algorithm for the minimum terminal spanning tree construction, which is the bottleneck step of several existing approaches in terms of running time. We adopt an edge-based heuristic, which enables us to perform both local and global refinement, leading to Steiner trees with small lengths. The time complexity of our algorithm is O(nlogn). Hence, our technique is the most efficient one to the best of our knowledge. Experimental results on various benchmarks show that our algorithm achieves 25.8 times speedup on average, while the average length of the resulting obstacle-avoiding rectilinear Steiner trees is only 1.58% larger than the best existing solution

References

1. Borah, M., R. M. Owens, and M. J. Irwin, An Edge-Based Heuristic for Steiner Routing. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 1994. 13(12): p. 1563--1568.
2. Hannan, M., On Steiner's Problem with Rectilinear Distance. SIAM Journal on Applied Mathematics, 1966. 14: p. 255--265.
3. Zhou, H., Efficient Steiner Tree Construction Based on Spanning Graph. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 2004. 23(5): p. 704--710.
4. Garey, M. and D. Johnson, The Rectilinear Steiner Tree Problem is NP-Complete. SIAM Journal on Applied Mathematics, 1977. 32: p. 826--834.
5. Ganley, J. L. and J. P. Cohoon. Routing a Multi-Terminal Critical Net: Steiner Tree Construction in the Presence of Obstacles. in Int. Symp. on Circuits and Systems. 1994.
6. Yang, Y., et al. Rectilinear Steiner Minimal Tree among Obstacles. in Int. Conf. on ASIC. 2003.
7. Feng, Z., et al. An O(nlogn) Algorithm for Obstacle-Avoiding Routing Tree Construction in the Lambda-Geometry Plane. in Int. Symp. on Physical Design. 2006.
8. Shen, Z., C. Chu, and Y. Li. Efficient Rectilinear Steiner Tree Construction with Rectilinear Blockages. in Int. Conf. on Computer Design. 2005.
9. Lin, C., et al. Efficient Obstacle-Avoiding Rectilinear Steiner Tree Construction. in Int. Symp. on Physical Design. 2007.
10. Pan, M. and C. Chu. FastRoute: A Step to Integrate Global Routing into Placement. in Int. Conf. Computer Aided Design. 2006.
11. Cormen, T. H., et al., Introduction to Algorithms. 1989: MIT Press.

Index Terms

• Hardware

  • Electronic design automation

    • Physical design (EDA)

      • Placement

      • Wire routing