A construction of minimal delay Steiner tree using two-pole delay model

ABSTRACT

In this paper, we will study the construction of a Steiner routing tree for a given net with the objective of minimizing the delay of the routing tree. Previous researches adopt Elmore delay model to compute delay. However, with the advancement of IC technology, a more accurate delay model is required. Therefore, in this paper, we will use two-pole delay model to compute the cost function of a Steiner tree. Moreover, we propose a new algorithm to construct the Steiner tree. Our algorithm takes into consideration the net topology, the total wire length and the longest path from the source to sink. Experimental results show that our algorithm is very effective and efficient as compared to [8].

REFERENCES

• 1: A. E. Dunlop , V. D. Agrawal , D. N. Deutsch , M. F. Jukl , P. Kozak , M. Wiesel, Chip layout optimization using critical path weighting, Proceedings of the 21st conference on Design automation, p.133-136, June 25-27, 1984, Albuquerque, New Mexico, United States
• 2: J. Cong, A. Kahng, G. Robins, M. Sarrafzadeh, C. K. Wong, "Provably Good Performance-Driven Global Routing", IEEE Trans. CAD , vol. 11, no. 6, pp. 739-752, 1992.
• 3: 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
• 4: M. J. Alexander, G. Robins, "New Performance-Driven FPGA Routing Algorithm", ACM/IEEE Design Automation Conf. , pp. 652-657, 1994.
• 5: C. J. Alpert, T. C. Hu, J. H. Huang, A. B. Kahng, D. Karger, "Prim-Dijkstra Tradeoffs for Improved Performance-Driven Routing Tree Design", IEEE Trans. CAD , vol. 14, no. 7, pp. 890-896, 1995.
• 6: H. Mitsubayashi, A. Takahashi, Y. Kajitani, "Cost-Radius Balanced Spanning/Steiner Tree", IEEE Asia Pacific Conference on Circuits and Systems , pp. 377-380, 1996.
• 7: J. Oh, I. Pyo, M. Pedrame, "Constructing Minimal Spanning Trees with Lower and Upper Bounded Path Delays," ISCAS'96 , vol. 4, pp. 416-419, 1996.
• 8: K. D. Boese, A. B. Kahng, B. A. McCoy, G. Robins, "Near- Optimal Critical Sink Routing Tree Constructions", IEEE Trans. CAD , vol. 14, no. 12, pp. 1417-1436, 1995.
• 9: Kenneth D. Boese , Andrew B. Kahng , Bernard A. McCoy , Gabriel Robins, Rectilinear Steiner trees with minimum Elmore delay, Proceedings of the 31st annual conference on Design automation, p.381-386, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196428]
• 10: W. C. Elmore, "The Transient Response of Damped Linear Networks with Particular Regard to Wideband Amplifiers", Journal of Applied Physics 19 , pp. 55-63, 1948.
• 11: A. B. Kahng, S. Muddu, "Two-pole Analysis of Interconnection Trees", IEEE MCMC Conf., pp.105-110, 1995.
• 12: A. B. Kahng, S. Muddu, "An Analytical Delay ModelforRLC Interconnections", ISCAS'96, vol. 4, pp. 237-240, 1996
• 13: Jun-Dong Cho , Majid Sarrafzadeh , Mysore Sriram , Sung-Mo Kang, High-Performance MCM Routing, IEEE Design & Test, v.10 n.4, p.27-37, October 1993 [doi>10.1109/54.245961]
• 14: Andrew B. Kahng , Kei Masuko , Sudhakar Muddu, Delay Models for MCM Interconnects when Response is Non-Monotone, Proceedings of the 1997 Conference on IEEE Multi-Chip Module Conference, p.102, February 04-05, 1997
• 15: Youxin Gao, D. F. Wong, "Wire-Sizing Optimization with Induztance Consideration Using Transmission-Line Model", IEEE Trans. CAD, vol. 18, no. 12, pp. 1759-1767, 1999.
• 16: M. Hanan, "On Steiner's Problem with Rectilinear Distance", SIAM J. Appl. Math., vol. 14, pp. 255-265, 1996.
• 17: H. Hou, J. Hu, S. S. Sapatnekar, "Non-Hanan Routing", IEEE Trans. CAD, vol. 18, no. 4, pp. 436-444, 1999.
• 18: A. B. Kahng, G. Robins, "On Optimal Interconnections for VLSI", Kluwer Academic Publishers, Boston, MA, 1995.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
  B.8 Performance and Reliability

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Electronics

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory