This paper presents an algorithm for finding optimum routings for interconnection paths in a channel between two parallel rows of circuit cells. A routing algorithm thus need only avoid overlapping collinear horizontal segments of different nets, and avoid overlapping collinear vertical segments, to achieve a physically acceptable routing. The algorithm, although based on branch and bound, has provided optimum routings for circuits with 50 to 60 nets in a minute or two of computing.
All Science Journal Classification (ASJC) codes
- Computer Science Applications
- Control and Systems Engineering
- Electrical and Electronic Engineering
- Modeling and Simulation