Geometrical compaction in one dimension for channel routing

ABSTRACT

A channel router which is to be effective for general-purpose automatic routing must be able to use different sets of routing criteria priorities, in a controllable manner. We present an approach to channel routing with compaction in which channel compaction is adaptable to several routing criteria priorities. We show how overall channel routing performance can be improved by taking advantage of this versatility in channel compaction. We indicate some routing capabilities which cannot be effectively achieved by simply post-processing the output of a traditional gridded channel router. Our solution to this problem is outlined and some results obtained from our router are compared with those of other published channel routers.

REFERENCES

• Bur83: Michael Burstein , Richard Pelavin, Hierarchical channel router, Proceedings of the 20th conference on Design automation, p.591-597, June 27-29, 1983, Miami Beach, Florida, United States
• Che85: ellen, H.H., and Kuh, E.S., "A Variable-width Gridless Channel Router", Proc. ICCAD-85, pp. 304-306, 1985.
• Cie82: M. J. Ciesielski , E. Kinnen, An analytical method for compacting routing area in integrated circuits, Proceedings of the 19th conference on Design automation, p.30-37, January 1982
• Deu76: David N. Deutsch, A “Dogleg” channel router, Proceedings of the 13th conference on Design automation, p.425-433, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804843]
• Deu85: Dcutsch, D., "Compacted Channel Routing", Proc. ICCAD- 85, pp. 223-225, 1985.
• Hsu83: Chi-Ping Hsu, General river routing algorithm, Proceedings of the 20th conference on Design automation, p.578-583, June 27-29, 1983, Miami Beach, Florida, United States
• Ked83: Gershon Kedem , Hiroyuki Watanabe, Graph-optimization techniques for IC layout and compaction, Proceedings of the 20th conference on Design automation, p.113-120, June 27-29, 1983, Miami Beach, Florida, United States
• LaP80: LaPaugh, A., "Algorithms for Integrated Circuit Layout: an Analytic Approach", Ph.D. Thesis, MIT, 1980.
• Pre85: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• Riv82: Ronald L. Rivest , Charles M. Fiduccia, A “greedy” channel router, Proceedings of the 19th conference on Design automation, p.418-424, January 1982
• San84: Sangiovanni-Vincentelli, A.S., Santomauro, M., and Reed, J., "A New Gridless Channel Router: Yet Another Channel Router the Second (YACR-II)", Proc. ICCAD-84, pp. 72-75, 1984.
• Sch83: W. L. Schiele, Improved compaction by minimized length of wires, Proceedings of the 20th conference on Design automation, p.121-127, June 27-29, 1983, Miami Beach, Florida, United States
• Sou83: Soukup, J., "Routing on one layer - an algorithm and its implementation", Proceexlings 1983 IEEE International Conference on Computer Design, Port Chester, N.Y., pp 126-135, 1983.
• Szy85: Szymanski, T.G., "Dogleg Channel Routing is N-P- complete", IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, Vol. CAD-4, No. 1, pp. 31.40, 1985.
• Yos80: Yoshimum, T. and Kuh, E., "Efficient Algorithms for Channel Routing", U.C. Berkeley Electronics Research Laboratory Memo, No. M80/43, 1980.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
          Subjects: Placement and routing

Additional Classification:
  C. Computer Systems Organization

General Terms:
Design, Performance