Channel Routing Algorithms for Overlap Models
- 1 January 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
- Vol. 4 (1) , 23-30
- https://doi.org/10.1109/tcad.1985.1270095
Abstract
We consider routing models that consist of L layers in which each layer can contain horizontal and vertical wires and in which up to k wires on different layers are allowed to run on top of each other. Within this overlap model we study the relationship between the channel width, the number of contact points, and the amount of overlap used for routing n two-terminal nets across a channel. For k ≤ [L/2] - 2 we show how to solve the channel routing problem using [d/k] + 1 tracks, which is only one track more than the optimal channel width. We extend this algorithm to values of k in the range [L/2] - 1 ≤ k ≤ [L/2] +1. We also present algorithms for the 3- and 4-layer model with double overlap that use fewer tracks than our general channel routing algorithm. All algorithms use O(n) contact points and can be implemented to run in O(n) time.Keywords
This publication has 5 references indexed in Scilit:
- Optimal Three-Layer Channel RoutingIEEE Transactions on Computers, 1984
- Efficient Algorithms for Channel RoutingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1982
- A “greedy” channel routerPublished by Association for Computing Machinery (ACM) ,1982
- Provably Good Channel Routing AlgorithmsPublished by Springer Nature ,1981
- A “Dogleg” channel routerPublished by Association for Computing Machinery (ACM) ,1976