A NEURAL-NETWORK APPROACH TO TOPOLOGICAL VIA-MINIMIZATION PROBLEMSLR946

Topological via-minimization (TVM) algorithms in two-layer channels based on the artificial neural network model are presented in this paper. TVM problems require not only assigning wires or nets between terminals without an intersection to one of two layers, but also a minimization of the number of vias, which are the single contacts of nets between two layers. The goal of our algorithms is to embed the maximum number of nets without an intersection. Two types of TVM problems are examined: split rectangular TVM (RTVM) problems and split circular TVM (CTVM) problems. Our algorithms require 3n processing elements for the n-net split RTVM problems, and 5n processing elements for the n-net split CTVM problems. The algorithms were verified by solving seven problems with 20 to 80 nets. The algorithms can be easily extended for more-than-two-layer problems.