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

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

61 Scopus citations


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.

Original languageEnglish
Title of host publicationProceedings of the 47th Design Automation Conference, DAC '10
Number of pages6
StatePublished - 2010
Event47th Design Automation Conference, DAC '10 - Anaheim, CA, United States
Duration: 13 Jun 201018 Jun 2010

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Conference47th Design Automation Conference, DAC '10
Country/TerritoryUnited States
CityAnaheim, CA


  • Global routing
  • Maze routing
  • Multi-threaded


Dive into the research topics of 'Multi-threaded collision-aware global routing with bounded-length maze routing'. Together they form a unique fingerprint.

Cite this