DocumentCode :
26672
Title :
NCTU-GR 2.0: Multithreaded Collision-Aware Global Routing With Bounded-Length Maze Routing
Author :
Wen-Hao Liu ; Wei-Chun Kao ; Yih-Lang Li ; Kai-Yuan Chao
Author_Institution :
Dept. of Comput. Sci., Nat. Chiao-Tung Univ., Hsinchu, Taiwan
Volume :
32
Issue :
5
fYear :
2013
fDate :
May-13
Firstpage :
709
Lastpage :
722
Abstract :
Modern global routers employ various routing methods to improve routing speed and quality. Maze routing is the most time-consuming process for existing global routing algorithms. This paper presents two bounded-length maze routing (BLMR) algorithms (optimal-BLMR and heuristic-BLMR) that perform much faster routing than traditional maze routing algorithms. In addition, a rectilinear Steiner minimum tree aware routing scheme is proposed to guide heuristic-BLMR and monotonic routing to build a routing tree with shorter wirelength. This paper also proposes a parallel multithreaded collision-aware global router based on a previous sequential global router (SGR). Unlike the partitioning-based strategy, the proposed parallel router uses a task-based concurrency strategy. Finally, a 3-D wirelength optimization technique is proposed to further refine the 3-D routing results. Experimental results reveal that the proposed SGR uses less wirelength and runs faster than most of other state-of-the-art global routers with a different set of parameters , , , . Compared to the proposed SGR, the proposed parallel router yields almost the same routing quality with average 2.71 and 3.12-fold speedup on overflow-free and hard-to-route cases, respectively, when running on a 4-core system.
Keywords :
multi-threading; network routing; tree searching; 3D routing; 3D wirelength optimization technique; 4 core system; bounded length maze routing algorithm; global routers; global routing algorithm; heuristic BLMR; monotonic routing; multithreaded collision aware global routing; parallel multithreaded collision aware global router; parallel router; partitioning based strategy; rectilinear Steiner minimum tree aware routing; routing quality; routing speed; routing tree; sequential global router; task based concurrency strategy; time consuming process; various routing method; Cost function; Delays; Heuristic algorithms; History; Routing; Runtime; Skeleton; Global routing; maze routing; multithreaded routing; physical design; rip-up and reroute;
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/TCAD.2012.2235124
Filename :
6504553
Link To Document :
بازگشت