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

fYear

1988

fDate

25-27 May 1988

Firstpage

181

Lastpage

187

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Artificial Intelligence for Industrial Applications, 1988. IEEE AI '88., Proceedings of the International Workshop on

Conference_Location

Hitachi City, Japan

Type

conf

DOI

10.1109/AIIA.1988.13290

Filename

13290

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3363339