A neural network approach to topological via-minimization problems

Topological via-minimization (TVM) algorithms in two-layer channels based on the artificial neural network model are presented. TVM problems require not only assigning wires or nets between terminals to one of two layers without an intersection, but also minimizing the number of vias, which are the single contacts between the nets in the two layers. The goal of the algorithm 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. The 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 to problems with more than two layers