標題: | NCTU-GR 2.0: Multithreaded Collision-Aware Global Routing with Bounded-Length Maze Routing |
作者: | Liu, Wen-Hao Kao, Wei-Chun Li, Yih-Lang Chao, Kai-Yuan 資訊工程學系 Department of Computer Science |
關鍵字: | global routing;maze routing;multithreaded routing;physical design;rip-up and reroute |
公開日期: | 1-五月-2013 |
摘要: | 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 [12], [16], [17], [20]. 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. |
URI: | http://dx.doi.org/10.1109/TCAD.2012.2235124 http://hdl.handle.net/11536/21646 |
ISSN: | 0278-0070 |
DOI: | 10.1109/TCAD.2012.2235124 |
期刊: | IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS |
Volume: | 32 |
Issue: | 5 |
起始頁: | 709 |
結束頁: | 722 |
顯示於類別: | 期刊論文 |