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
fDate :
7/1/1990 12:00:00 AM
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;
Journal_Title :
Computers, IEEE Transactions on
