A gridless router based on hierarchical PB corner stitching structure

Author

Zhang, Yiqian ; Cai, Yici ; Hong, Xianlong ; Zhang, Yan ; Xie, Min

Author_Institution

Dept. of Comput. Sci. & Technol., Tsinghua Univ., Beijing, China

Volume

2

fYear

2002

fDate

29 June-1 July 2002

Firstpage

1438

Abstract

A multi-layer gridless area router is given in this paper. Based on corner stitching, this router adopts tile expansion to explore path for each net. A heuristic method that penalizes nodes deviating from the destination is devised to accelerate the algorithm. Besides, an enhanced interval tree is used to manage the intermediate data structure. In order to eliminate the effect that the routing order has on final results, a new gridless rip-up and rerouting algorithm is proposed. Test results indicate that the completion rate is improved after the rip-up and reroute process and the speed of this algorithm is satisfactory.

Keywords

circuit layout CAD; network routing; trees (mathematics); hierarchical PB corner stitching structure; interval tree; multi-layer gridless area router; rip-up and rerouting algorithm; tile expansion; Acceleration; Algorithm design and analysis; Computer science; Data structures; Databases; Nonhomogeneous media; Routing; Testing; Tiles; Tree data structures;

fLanguage

English

Publisher

ieee

Conference_Titel

Communications, Circuits and Systems and West Sino Expositions, IEEE 2002 International Conference on

Print_ISBN

0-7803-7547-5

Type

conf

DOI

10.1109/ICCCAS.2002.1179050

Filename

1179050