A novel framework for multilevel full-chip gridless routing
Resource
Design Automation, 2006. Asia and South Pacific Conference on
Journal
Asia and South Pacific Conference on Design Automation, 2006.
Pages
-
Date Issued
2006-01
Date
2006-01
Author(s)
DOI
N/A
Abstract
Due to its great flexibility, gridless routing is desirable for nanometer circuit designs that use variable wire widths and spacings. Nevertheless, it is much more difficult than grid-based routing because of its larger solution space. In this paper, we present a novel "V-shaped" multilevel framework (called VMF) for full-chip gridless routing. Unlike the traditional "A-shaped" multilevel framework (inaccurately called the "Vcycle" framework in the literature), our VMF works in the V-shaped manner: top-down uncoarsening followed by bottom-up coarsening. Based on the novel framework, we develop a multilevel full-chip gridless router (called VMGR) for large-scale circuit designs. The top-down uncoarsening stage of VMGR starts from the coarsest regions and then processes down to finest ones level by level; at each level, it performs global pattern routing and detailed routing for local nets and then estimate the routing resource for the next level. Then, the bottom-up coarsening stage performs global maze routing and detailed routing to reroute failed connections and refine the solution level by level from the finest level to the coarsest one. We employ a dynamic congestion map to guide the global routing at all stages and propose a new cost function for congestion control. Experimental results show that VMGR achieves the best routability among all published gridless routers based on a set of commonly used MCNC benchmarks. Besides, VMGR can obtain significantly less wire-length, smaller critical path delay, and smaller average net delay than the previous works. In particular, VMF is general and thus can readily apply to other problems.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
01594757.pdf
Size
410.37 KB
Format
Adobe PDF
Checksum
(MD5):d7963352778c73c0a8824e303cfeeb5f