Timing-driven octilinear Steiner tree construction based on Steiner-point reassignment and path reconstruction

ABSTRACT

It is well known that the problem of constructing a timing-driven rectilinear Steiner tree for any signal net is important in performance-driven designs and has been extensively studied. Until now, many efficient approaches have been proposed for the construction of a timing-driven rectilinear Steiner tree. As technology process advances, +45° and −45° diagonal segments can be permitted in an octilinear routing model. To our knowledge, no approach is proposed to construct a timing-driven octilinear Steiner tree for any signal net. In this paper, given a rectilinear Steiner tree for any signal net, we propose an efficient transformation-based approach to construct a timing-driven octilinear Steiner tree based on the computation of the octilinear distance and the concept of Steiner-point reassignment and path reconstruction in an octilinear routing model. The experimental results show that our proposed transformation-based approach can use reasonable CPU time to construct a TOST, and a 10%--18% improvement in timing delay and a 5%--14% improvement in total wire length in the original RSTs are obtained in the construction of TOSTs for the tested signal nets.

REFERENCES

• 1: Chiang, C., Wong, C. K., and Sarrafzaeh, M. 1994. A weighted Steiner trees-based global router with simultaneous length and density minimization. IEEE Trans. Comput.-Aided. Des. Integr. Circ. Syst. 13, 1461--1469.
• 2: Chiang, C. and Chiang, C. S. 2002. Octilinear Steiner tree construction. In Proceedings of the 45th IEEE Midwest Symposium on Circuits and Systems. 211--216.
• 3: Charles Chiang , Qing Su , Ching-Shoei Chiang, Wirelength reduction by using diagonal wire, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764836]
• 4: Cong, J., Kahng, A. B., Robins, G., Sarrafzaeh, M., and Wong, C. K. 1992. Provably good performance-driven global routing. IEEE Trans. Comput.-Aided. Des. Integr. Circ. Syst. 11, 739--752.
• 5: Chris S. Coulston, Constructing exact octagonal steiner minimal trees, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764810]
• 6: Garey, M. and Johnson, D. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 826--834.
• 7: Xianlong Hong , Tianxiong Xue , Ernest S. Kuh , Chung-Kuan Cheng , Jin Huang, Performance-driven Steiner tree algorithm for global routing, Proceedings of the 30th international conference on Design automation, p.177-181, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164658]
• 8: Hou, H., Hu, J., and Sapatnekar, S. S. 1999. Non-Hanan routing. IEEE Trans. Comput.-Aided. Des. Integr. Circ. Syst. 18, 436--444.
• 9: Jiang Hu , Sachin S. Sapatnekar, A timing-constrained algorithm for simultaneous global routing of multiple nets, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 10: Andrew B. Kahng , Ion I. Măndoiu , Alexander Z. Zelikovsky, Highly scalable algorithms for rectilinear and octilinear Steiner trees, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119955]
• 11: Sarrafzaeh, M. and Wong, C. K. 1992. Hierarchical Steiner tree construction in uniform orientations. IEEE Trans. Comput.-Aided Des. Integr. Circ. Syst. 11, 1095--1103.
• 12: Steven L. Teig, The X architecture: not your father's diagonal wiring, Proceedings of the 2002 international workshop on System-level interconnect prediction, April 06-07, 2002, San Diego, California, USA [doi>10.1145/505348.505355]
• 13: Yan, J. T., Wang, T. Y., and Lee, Y. C. 2005. Timing-driven Steiner tree construction based on feasible assignment of hidden Steiner points. In Proceedings of the IEEE International Symposium on Circuits and Systems. 1370--1373.
• 14: Jin-Tai Yan , Shun-Hua Lin, Timing-constrained congestion-driven global routing, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan
• 15: Qi Zhu , Hai Zhou , Tong Jing , Xianlong Hong , Yang Yang, Efficient octilinear Steiner tree construction based on spanning graphs, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, January 27-30, 2004, Yokohama, Japan

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Verification

General Terms:
Algorithms, Verification

Keywords:
Elmore delay, Global routing, Steiner points, octilinear Steiner tree