skip to main content
research-article

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

Published: 23 April 2008 Publication History

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]
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.
[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]
Coulston, C. 2003. Constructing exact octagonal Steiner minimal trees. In Proceedings of the 13th IEEE Great Lakes Symposium on VLSI. 1--6.
[6]
Garey, M. and Johnson, D. 1977. The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math., 826--834.
[7]
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.
[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]
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.
[10]
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.
[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]
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.
[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]
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.
[15]
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.

Cited By

View all
  • (2022)Two-Stage Competitive Particle Swarm Optimization Based Timing-Driven X-Routing for IC Design Under Smart ManufacturingACM Transactions on Management Information Systems10.1145/353132813:4(1-26)Online publication date: 22-Apr-2022
  • (2022)Performance-Driven X-Architecture Routing Algorithm for Artificial Intelligence Chip Design in Smart ManufacturingACM Transactions on Management Information Systems10.1145/351942213:4(1-20)Online publication date: 24-Mar-2022
  • (2022)Social learning discrete Particle Swarm Optimization based two-stage X-routing for IC design under Intelligent Edge Computing architectureApplied Soft Computing10.1016/j.asoc.2021.107215104:COnline publication date: 22-Apr-2022
  • Show More Cited By

Index Terms

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

        Recommendations

        Comments

        Information & Contributors

        Information

        Published In

        cover image ACM Transactions on Design Automation of Electronic Systems
        ACM Transactions on Design Automation of Electronic Systems  Volume 13, Issue 2
        April 2008
        272 pages
        ISSN:1084-4309
        EISSN:1557-7309
        DOI:10.1145/1344418
        Issue’s Table of Contents
        Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

        Publisher

        Association for Computing Machinery

        New York, NY, United States

        Journal Family

        Publication History

        Published: 23 April 2008
        Accepted: 01 October 2007
        Revised: 01 February 2007
        Received: 01 July 2006
        Published in TODAES Volume 13, Issue 2

        Permissions

        Request permissions for this article.

        Check for updates

        Author Tags

        1. Elmore delay
        2. Global routing
        3. Steiner points
        4. octilinear Steiner tree

        Qualifiers

        • Research-article
        • Research
        • Refereed

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)6
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 15 Feb 2025

        Other Metrics

        Citations

        Cited By

        View all
        • (2022)Two-Stage Competitive Particle Swarm Optimization Based Timing-Driven X-Routing for IC Design Under Smart ManufacturingACM Transactions on Management Information Systems10.1145/353132813:4(1-26)Online publication date: 22-Apr-2022
        • (2022)Performance-Driven X-Architecture Routing Algorithm for Artificial Intelligence Chip Design in Smart ManufacturingACM Transactions on Management Information Systems10.1145/351942213:4(1-20)Online publication date: 24-Mar-2022
        • (2022)Social learning discrete Particle Swarm Optimization based two-stage X-routing for IC design under Intelligent Edge Computing architectureApplied Soft Computing10.1016/j.asoc.2021.107215104:COnline publication date: 22-Apr-2022
        • (2021)Timing-Driven X-architecture Steiner Minimum Tree Construction Based on Social Learning Multi-Objective Particle Swarm OptimizationCompanion Proceedings of the Web Conference 202110.1145/3442442.3451143(77-84)Online publication date: 19-Apr-2021
        • (2021)X-architecture Steiner Tree Algorithm with Limited Routing Length inside Obstacle2021 11th International Conference on Information Technology in Medicine and Education (ITME)10.1109/ITME53901.2021.00040(152-156)Online publication date: Nov-2021
        • (2021)PSO-based Power-Driven X-Routing Algorithm in semiconductor design for predictive intelligence of IoT applicationsApplied Soft Computing10.1016/j.asoc.2021.108114114:COnline publication date: 30-Dec-2021
        • (2020)Timing-Driven Flow-Channel Network Construction for Continuous-Flow Microfluidic BiochipsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2019.291293639:6(1314-1327)Online publication date: Jun-2020
        • (2020)A Survey on Steiner Tree Construction and Global Routing for VLSI DesignIEEE Access10.1109/ACCESS.2020.29861388(68593-68622)Online publication date: 2020
        • (2020)Efficient VLSI routing algorithm employing novel discrete PSO and multi-stage transformationJournal of Ambient Intelligence and Humanized Computing10.1007/s12652-020-02659-8Online publication date: 13-Nov-2020
        • (2020)SLPSO-Based X-Architecture Steiner Minimum Tree ConstructionWeb Information Systems and Applications10.1007/978-3-030-60029-7_12(131-142)Online publication date: 23-Sep-2020
        • Show More Cited By

        View Options

        Login options

        Full Access

        View options

        PDF

        View or Download as a PDF file.

        PDF

        eReader

        View online with eReader.

        eReader

        Figures

        Tables

        Media

        Share

        Share

        Share this Publication link

        Share on social media