Title :
On the Steiner tree problem in L3-metric [VLSI wiring]
Author :
Li, Y.Y. ; Cheung, S.K. ; Leung, K.S. ; Wong, C.K.
Author_Institution :
Dept. of Comput. Sci. & Eng., Chinese Univ. of Hong Kong, Shatin, Hong Kong
Abstract :
We consider Steiner minimal trees (SMT) in metrics defined by given orientations. The problem is motivated by wiring consideration of VLSI chips when the wiring direction is not restricted to only horizontal and vertical. In particular, we concentrate on the case when the given orientations form angles of 0°, 60° and 120° (λ3-metric) since many interesting results can be obtained, which may shed light on other metrics in the family. Specifically, we show that any SMT can be transformed to one with their Steiner points located on the grid points of a multilevel grid, where the number of levels is at most [n-2/2], n being the number of input points. Based on this result, we have developed a Simulated Annealing (SA) based algorithm to generate near-optimal SMT´s. Empirical results compared with Euclidean cases are also given
Keywords :
VLSI; circuit layout CAD; integrated circuit layout; network routing; network topology; simulated annealing; trees (mathematics); L3-metric; Steiner minimal trees; Steiner tree problem; VLSI chip layout; VLSI wiring; multilevel grid; orientations; simulated annealing based algorithm; Computer science; Euclidean distance; Industrial engineering; Manufacturing; Simulated annealing; Steiner trees; Surface-mount technology; Very large scale integration; Wires; Wiring;
Conference_Titel :
Circuits and Systems, 1997. ISCAS '97., Proceedings of 1997 IEEE International Symposium on
Print_ISBN :
0-7803-3583-X
DOI :
10.1109/ISCAS.1997.621428
