DocumentCode :
1244428
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
Volume :
24
Issue :
3
fYear :
2005
fDate :
3/1/2005 12:00:00 AM
Firstpage :
382
Lastpage :
394
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);
fLanguage :
English
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
Publisher :
ieee
ISSN :
0278-0070
Type :
jour
DOI :
10.1109/TCAD.2004.842803
Filename :
1397799
Link To Document :
بازگشت