A Digital Neural Network for Multilayer Channel Routing with Crosstalk Minimization


IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E80-A       pp.1704-1713
Publication Date: 1997/09/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Category: Neural Networks
crosstalk,  multilayer channel routing,  neural network,  digital technology,  NP-complete,  

Full Text: PDF>>
Buy this Article

A digital neural network approach is presented for the multilayer channel routing problem with the objective of crosstalk minimization in this paper. As VLSI fabrication technology advances, the reduction of crosstalk between interconnection wires on a chip has gained important consideration in VLSI design, because of the closer interwire spacing and the circuit operation at higher frequencies. Our neural network is composed of N M L digital neurons with one-bit output and seven-bit input for the N-net-M-track-2L-layer problem using a set of integer parameters, which is greatly suitable for the implementaion on digital technology. The digital neural network directly seeks a routing solution of satisfying the routing constraint and the crosstalk constraint simultaneously. The heuristic methods are effectively introduced to improve the convergence property. The performance is evaluated through solving 10 benchmark problems including Deutsch difficult example in 2-10 layers. Among the existing neural networks, the digital neural network first achieves the lower bound solution in terms of the number of tracks in any instance. Through extensive simulation runs, it provides the best maximum crosstalks of nets for valid routing solutions of the benchmark problems in multilayer channels.