TY - JOUR
T1 - Spanning graph-based nonrectilinear steiner tree algorithms
AU - Zhu, Qi
AU - Zhou, Hai
AU - Jing, Tong
AU - Hong, Xian Long
AU - Yang, Yang
N1 - Funding Information:
Manuscript received March 14, 2004; revised August 29, 2004. This work was supported in part by the NSFC (China) under Grant 60373012, the NSF (USA) under Grant CCR-0238484, the Specialized Research Fund for the Doctoral Program of Higher Education of China under Grant 20020003008, the Hi-Tech Research and Development (863) Program of China under Grant 2004AA1Z1050, and the Key Faculty Support Program of Tsinghua University under Grant [2002]4. A preliminary version of this work has been published in the IEEE/ACM Asian–Pacific Design Automation Conference (ASP-DAC), Yokohama, Japan, 2004, pp. 687–690. This paper was recommended by Associate Editor M. D. F. Wong.
PY - 2005/7
Y1 - 2005/7
N2 - With advances in fabrication technology of very/ultra large scale integrated circuit (VLSI/ULSI), we must face many new challenges. One of them is the interconnect effects, which may cause longer delay and heavier crosstalk. To solve this problem, many interconnect performance optimization algorithms have been proposed. However, when these algorithms are designed based on rectilinear interconnect architecture, the optimization capability is limited. Therefore, nonrectilinear interconnect architectures become a field of active research in which the octilinear interconnect architecture is the most promising one since it extends from the rectilinear case and greatly shortens the wire length. Meanwhile, an interconnect with less length is helpful to reduce wire capacitance, congestion, and routing area. In an interconnect architecture, the Steiner minimal tree (SMT) construction is one of the key problems. In this paper, we give two practical octilinear Steiner minimal tree (OSMT) construction algorithms based on octilinear spanning graphs (OSGs). The one with edge substitution (OST-E) has a worst-case running time of O(n log n) and a similar performance as the recent work using batched greedy. The other one with triangle contraction (OST-T) has a small increase in the constant factor of running time and a better performance. These two are the fastest algorithms for octilinear Steiner tree construction so far. Experiments on both industrial and random test cases are conducted to compare with other programs. We also proposed the extension of our algorithms to any λ geometry.
AB - With advances in fabrication technology of very/ultra large scale integrated circuit (VLSI/ULSI), we must face many new challenges. One of them is the interconnect effects, which may cause longer delay and heavier crosstalk. To solve this problem, many interconnect performance optimization algorithms have been proposed. However, when these algorithms are designed based on rectilinear interconnect architecture, the optimization capability is limited. Therefore, nonrectilinear interconnect architectures become a field of active research in which the octilinear interconnect architecture is the most promising one since it extends from the rectilinear case and greatly shortens the wire length. Meanwhile, an interconnect with less length is helpful to reduce wire capacitance, congestion, and routing area. In an interconnect architecture, the Steiner minimal tree (SMT) construction is one of the key problems. In this paper, we give two practical octilinear Steiner minimal tree (OSMT) construction algorithms based on octilinear spanning graphs (OSGs). The one with edge substitution (OST-E) has a worst-case running time of O(n log n) and a similar performance as the recent work using batched greedy. The other one with triangle contraction (OST-T) has a small increase in the constant factor of running time and a better performance. These two are the fastest algorithms for octilinear Steiner tree construction so far. Experiments on both industrial and random test cases are conducted to compare with other programs. We also proposed the extension of our algorithms to any λ geometry.
KW - Deep submicron (DSM)
KW - Interconnect
KW - Physical design
KW - Routing
KW - Steiner tree
KW - Very large scale integration (VLSI)
UR - http://www.scopus.com/inward/record.url?scp=22544443621&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=22544443621&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2005.850862
DO - 10.1109/TCAD.2005.850862
M3 - Article
AN - SCOPUS:22544443621
SN - 0278-0070
VL - 24
SP - 1066
EP - 1075
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 7
ER -