Title :
MARS-a multilevel full-chip gridless routing system
Author :
Cong, J. ; Jie Fang ; Min Xie ; Yan Zhang
Author_Institution :
Comput. Sci. Dept., Univ. of California, Los Angeles, CA, USA
fDate :
3/1/2005 12:00:00 AM
Abstract :
This paper presents MARS, a novel multilevel full-chip gridless 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.7/spl times/.
Keywords :
VLSI; circuit optimisation; integrated circuit design; network routing; trees (mathematics); MARS; design automation; graph-based Steiner tree heuristic; history-based iterative refinement; multilevel full-chip gridless routing system; recursive coarsening; recursive refinement; resource reservation; routing flow; routing optimization; routing regions; very large scale integration; Circuit noise; Field programmable gate arrays; Iterative algorithms; Iterative methods; Partitioning algorithms; Routing; Runtime; Very large scale integration; Design automation; routing optimization methods; very large scale integration (VLSI);
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2004.842803