Neural Computation for Channel Routing Using Hopfield Neural Network Model

Takashi SHIMAMOTO  Akio SAKAMOTO  

Publication
IEICE TRANSACTIONS (1976-1990)   Vol.E72   No.12   pp.1360-1366
Publication Date: 1989/12/25
Online ISSN: 
DOI: 
Print ISSN: 0000-0000
Type of Manuscript: Special Section PAPER (Special Issue on the 2nd Karuizawa Workshop on Circuits and Systems)
Category: VLSI Design Technology
Keyword: 


Full Text: PDF>>
Buy this Article




Summary: 
A neural network model for solving channel routing problem is proposed and described. Channel routing problem is one of the most important and popular phases of computer aided design of VLSI chips. Since the problem is NP-complete, many heuristic algorithms with various routing conditions have been proposed for the last decade. Recently, J.J. Hopfield has demonstrated that a neural network can provide a heuristic technique for solving optimization problem. This paper describes how channel routing problem can be solved by a neural network model proposed by Hopfield. A brief summary of Hopfield neural network model, how to construct a neural network for solving channel routing problem, and results of digital computer simulation are described. Our results show that the neural network could provide good solutions of channel routing problem. For example, it computes a solution of the number of horizontal tracks 31 for the difficult example" and by using simple compaction algorithm the solution can be improved to 28, which is optimal within our channel routing strategy.