Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
MaizeRouter: engineering an effective global router
Moffitt M.  ASP-DAC 2008 (Proceedings of the 2008 Asia and South Pacific Design Automation Conference, Seoul, Korea, Jan 21-24, 2008)226-231.2008.Type:Proceedings
Date Reviewed: Apr 17 2009

Routing is an essential step in the process of modern very large-scale integration (VLSI) physical design. Without an effective and efficient router, it is difficult to implement the physical layout of an integrated circuit that may contain millions or even billions of transistors. Since routing is a very complex task, it is usually split into two phases: global routing and detailed routing. Also, due to the fact that global routing can significantly influence the performance of a design, continuous effort in the research and development of global routing engines is indispensable.

The global routing contest held at the International Symposium on Physical Design (ISPD) is a very competitive contest, and MaizeRouter won first place in the three-dimensional (3D) track of the contest, in 2007. This paper presents the algorithmic and conceptual details that constitute the router.

Although MaizeRouter has achieved excellent routing results in terms of overflow, total wirelength, and runtime, its main concepts rely on two relatively simple edge-based operations: extreme edge shifting and edge retraction. The major purpose of extreme edge shifting is to move nets out of highly congested regions, while at the same time preserving their connections. Since extreme edge shifting can increase the total wirelength of a design, Moffitt proposes the use of edge retraction to reduce it.

In addition to the two edge-based operations, the paper presents many other techniques, including: interdependent net decomposition, a data structure for representing multiterminal nets; rapid exploration, for rapidly moving net segments; garbage collection, for removing dangling nets; and net defragmentation, for merging net segments. Although these techniques are easy to understand and implement, they are essential to complement the two edge-based operations, and can be used in other applications as well.

However, according to the experimental results published by the author, MaizeRouter is not significantly better than other leading routers, after those routers have been fine tuned. Nevertheless, the paper contains innovative concepts and techniques that can be incorporated into other global routers, to achieve even better results.

Reviewer:  I-Lun Tseng Review #: CR136707 (1007-0689)
Bookmark and Share
  Reviewer Selected
 
 
Placement And Routing (B.7.2 ... )
 
 
Routing And Layout (F.2.2 ... )
 
 
Performance Analysis And Design Aids (B.8.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Placement And Routing": Date
A 2d channel router for the diagonal model
Lodi E., Luccio F., Song X. Integration, the VLSI Journal 11(2): 111-125, 1991. Type: Article
Aug 1 1992
Tree placement in Cascode-switch macros
Sarrafzadeh M. Integration, the VLSI Journal 11(2): 127-139, 1991. Type: Article
Oct 1 1992
VYUHA
Ravikumar C., Sastry S. Integration, the VLSI Journal 11(2): 141-157, 1991. Type: Article
Aug 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy