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
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;
Conference_Titel :
Circuits and Systems, 2007. MWSCAS 2007. 50th Midwest Symposium on
Conference_Location :
Montreal, Que.
Print_ISBN :
978-1-4244-1175-7
Electronic_ISBN :
1548-3746
DOI :
10.1109/MWSCAS.2007.4488755