Title :
Spanning graph-based nonrectilinear steiner tree algorithms
Author :
Zhu, Qi ; Zhou, Hai ; Jing, Tong ; Hong, Xian-Long ; Yang, Yang
Author_Institution :
Comput. Sci. & Technol. Dept., Tsinghua Univ., Beijing, China
fDate :
7/1/2005 12:00:00 AM
Abstract :
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(nlogn) 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.
Keywords :
ULSI; VLSI; circuit layout CAD; circuit optimisation; integrated circuit interconnections; integrated circuit layout; network routing; trees (mathematics); ULSI; VLSI; edge substitution; integrated circuit interconnection; interconnect performance optimization algorithms; nonrectilinear Steiner tree algorithms; nonrectilinear interconnect architectures; octilinear Steiner minimal tree construction; octilinear interconnect architecture; octilinear spanning graphs; rectilinear interconnect architecture; spanning graph; triangle contraction; ultra large scale integration; very large scale integration; Crosstalk; Delay effects; Fabrication; Integrated circuit interconnections; Integrated circuit technology; Steiner trees; Tree graphs; Ultra large scale integration; Very large scale integration; Wire; Deep submicron (DSM); Steiner tree; interconnect; physical design; routing; very large scale integration (VLSI);
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2005.850862