Global wire routing in two-dimensional arrays
- 1 November 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 453-459
- https://doi.org/10.1109/sfcs.1983.23
Abstract
We examine the problem of routing wires on a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case "channel-width" needed to route an n × n array, and develop provably good heuristics for the general case. An interesting "rounding algorithm" for obtaining integral approximations to solutions of linear equations is used to show the near-optimality of single-turn routings in the worst-case.Keywords
This publication has 6 references indexed in Scilit:
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- Wire-routing machines—New tools for VLSI physical designProceedings of the IEEE, 1983
- The NP-completeness column: An ongoing guldeJournal of Algorithms, 1982
- New lower bound techniques for VLSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1981
- Two-dimensional stochastic model for interconnections in master slice integrated circuitsIEEE Transactions on Circuits and Systems, 1981
- Area-time complexity for VLSIPublished by Association for Computing Machinery (ACM) ,1979