MARS Multilevel Full-Chip Routing System

Project Director: Professor Jason Cong
People: Yan Zhang Min Xie

1. Introduction

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 resource 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.

2. Benchmarks

GDF file format [PDF]
GDF parser [gdfparser.tar.gz-solaris] [gdfparser-linux rhep3.0]
Uniform Design Rule Examples [design.gz]
Variable Design Rule Examples (with 10% longest nets scaled to 1.5x, the next 10% scaled to 1.2x) [vd_design.gz]
Layer Assignment Examples (Chang and Cong, TCAD 99) [ via_min_data.tar.gz]

3. Publications

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, November 2001.
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, November 2002
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

MARS 1.0 [Linux Version rhep 3.0]

Please send comments regarding this page to zhangyan@cs.ucla.edu .