Routing Algorithm Based on Obstacle-Avoiding Rectilinear Steiner Minimum Tree for Three-Dimensional Integrated Circuit
Journal of Circuits, Systems and Computers · 28.03.2026
DOI: 10.1142/s0218126626501768 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Circuits, Systems and Computers, online erschienen am 28.03.2026. Verfasst von Zhensong Li und 1 weiteren Autor:innen. Die Arbeit nennt 24 Literaturangaben. Gefördert von: Joint Funds of the National Natural Science Foundation of China.
Abstract (Originalsprache)
In view of the routing stage of very large-scale integration circuits (VLSI), it is essential to construct an obstacle-avoiding rectilinear Steiner minimum tree (OARSMT) quickly and efficiently. For three-dimensional integrated circuits (3D ICs), the routing stage is a critical problem that cannot be handled efficiently by commercial electronic design automation (EDA) software. In this paper, single-layer OARSMT (SL-OARSMT) and three-dimensional OARSMT (3D-OARSMT) routing algorithms are proposed to complete the routing stage in a three-dimensional integration system. In the SL-OARSMT algorithm, an obstacle-avoiding spanning graph (OASG) is constructed, and a multi-terminal spanning tree (MTST) is built and then converted into a pin spanning tree (PST) by removing all nonpin points from the MTST. Then, a rectilinear Steiner minimum tree (RSMT) is generated and legalized to obtain a legal routing solution for a single routing layer. Multi-segment-edge global optimization and V-type local optimization are adopted to achieve the minimum routing length. The 3D-OARSMT is formed by combining SL-OARSMT with the strategic insertion of through-silicon vias (TSVs), thereby enabling effective handling of inter-layer routing in 3D integrated circuits. Experimental results show that the SL-OARSMT algorithm achieves a 2–5% reduction in total wire length compared to recent leading research and makes single-layer routing more efficient. For the 3D-OARSMT, the number of TSVs required for inter-layer routing is significantly reduced, and this algorithm provides a feasible solution for 3D integration system routing.
Förderung
- Joint Funds of the National Natural Science Foundation of China
Zitieren
APA
Li, Z., & Wen, H. (2026). Routing Algorithm Based on Obstacle-Avoiding Rectilinear Steiner Minimum Tree for Three-Dimensional Integrated Circuit. Journal of Circuits, Systems and Computers. https://doi.org/10.1142/s0218126626501768
Vancouver
Li Z, Wen H. Routing Algorithm Based on Obstacle-Avoiding Rectilinear Steiner Minimum Tree for Three-Dimensional Integrated Circuit. Journal of Circuits, Systems and Computers. 2026. doi:10.1142/s0218126626501768
BibTeX
@article{Li2026,
author = {Li, Zhensong and Wen, Hao},
title = {Routing Algorithm Based on Obstacle-Avoiding Rectilinear Steiner Minimum Tree for Three-Dimensional Integrated Circuit},
journal = {Journal of Circuits, Systems and Computers},
year = {2026},
doi = {10.1142/s0218126626501768}
}
EUVIMED