Jin-Tai Yan
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.
- 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.Google Scholar
Digital Library
- 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.Google Scholar
- Chiang, C., SU, Q., and Chiang, C. S. 2003. Wirelength reduction by using diagonal wire. In Proceedings of the 13th IEEE Great Lakes Symposium on VLSI. 104--107. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Coulston, C. 2003. Constructing exact octagonal Steiner minimal trees. In Proceedings of the 13th IEEE Great Lakes Symposium on VLSI. 1--6. Google ScholarDigital Library
- Garey, M. and Johnson, D. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 826--834.Google Scholar
- Hong, X., Xue, T., Kuh, E. S., Cheng, C. K., and Huang, J. 1993. Performance-driven Steiner tree algorithm for global routing. In Proceedings of the 30th ACM/IEEE Design Automation Conference. 177--181. Google ScholarDigital Library
- Hou, H., Hu, J., and Sapatnekar, S. S. 1999. Non-Hanan routing. IEEE Trans. Comput.-Aided. Des. Integr. Circ. Syst. 18, 436--444. Google ScholarDigital Library
- Hu, J. and Sapatnekar, S. S. 2000. A timing-constrained algorithm for simultaneous global routing of multiple nets. In Proceedings of the IEEE International Conference on Computer-Aided Design. 99--103. Google ScholarDigital Library
- Kahng, A. B., Mandoiu, I. I., and Zelikovsky, A. 2003. Highly scalable algorithms for rectilinear and octilinear Steiner trees. In Proceedings of the IEEE Asia and South Pacific Design Automation Conference. 827--833. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- Teig, S. 2002. The X-architecture: not your father's diagonal wiring. In Proceedings of the International Workshop on System-Level Interconnect Prediction. 33--37. Google ScholarDigital Library
- 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.Google Scholar
- Yan, J. T. and Lin, S. H. 2004. Timing-constrained congestion-driven global routing. In Proceedings of the IEEE Asia and South Pacific Design Automation Conference. 683--686. Google ScholarDigital Library
- Zhu, Q., Zhou, H., Jing, T., Hong, X. L., and Yang, Y. 2004. Efficient octilinear Steiner tree construction based on spanning graphs. In Proceedings of the IEEE Asia and South Pacific Design Automation Conference. 687--690. Google ScholarDigital Library
Index Terms
- Timing-driven octilinear Steiner tree construction based on Steiner-point reassignment and path reconstruction
Recommendations
A Timing Driven Congestion Aware Global Router
EAIT '11: Proceedings of the 2011 Second International Conference on Emerging Applications of Information TechnologyThe multi-net Global Routing Problem (GRP) is a problem of routing a set of nets subject to resources and delay constraints. Many modern routers use FLUTE (Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design) as the basic ...
Obstacle-avoiding rectilinear Steiner tree construction
ICCAD '08: Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided DesignIn today's VLSI designs, there can be many blockages in a routing region. The obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) problem has become an important problem in the physical design stage of VLSI circuits. This problem has attracted a ...
Delay bounded buffered tree construction for timing driven floorplanning
ICCAD '97: Proceedings of the 1997 IEEE/ACM international conference on Computer-aided designAs devices and lines shrink into the deep submicron range, the propagation delay of signals can be effectively improved by repowering the signals using intermediate buffers placed within the routing trees. Almost no existing timing driven floorplanning ...
Comments