A new approach to the rectilinear Steiner tree problem

ABSTRACT

We discuss a new approach to constructing the rectilinear Steiner tree (RST) of a given set of points in the plane, starting from a minimum spanning tree (MST). The main idea in our approach is to determine L-shaped layouts for the edges of the MST, so as to maximize the overlaps between the layouts, thus minimizing the cost (i.e., wire length) of the resulting RST. We describe a linear time algorithm for constructing a RST from a MST, such that the RST is optimal under the restriction that the layout of each edge of the MST is an L-shape. The RST's produced by this algorithm have 8-33% lower cost than the MST, with the average cost improvement, over a large number of random point sets, being about 9%. The running time of the algorithm on an IBM 3090 processor is under 0.01 seconds for point sets with cardinality 10. We also discuss a property of RST's called stability under rerouting, and show how to stabilize the RST's derived from our approach. Stability is a desirable property in VLSI global routing applications.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft , Jeffrey Ullman , J. D. Ullman , J. E. Hopcroft, Data Structures and Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 2: M.A. Breuer, "Min-Cut Placement," Design Automation and Fault-Tolerant Computing, Vol. 1, 1977, pp 343-362.
• 3: A.E. Dunlop, and B. W. Kernighan, "A Procedure for Placement of Standard-Cell VLS1 Circuits," IEEE Transactions on Computer-Aided Design, Vol. CAD-4, 1985, pp 92-98.
• 4: M.R. Garey, and D. S. Johnson, "The Rectilinear Steiner Tree Problem is NP-complete," SIAM Journal of Applied Mathematics, Vol. 32, No. 4, 1977, pp 37-58.
• 5: F. K. Hwang, An O(n log n) Algorithm for Rectilinear Minimal Spanning Trees, Journal of the ACM (JACM), v.26 n.2, p.177-182, April 1979 [doi>10.1145/322123.322124]
• 6: F.K. l lwang, "An O(n log n) Algorithm for Suboptimal Rectilinear Steiner Trees," 1EEE Transactions on Circuits and Systems, Vol. CAS-26, No. 1, January 1979, pp 75-77.
• 7: F. K. I lwang, "On Steiner Minimal Trees with Rectilinear Distance," SIAM Journal of Applied Mathematics, Vol. 30, No. I, January 1976, pp 104-1 14.
• 8: D.T. Lee and C. K. Wong, "Voronoi Diagrams in LI, Lpo Metrics with 2-Dimensional Storage Applications, SlAM Journal of Computing, Vol. 9, No. 1, February 1980, pp 200-211.
• 9: J. It. Lee, N. K. Bose, F. K. ltwang, *Use of Steiner's problem in sub-optimal routing in rectilinear metric," I EEE Transactions on Circuits and Systems, Vol. CAS-23, July 1976, pp 470-476.
• 10: K-W. Lee, and C. Sechen, "A New Global Router for Row-Based Layout,* Proceedings of IEEE International Conference on Computer-Aided Design, Santa Clara, November 1988, pp 180-183.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Layout

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design