Multi-threaded collision-aware global routing with bounded-length maze routing

Wen Hao Liu*, Wei Chun Kao, Yih-Lang Li, Kai Yuan Chao


研究成果: Conference contribution同行評審

61 引文 斯高帕斯(Scopus)


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.71 and 3.12-fold speedup on overflow-free and hard-to-route benchmarks, respectively, when running on an Intel quad-core system.

主出版物標題Proceedings of the 47th Design Automation Conference, DAC '10
出版狀態Published - 2010
事件47th Design Automation Conference, DAC '10 - Anaheim, CA, United States
持續時間: 13 6月 201018 6月 2010


名字Proceedings - Design Automation Conference


Conference47th Design Automation Conference, DAC '10
國家/地區United States
城市Anaheim, CA


深入研究「Multi-threaded collision-aware global routing with bounded-length maze routing」主題。共同形成了獨特的指紋。