Timing-driven Steiner trees are (practically) free

ABSTRACT

Traditionally, rectilinear Steiner minimum trees (RSMT) are widely used for routing estimation in design optimizations like floorplanning and physical synthesis. Since it optimizes wirelength, an RSMT may take a "non-direct" route to a sink, which may give the designer an unnecessarily pessimistic view of the delay to the sink.Previous works have addressed this issue through performance-driven constructions, minimum Steiner arborescence, and critical sink based Steiner constructions. Physical synthesis and routing flows have been reticent to adapt universal timing-driven Steiner constructions out of fear that they are too expensive (in terms of routing resource and capacitance). This paper studies several different performance-driven Steiner tree constructions in order to show which ones have superior performance.A key result is that they add at most 2%-4% extra capacitance, and are thus a promising avenue for today's increasingly aggressive performance-driven P&R flows.We demonstrate using a production P&R flow that timing-driven Steiner topologies can be easily embedded into an incremental routing subflow to obtain significantly improved timing (3.6% and 5.1% improvements in cycle time for two industry testcases) at practically no cost of wirelength or routability.

REFERENCES

• 1: Personal communication with Dr. Weiping Shi.
• 2: C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, and D. Karger. Prim-dijkstra tradeoffs for improved performance-driven routing tree design. IEEE TCAD, 14(7):890--896, July 1995.
• 3: K. D. Boese, A. B. Kahng, B. A. McCoy, and G. Robins. Near-optimal critical sink routing tree constructions. IEEE TCAD, 14(12):1417--36, Dec. 1995.
• 4: M. Borah, R. M. Owens, and M. J. Irwin. An edge-based heuristic for Steiner routing. IEEE TCAD, 13(12):1563--1568, Dec. 1994.
• 5: Manjit Borah , Robert Michael Owens , Mary Jane Irwin, A fast and simple Steiner routing heuristic, Discrete Applied Mathematics, v.90 n.1-3, p.51-67, Jan. 15, 1999 [doi>10.1016/S0166-218X(98)00085-7]
• 6: Chris Chu , Yiu-Chung Wong, Fast and accurate rectilinear steiner minimal tree algorithm for VLSI design, Proceedings of the 2005 international symposium on Physical design, April 03-06, 2005, San Francisco, California, USA [doi>10.1145/1055137.1055145]
• 7: J. Cong, A. B. Kahng, and K.-S. Leung. Efficient algorithms for the minimum shortest path Steiner arborescence problem with applications to vlsi physical design. IEEE TCAD, 17(1):24--39, Jan. 1999.
• 8: J. Cong, A. B. Kahng, G. Robins, M. Sarrafzadeh, and C. K. Wong. Provably good performance-driven global routing. IEEE TCAD, 11(6):739--752, June 1992.
• 9: J. Cordova and Y. H. Lee. A heuristic algorithm for the rectilinear Steiner arborescence problem. Tech. Report, CIS Department, Univ. of Florida, (TR 94-025), 1994.
• 10: J. Griffith, G. Robins, J. Salowe, and T. Zhang. Closing the gap: Near-optimal Steiner trees in polynomial time. IEEE TCAD, 13:1351--1365.
• 11: A. B. Kahng and G.Robins. On optimal interconnections for VLSI. Kluwer Academic Publishers, Boston, MA, 1995.
• 12: Samir Khuller , Balaji Raghavachari , Neal Young, Balancing minimum spanning and shortest path trees, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.243-250, January 25-27, 1993, Austin, Texas, United States
• 13: Guy Kortsarz , David Peleg, Approximating shallow-light trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.103-110, January 05-07, 1997, New Orleans, Louisiana, United States
• 14: P. Madden. BOI source code. http://vlsicad.ucsd.edu/GSRC/bookshelf/Slots/RSMT/ Madden_BOI.html.
• 15: Madhav V. Marathe , R. Ravi , R. Sundaram , S. S. Ravi , Daniel J. Rosenkrantz , Harry B. Hunt, III, Bicriteria Network Design Problems, Proceedings of the 22nd International Colloquium on Automata, Languages and Programming, p.487-498, July 10-14, 1995
• 16: J. Naor , B. Schieber, Improved approximations for shallow-light spanning trees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.536, October 19-22, 1997
• 17: Sven Peyer , Martin Zachariasen , David Grove Jørgensen, Delay-related secondary objectives for rectilinear Steiner minimum trees, Discrete Applied Mathematics, v.136 n.2-3, p.271-298, 15 February 2004 [doi>10.1016/S0166-218X(03)00445-1]
• 18: Wangqi Qiu , Weiping Shi, Minimum moment Steiner trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 19: S. K. Rao, P. Sadayappan, F. K. Hwang, and P. W. Shor. The rectilinear Steiner arborescence problem. Algorithmica, 7:277--288, 1992.
• 20: J. Soukup. Uniform steiner tree representation from the floor planning to the final routing. Unpublished manuscript.
• 21: D. M. Warme, P. Winter, and M. Zachariesen. Exact algorithms for plane Steiner tree problems: A computational study. pp. 81--116, 2000.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Design, Performance

Keywords:
arborescence, rectilinear Steiner tree, timing-driven