Browsing by Author "Kao, Wei-Chun"

Now showing 1 - 2 of 2

Multi-Threaded Collision-Aware Global Routing with Bounded-Length Maze Routing
(2010-01-01)
Liu, Wen-Hao
;
Kao, Wei-Chun
;
Li, Yih-Lang
;
Chao, Kai-Yuan
;
資訊工程學系
Modern global routers use various routing methods to improve routing speed and the 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) to perform much faster routing than traditional maze routing algorithms. The proposed sequential global router, which adopts a heuristic-BLMR, identifies less-wirelength routing results with less runtime than state-of-the-art global routers. This study also proposes a parallel multi-threaded collision-aware global router based on a previous sequential global router. Unlike the conventional partition-based concurrency strategy, the proposed algorithm uses a task-based concurrency strategy. Experimental results reveal that the proposed sequential global router uses less wirelength and runs about 1.9X to 18.67X faster than other state-of-the-art global routers. Compared to the proposed sequential global router, the proposed parallel global router yields almost the same routing quality with average 2.71and 3.12-fold speedup on overflow-free and hard-to-route benchmarks, respectively, when running on an Intel quad-core system.
NCTU-GR 2.0: Multithreaded Collision-Aware Global Routing with Bounded-Length Maze Routing
(2013-05-01)
Liu, Wen-Hao
;
Kao, Wei-Chun
;
Li, Yih-Lang
;
Chao, Kai-Yuan
;
資訊工程學系
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.