MARS Multilevel Full-Chip
Project Director: Professor
This project is about MARS, a novel multilevel
full-chip routing system. The multilevel framework with recursive coarsening
and refinement allows for scaling of our gridless routing system to very
large designs. The downward pass of recursive coarsening builds the representations
of routing regions at different levels while the upward pass of iterative
refinement allows a gradually improved solution. We introduced a number
of efficient techniques in the multilevel routing scheme, including
reservation, graph-based Steiner tree heuristic and history-based
iterative refinement. We compared our multilevel framework with a recently
published three-level routing flow. Experimental results show that MARS
helps to improve the completion rate by over 10%, and the runtime by 11.7x.
Moreover, the multilevel framework combines
global routing and detailed routing in a seamless fashion, with the potential
for integrating various interconnect optimization algorithms at different
levels. and allows us to apply gridless routing to full-chip designs.
For the future work, we will integrate different optimization algorithms
in the framework, such as, temperature constraints, etc. We will
further our research to find out an efficient way to insert individual
optimization algorithms into the multilevel framework and learn about how
those algorithms will interact with each other throughout the framework.
To our knowledge, this is the first time that multilevel optimization as
been applied to IC routing.
J. Cong, J. Fang and Y. Zhang "Multilevel
Approach to Full-Chip Gridless Routing," Proc. IEEE International
Conference on Computer Aided Design, San Jose, California, pp. 396-403,
J. Cong, M. Xie and Y. Zhang, "An
Enhanced Multilevel Routing System," Proc. IEEE International
Conference on Computer Aided Design, San Jose, California, pp 51-58,
J. Cong, J. Fang, M. Xie, and Y. Zhang, "MARS
- A Multilevel Full-Chip Gridless Routing System," IEEE Transactions
on Computer-Aided Design of Integrated Circuits and Systems, Vol. 24,
No. 3, pp. 382-394, March 2005.
4. Software Release
Please send comments regarding this page to email@example.com