A neural network approach to topological via-minimization problems
- 1 June 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 12 (6) , 770-779
- https://doi.org/10.1109/43.229751
Abstract
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 layersKeywords
This publication has 27 references indexed in Scilit:
- The constrained via minimization problem for PCB and VLSI designPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Fast algorithm for optimal layer assignmentPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- A Parallel Algorithm for Traffic Control Problems in Three-Stage Connecting NetworksJournal of Parallel and Distributed Computing, 1994
- Comparisons of seven neural network models on traffic control problems in multistage interconnection networksIEEE Transactions on Computers, 1993
- A parallel algorithm for channel routing problems (VLSI)IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1992
- A neural network model for finding a near-maximum cliqueJournal of Parallel and Distributed Computing, 1992
- A neural network parallel algorithm for clique vertex-partition problemsInternational Journal of Electronics, 1992
- Layer assignment problem for three-layer routingIEEE Transactions on Computers, 1988
- Finding a Maximum Planar Subset of a Set of Nets in a ChannelIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987
- Efficient Algorithms for Layer Assignment ProblemIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1987