Name
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 "V-cycle" 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 wirelength, 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. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1145/1118299.1118448 | ASP-DAC |
Keywords | Field | DocType |
multilevel framework,routing resource,next level,global pattern routing,multilevel full-chip,gridless routing,novel framework,global routing,global maze routing,detailed routing,finest level,grid-based routing,network routing,cost function,network synthesis,chip,circuit design,critical path,top down,bottom up,congestion control | Multipath routing,Equal-cost multi-path routing,Link-state routing protocol,Dynamic Source Routing,Static routing,Computer science,Parallel computing,Destination-Sequenced Distance Vector routing,Real-time computing,Electronic engineering,Routing table,Routing Information Protocol | Conference |
ISSN | ISBN | Citations |
2153-6961 | 0-7803-9451-8 | 13 |
PageRank | References | Authors |
0.78 | 22 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tai-Chen Chen | 1 | 87 | 7.99 |
| Yao-Wen Chang | 2 | 3437 | 253.54 |
| Shyh-Chang Lin | 3 | 279 | 17.98 |