Reducing Channel Density in Standard Cell Layout
- 1 January 1983
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 263-269
- https://doi.org/10.1109/dac.1983.1585660
Abstract
The problem of global routing in standard cell layouts so as to minimize total channel density is considered. A sub-problem of this, called the linear net routing problem (LNRP), is defined and is argued to be the key to a successful solution to the general problem. A polynomial-time heuristic for LNRP is presented and its behavior analyzed. In particular, it is proven that the heuristic can produce results as bad as, but no worse than, 50% over the optimal.Keywords
This publication has 9 references indexed in Scilit:
- Performance results of the simplex algorithm for a set of real-world linear programming modelsCommunications of the ACM, 1982
- 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
- Polynomial algorithms in linear programmingUSSR Computational Mathematics and Mathematical Physics, 1980
- CALMOS : A Portable Software System for the Automatic and Interactive Layout of MOS/LSIPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- An Analysis of Several Heuristics for the Traveling Salesman ProblemSIAM Journal on Computing, 1977
- A “Dogleg” channel routerPublished by Association for Computing Machinery (ACM) ,1976
- Automatic layout of low-cost quick-turnaround random-logic custom LSI devicesPublished by Association for Computing Machinery (ACM) ,1976