Abstract
We present in this thesis a fast and stable global router called NTHU-Route 2.0 that improves the solution quality and runtime of a state-of-the-art router, NTHURoute, by the following enhancements: (1) a new history based cost function, (2) new ordering methods for rip-up-and-reroute and congested region identification, and (3) two implementation techniques. The experimental results show that our router solves all ISPD98 benchmarks with very good quality. Besides, it routes 7 of 8 ISPD07 benchmarks without inducing any overflow. In particular, for one of the benchmarks which are thought to be difficult cases previously, our router is the only one that can completely eliminate its total overflow. Our router also successfully solves 12 of 16 ISPD08 benchmarks without causing any overflow and efficiently generates the best solutions for almost all benchmarks among all stateof-the-art global routers.