Title :
An A* algorithm to yield an optimal solution for the channel routing problem in VLSI
Author :
Wang, Jia-Shung ; Lee, R.C.T.
Author_Institution :
Inst. of Comput. & Decision Sci., Nat. Tsing Hua Univ., Hsinchu, Taiwan
Abstract :
An algorithm is proposed to find an optimal solution for the channel-routing problem in VLSI design. The algorithm is an A* algorithm with good heuristics and dominance rules to terminate unnecessary nodes in the searching-tree. Theoretical and experimental results indicate that it behaves quite well in average cases. The authors obtained an optimal solution for the Deutsch difficult case in 5.5 minutes of CPU time, with the algorithm implemented in Pascal and run on a VAX 11/750 computer.<>
Keywords :
DEC computers; VLSI; circuit layout CAD; optimisation; search problems; trees (mathematics); 5.5 min; A* algorithm; CPU time; Deutsch difficult case; Pascal; VAX 11/750 computer; VLSI design; channel routing; dominance rules; heuristics; optimal solution; searching-tree; unnecessary nodes; Algorithm design and analysis; Cost function; Councils; Data structures; Heuristic algorithms; Polynomials; Routing; Tree graphs; Very large scale integration; Wire;
Conference_Titel :
Artificial Intelligence for Industrial Applications, 1988. IEEE AI '88., Proceedings of the International Workshop on
Conference_Location :
Hitachi City, Japan
DOI :
10.1109/AIIA.1988.13290
