Back to Search
Start Over
Timing-Driven Obstacle-Avoiding X-Architecture Steiner Minimum Tree Algorithm With Slack Constraints
- Source :
- IEEE Transactions on Systems, Man, and Cybernetics: Systems; 2024, Vol. 54 Issue: 5 p2927-2940, 14p
- Publication Year :
- 2024
-
Abstract
- Steiner minimum tree (SMT) is an optimized model for solving the routing problem of a multipin net in very large-scale integrated circuits. As the appearance of various obstacles on chips, the obstacle-avoiding problem has attracted much attention in recent years. Meanwhile, since interconnect delay plays a major role in chip delay, timing analysis is another critical problem worthy of consideration when constructing an SMT. Furthermore, the introduction of the <inline-formula> <tex-math notation="LaTeX">$\boldsymbol {X}$ </tex-math></inline-formula>-architecture allows for better utilization of routing resources. In this article, a timing-driven obstacle-avoiding X-architecture Steiner minimum tree algorithm with slack constraints (TD-OAXSMT-SC) is proposed to consider obstacle-avoiding, timing slack constraints, and <inline-formula> <tex-math notation="LaTeX">$\boldsymbol {X}$ </tex-math></inline-formula>-architecture simultaneously for the first time. The TD-OAXSMT-SC algorithm consists of four major stages: 1) in the routing tree initialization stage, this article constructs an <inline-formula> <tex-math notation="LaTeX">$\boldsymbol {X}$ </tex-math></inline-formula>-architecture Prim–Dijkstra spanning tree as the initial routing tree with minimum total delay; 2) in the particle swarm optimization (PSO)-based routing tree iteration stage, a novel discrete PSO algorithm based on genetic operators is proposed to obtain a high-quality routing tree; 3) in the routing tree standardization stage, two effective standardization strategies are proposed to obtain a routing tree that satisfies both obstacle-avoiding and timing slack constraints; and 4) in the routing tree optimization stage, the connection of interconnected wires is optimized in a global manner, thus obtaining an optimized routing tree. Experimental results show that the proposed TD-OAXSMT-SC algorithm outperforms the state-of-the-art methods in routing quality with slack constraints.
Details
- Language :
- English
- ISSN :
- 21682216 and 21682232
- Volume :
- 54
- Issue :
- 5
- Database :
- Supplemental Index
- Journal :
- IEEE Transactions on Systems, Man, and Cybernetics: Systems
- Publication Type :
- Periodical
- Accession number :
- ejs66174405
- Full Text :
- https://doi.org/10.1109/TSMC.2024.3353534