FastRoute: An Efficient and High-Quality Global Router

dc.contributor.author Pan, Min
dc.contributor.author Xu, Yue
dc.contributor.author Chu, Chris Chong-Nuen
dc.contributor.author Zhang, Yanheng
dc.contributor.author Chu, Chris Chong-Nuen
dc.contributor.department Electrical and Computer Engineering
dc.date 2018-02-17T17:56:47.000
dc.date.accessioned 2020-06-30T02:02:00Z
dc.date.available 2020-06-30T02:02:00Z
dc.date.copyright Sun Jan 01 00:00:00 UTC 2012
dc.date.issued 2012-01-01
dc.description.abstract <p>Modern large-scale circuit designs have created great demand for fast and high-quality global routing algorithms to resolve the routing congestion at the global level. Rip-up and reroute scheme has been employed by the majority of academic and industrial global routers today, which iteratively resolve the congestion by recreating the routing path based on current congestion. This method is proved to be the most practical routing framework. However, the traditional iterative maze routing technique converges very slowly and easily gets stuck at local optimal solutions. In this work, we propose a very efficient and high-quality global router—FastRoute. FastRoute integrates several novel techniques: fast congestion-driven via-aware Steiner tree construction, 3-bend routing, virtual capacity adjustment, multisource multi-sink maze routing, and spiral layer assignment. These techniques not only address the routing congestion measured at the edges of global routing grids but also minimize the total wirelength and via usage, which is critical for subsequent detailed routing, yield, and manufacturability. Experimental results show that FastRoute is highly effective and efficient to solve ISPD07 and ISPD08 global routing benchmark suites. The results outperform recently published academic global routers in both routability and runtime. In particular, for ISPD07 and ISPD08 global routing benchmarks, FastRoute generates 12 congestion-free solutions out of 16 benchmarks with a speed significantly faster than other routers.</p>
dc.description.comments <p>This is an article from <em>VLSI Design</em> 2012 (2012): 608362, doi: <a href="http://dx.doi.org/10.1155/2012/608362" target="_blank">10.1155/2012/608362</a>. Posted with permission.</p>
dc.format.mimetype application/pdf
dc.identifier archive/lib.dr.iastate.edu/ece_pubs/103/
dc.identifier.articleid 1104
dc.identifier.contextkey 8736621
dc.identifier.s3bucket isulib-bepress-aws-west
dc.identifier.submissionpath ece_pubs/103
dc.identifier.uri https://dr.lib.iastate.edu/handle/20.500.12876/20924
dc.language.iso en
dc.source.bitstream archive/lib.dr.iastate.edu/ece_pubs/103/2012_ChuC_FastRouteEfficient.pdf|||Fri Jan 14 18:18:04 UTC 2022
dc.source.uri 10.1155/2012/608362
dc.subject.disciplines Electrical and Computer Engineering
dc.title FastRoute: An Efficient and High-Quality Global Router
dc.type article
dc.type.genre article
dspace.entity.type Publication
relation.isAuthorOfPublication 18176b63-cd29-4c6c-8d6e-037695390cd9
relation.isOrgUnitOfPublication a75a044c-d11e-44cd-af4f-dab1d83339ff
File
Original bundle
Now showing 1 - 1 of 1
Name:
2012_ChuC_FastRouteEfficient.pdf
Size:
2.25 MB
Format:
Adobe Portable Document Format
Description:
Collections