| |
Jiayuan He, Martin Burtscher, Rajit Manohar, Keshav Pingali
The complexity of global routing increases rapidly
as chip designs grow larger. In many global routers, maze routing
is the most time-consuming stage. One way to reduce its runtime
is parallelization. Existing parallel maze routers work either
by identifying and routing independent nets or by partitioning
the chip area into non-overlapping regions. In this paper, we
describe a scalable parallel global router called SPRoute that
initially exploits net-level parallelism, automatically lowers the
parallelism when livelock is identified, and finally switches to fine-grain
parallelism to guarantee convergence. We evaluate SPRoute
on a 28-core machine on the ISPD 2008 global routing contest
benchmark suite. It achieves an average speedup of 11.5 with a
wirelength penalty of 0.6% on overflow-free benchmarks, and an
average speedup of 4.5 with a total overflow penalty of 7% on
hard-to-route benchmarks over sequential SPRoute. Compared
to FastRoute 4.1, SPRoute achieves an average speedup of
11.0 and 3.1 on overflow-free benchmarks and hard-to-route
benchmarks, respectively.
|
|
