Neural Network Approach To The Routing Problem

The routing problem of VLSI layout is to realize the interconnection requirements of the given netlists. This problem is in the NP-complete class and most of the currently available algorithms are heuristic. This paper proposes a new architecture of neural network based on the Hopfield and Tank model for the routing problem. Our approach takes all interconnection requirements into consideration simultaneously. Using the massive parallelism of a neural network to solve NP-complete problems has been demonstrated to be an effective approach. However, applying this technique to the routing problem is still to be investigated. This network is constructed of two layers of neurons. One layer of neurons is used for minimizing the total path length and distributing interconnecting wires evenly among channels. The other layer of neurons is used for channel capacity enforcement. A set of randomly generated testing examples are used to verify the performance of our approach. About 15-20% reduction of total path length is achieved using this network.