Title :
Median biased Steiner tree heuristics in the rectilinear plane for low-power physical layout
Author :
Jiménez, Manuel A. ; Shanblatt, Michael A.
Author_Institution :
Dept. of Electr. Eng., Michigan State Univ., East Lansing, MI, USA
Abstract :
Two heuristics are proposed for the rectilinear Steiner-minimum tree (SMT) problem arising when interconnecting multiple terminals in a layout with obstacles. Efficient algorithms are implemented to convert circuit layouts into graphs. A set of reduction techniques are implemented to remove unfeasible vertices. These techniques delete an average of over 90% of the m Steiner candidates in O(m2) time. The proposed SMT heuristics grow trees biased by the terminal distances of the n vertices in a graph in O(n2.log n) time. The results obtained highlight their suitability to be used as wire length estimators in a power optimizing placement tool
Keywords :
VLSI; circuit layout CAD; integrated circuit layout; low-power electronics; network topology; trees (mathematics); wiring; SMT heuristics; VLSI; circuit layouts; low-power physical layout; median biased Steiner tree heuristics; multiple terminals; obstacles; power optimizing placement tool; rectilinear plane; reduction techniques; terminal distances; unfeasible vertices; wire length estimators; Capacitance; Integrated circuit interconnections; LAN interconnection; Programmable logic arrays; Routing; Steiner trees; Surface-mount technology; Tree graphs; Very large scale integration; Wire;
Conference_Titel :
Circuits and Systems, 1998. Proceedings. 1998 Midwest Symposium on
Conference_Location :
Notre Dame, IN
Print_ISBN :
0-8186-8914-5
DOI :
10.1109/MWSCAS.1998.759484
