A neural network model for multilayer topological via minimization in a switchbox

This paper presents a new approach using a neural network model for the multilayer topological via minimization problem in a switchbox. Our algorithm consists of three steps: 1) dividing multiterminal nets into two-terminal nets, 2) finding a layer-assignment of the two-terminal nets by a neural network model so as to minimize the number of unassigned nets, and 3) embedding one via for each unassigned net by Marek-Sadowska's algorithm. The neural network model is composed of M x M processing elements to assign N two-terminal nets in an M-layer switchbox. The performance of our algorithm is verified by 15 benchmark problems where it can find optimum or near-optimum solutions. In the two-layer Burstein's switchbox, our algorithm finds a 15-via solution while the best known solution requires 20 vias.