DocumentCode :
3269547
Title :
Large-scale timing-driven rectilinear steiner tree construction in presence of obstacles
Author :
Huang, Hsin-Hsiung ; Chiu, Tung-Fu ; Lin, Yu-Cheng ; Hsieh, Tsai-Ming
Author_Institution :
Chung Yuan Christian Univ., Chungli
fYear :
2007
fDate :
5-8 Aug. 2007
Firstpage :
1122
Lastpage :
1125
Abstract :
In the paper, we provide a timing-driven rectilinear routing tree algorithm which applies top-down partitioning followed by the bottom-up routing tree construction in the presence of the obstacles. The objective is to simultaneously minimize the source-to-terminal delay and the total wirelength. First, a top-down partitioning method is used to divide the chip into four sub-regions according to the position of the source. Then, the terminals in each sub-region are connected by a fast sequential routing tree algorithm. The major steps of the routing algorithm include minimal spanning tree constructing, invalid edges pushing and routing. It shows experimentally that the maximum source-to-terminal delay of the routing tree is improved by 74%. Compared to previous results, total wirelength is significantly reduced by 34.7%.
Keywords :
integrated circuit design; integrated circuit layout; network routing; trees (mathematics); bottom-up routing tree construction; invalid edges pushing; large-scale timing-driven rectilinear Steiner tree; minimal spanning tree; sequential routing tree algorithm; source-to-terminal delay; source-to-terminal delay minimization; timing-driven rectilinear routing tree algorithm; top-down partitioning; total wirelength minimization; Cost function; Delay; Electronic commerce; Heuristic algorithms; Large-scale systems; Partitioning algorithms; Routing; Runtime; Timing; Tree graphs;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Circuits and Systems, 2007. MWSCAS 2007. 50th Midwest Symposium on
Conference_Location :
Montreal, Que.
ISSN :
1548-3746
Print_ISBN :
978-1-4244-1175-7
Electronic_ISBN :
1548-3746
Type :
conf
DOI :
10.1109/MWSCAS.2007.4488755
Filename :
4488755
Link To Document :
بازگشت