Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design

ABSTRACT

In this paper, we present a very fast and accurate rectilinear Steiner minimal tree (RSMT) algorithm called FLUTE. The algorithm is an extension of the wirelength estimation approach by fast lookup table [1]. The main contribution of this paper is a new net breaking technique which is much better than the one in [1]. A scheme is also presented to allow users to control the tradeoff between accuracy and runtime.FLUTE is optimal for nets up to degree 9 and is still very accurate for nets up to degree 100. So it is particularly suitable for VLSI applications in which most nets have a degree 30 or less. We show experimentally that over 18 industrial circuits in the ISPD98 benchmark suite, FLUTE with default accuracy is more accurate than the Batched 1-Steiner heuristic and is almost as fast as a very efficient implementation of Prim's rectilinear minimum spanning tree (RMST) algorithm. By adjusting the accuracy parameter, the error can be further reduced with only a small increase in runtime (e.g., 2.7x error reduction with 2.2x runtime increase).

REFERENCES

• 1: C. Chu, FLUTE: fast lookup table based wirelength estimation technique, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.696-701, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382665]
• 2: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 3: F. K. Hwang. On Steiner minimal trees with rectilinear distance. SIAM Journal of Applied Mathematics, 30:104--114, 1976.
• 4: F. K. Hwang, D. S. Richards, and P. Winter. The Steiner tree problem. Annals of Discrete Mathematics, 1992. Elsevier Science Publishers.
• 5: D. M. Warme, P. Winter, and M. Zachariasen. Exact algorithms for plane Steiner tree problems: A computational study. In D.Z. Du, J.M. Smith, and J.H. Rubinstein, editors, Advances in Steiner Trees, pages 81--116. Kluwer Academic Publishers, 2000.
• 6: GeoSteiner -- software for computing Steiner trees. http://www.diku.dk/geosteiner/.
• 7: J. Griffith, G. Robins, J. S. Salowe, and T. Zhang. Closing the gap: Near-optimal Steiner trees in polynomial time. IEEE Trans. Computer-Aided Design, 13(11):1351--1365, November 1994.
• 8: Ion I. Măndoiu , Vijay V. Vazirani , Joseph L. Ganley, A new heuristic for rectilinear Steiner trees, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.157-162, November 07-11, 1999, San Jose, California, United States
• 9: M. Borah, R. M. Owens, and M. J. Irwin. An edge-based heuristic for Steiner routing. 13(12):1563--1568, December 1994.
• 10: Hai Zhou, Efficient Steiner tree construction based on spanning graphs, Proceedings of the 2003 international symposium on Physical design, April 06-09, 2003, Monterey, CA, USA [doi>10.1145/640000.640034]
• 11: Hai Zhou , Narendra Shenoy , William Nicholls, Efficient minimum spanning tree construction without Delaunay triangulation, Information Processing Letters, v.81 n.5, p.271-276, 2002 [doi>10.1016/S0020-0190(01)00232-0]
• 12: J. Soukup. Circuit layout. Proceedings of IEEE, 69:1281--1304, October 1981.
• 13: Hongyu Chen , Changge Qiao , Feng Zhou , Chung-Kuan Cheng, Refined single trunk tree: a rectilinear steiner tree generator for interconnect prediction, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505366]
• 14: Charles J. Alpert, The ISPD98 circuit benchmark suite, Proceedings of the 1998 international symposium on Physical design, p.80-85, April 06-08, 1998, Monterey, California, United States [doi>10.1145/274535.274546]
• 15: Andrew B. Kahng and Ion Mandoiu. RMST-Pack: Rectilinear minimum spanning tree algorithms. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/RMST/.
• 16: M. Hanan. On Steiner's problem with rectilinear distance. SIAM Journal of Applied Mathematics, 14:255--265, 1966.
• 17: Chris Chu. FLUTE: Fast lookup table based technique for RSMT construction and wirelength estimation. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/.
• 18: A. E. Caldwell, A. B. Kahng, and I. L. Markov. VLSI CAD Bookshelf. http://www.gigascale.org/bookshelf/.
• 19: Natarajan Viswanathan , Chris Chong-Nuen Chu, FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model, Proceedings of the 2004 international symposium on Physical design, April 18-21, 2004, Phoenix, Arizona, USA [doi>10.1145/981066.981072]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

General Terms:
Algorithms, Design, Performance

Keywords:
rectilinear steiner minimal tree algorithm, routing, wirelength estimation