DocumentCode
1320021
Title
An efficient channel routing algorithm to yield an optimal solution
Author
Wang, Jia-Shung ; Lee, R.C.T.
Author_Institution
Inst. of Comput. Sci., Tsing Hua Univ., Hsinchu, Taiwan
Volume
39
Issue
7
fYear
1990
fDate
7/1/1990 12:00:00 AM
Firstpage
957
Lastpage
962
Abstract
An algorithm known as optimal channel routing (OCR) is proposed which finds an optimal solution for the channel routing problem in VLSI design. The algorithm is an A * algorithm with good heuristics and dominance rules for terminating unnecessary nodes in the searching tree. Experimental results, agreeing with theoretical analysis, show that it behaves quite well in average cases. An optimal solution is obtained for the Deutsch difficult case in 5.5-min-CPU time after the algorithm is implemented in Pascal and run on a VAX 11/750 computer
Keywords
VLSI; circuit layout CAD; trees (mathematics); Pascal; VAX 11/750 computer; VLSI design; channel routing algorithm; dominance rules; heuristics; optimal solution; searching tree; Algorithm design and analysis; Cost function; Councils; Heuristic algorithms; Optical character recognition software; Polynomials; Routing; Tree data structures; Tree graphs; Very large scale integration;
fLanguage
English
Journal_Title
Computers, IEEE Transactions on
Publisher
ieee
ISSN
0018-9340
Type
jour
DOI
10.1109/12.55698
Filename
55698
Link To Document