A subjective review of compaction (tutorial session)

ABSTRACT

Compaction is the CAD tool used to pack rough sketches or symbolic diagrams to produce IC layouts. Manual compaction is tedious, time-consuming, and error-prone; automated compaction tools can greatly shorten the layout design cycle. This paper reviews the historical background and the major developments in the field of compaction, emphasizing subjective evaluations rather than objective descriptions. The major approaches covered are constraint-graph, shear-line, and virtual-grid. Various ideas for further reducing chip area (such as inserting jog points, shortening wires, dense packing, 2-D compaction, and interactive tools) are also discussed. Because of the critical role of efficient algorithms in VLSI CAD systems, analyses of computational complexities are also included.

REFERENCES

• 1: Y. E. Cho , A. J. Kroenjak , D. E. Stockton, FLOSS: an approach to automated layout for high-volume designs, Papers on Twenty-five years of electronic design automation, p.138-141, June 1988 [doi>10.1145/62882.62895]
• 2: Dunlop, A. E. ~SLIP: Symbolic Layout of Integrated Circuits with Compaction~, Computer- Aided Design, November 1978, pp. 387-391.
• 3: Sheldon B. Akers , James M. Geyer , Donald L. Roberts, IC mask layout with a single conductor layer, Proceedings of the 7th workshop on Design automation, p.7-16, June 22-25, 1970, San Francisco, California, United States [doi>10.1145/800160.805107]
• 4: Auerbach, R. Oral presentation at the Design Automation Workshop, East Lansing, Michigan, October 1979.
• 5: Do, J.; and Dawson, W. ~SPACER If: A Well- Behaved IC Layout Compactor~, Proceedings of VLSI 85 International Conference, 1985.
• 6: Williams, J. D. ~STICKS -Graphics Editor for High-Level LSI Design', Proceedings of National Computer Conference, 1978, pp. 289- 295.
• 7: Hsueh, M. Y. ~Symbolic Layout and Compaction of Integrated Circuits~, U. C. Berkeley, UCB/ERL Report, M79/80, 1979.
• 8: Mathews, R.; and Saxe, T. Private communication, 1984.
• 9: H. S. Baird , Y. E. Cho, An artwork design verification system, Proceedings of the 12th conference on Design automation, p.414-420, January 1975
• 10: Baird, H. S. ~Fast Algorithms for LSI Artwork Analysis~, Journal of Design Automation and Fault-Tolerant Computing, 1978, pp. 179- 209.
• 11: Bentley, J. L.; Haken, D.; and Hon, R. W., ~Fast Geometric Algorithms for VLSI Tasks~, Proceedings of IEEE Computer Conference, 1980, pp. 88-92.
• 12: Thomas G. Szymanski , Christopher J. Van Wyk, Space efficient algorithms for VLSI artwork analysis, Proceedings of the 20th conference on Design automation, p.734-739, June 27-29, 1983, Miami Beach, Florida, United States
• 13: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 14: Tarjan, R. E. "Depth First Search and Linear Graph Algorithms~, SIAM Journal on Computing, 1972, pp. 146-160.
• 15: Maier, D. ~An Ei~cient Method for Storing Ancestor Information in Trees~, SIAM Journal on Computing, November 1979, pp. 599-617.
• 16: CustomPlus User's Manual, Calma Company, 1985.
• 17: 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
• 18: Christopher Kingsley, A hiererachical, error-tolerant compactor, Proceedings of the 21st conference on Design automation, p.126-132, June 25-27, 1984, Albuquerque, New Mexico, United States
• 19: 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
• 20: Schlag, M.; Liao, Y. Z.; and Wong, C. K. "An Algorithm for Optimal Two-Dimensional Compaction of VLSI Layouts", Integration, 1983, pp.179-209.
• 21: Hajimu Mori, Interactive compaction router for VLSI layout, Proceedings of the 21st conference on Design automation, p.137-143, June 25-27, 1984, Albuquerque, New Mexico, United States
• 22: Walter S. Scott , John K. Ousterhout, Plowing: Interactive stretching and compaction in magic, Proceedings of the 21st conference on Design automation, p.166-172, June 25-27, 1984, Albuquerque, New Mexico, United States
• 23: Neil Weste, Virtual grid symbolic layout, Proceedings of the 18th conference on Design automation, p.225-233, June 29-July 01, 1981, Nashville, Tennessee, United States
• 24: Boyer, D.G.; ~id Weste, N. "Virtual Grid. Compaction Using the Most Recent Layers Algorithm~, Proceedings of ICCAD, 1983, pp. 92-93.
• 25: Liao, Y.; and Wong, C. K. ~An Algorithm to Compact VLSI ',~ymbolic Layout with Mixed Constraints", IEEE Transactions on Computer- Aided Design of Circuits and Systems, April 1983, pp. 62-69,
• 26: Ousterhout, J, K. ~Coraer Stitching: A Data- Structuring Teclhnique for VLSI Layout Tools", IEEE Transac~tions on Computer-Aided Design of Circubls and Systems, January 1984, pp. 87-100.
• 27: Wolf, W.; Mathews, R.; Newkirk, J.; and Dutton, R. ~Two-Dimensional Compaction Strategies~, Proceedings olt" ICCAD, 1983, pp. 90-91
• 28: Wolf, W. H. ~Two-Dimensional Compaction Strategies", PhD Thesis, Stauford University, 1984.
• 29: A. E. Dunlop, SLIM-the translation of symbolic layouts into mask data, Proceedings of the 17th conference on Design automation, p.595-602, June 23-25, 1980, Minneapolis, Minnesota, United States [doi>10.1145/800139.804592]
• 30: Auerbach, R.; Lin, B.; and Elsayed, E. ~Layout Aid for the Design of VLSI Circuits", Computer-Aided Desiign, September 1981, pp. 271- 276.
• 31: Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984
• 32: Mathews, R.; Newkirk, J.; and Eichenberger, P. ~A Target Lang~Lage for Silicon Compilers", Proceedings of IEEE COMPCON, 1982, pp. 349- 353.
• 33: Mikhail Lotvin , Belinda Juran , Reeni Goldin, Amoeba: A symbolic VLSI layout system, Proceedings of the 21st conference on Design automation, p.294-300, June 25-27, 1984, Albuquerque, New Mexico, United States
• 34: Rothermel, H.-J.; and Mlynski, D. "Automatic Variable-Width Routing for VLSr', IEEE Transactions on Computer -Aided Design, October 1983, pp. 271-284.
• 35: Ulrich, L. ~A Min-Cut Placement Algorithm for General Cell Assemblies Based on A Graph Representation~, Proceedings of the 16th Design
• 36: Charles H. Ng, A symbolic-interconnect router for custom IC design, Proceedings of the 21st conference on Design automation, p.52-58, June 25-27, 1984, Albuquerque, New Mexico, United States
• 37: Dunlop, A. E. Private communication, 1985.
• 38: Kingsley, C.; aud Rowson, J. Priwte communication, 1985.
• 39: Mosteller, R. C. ~REST, A Leaf Cell Design System~, VLSI 81, Academic Press, 1981, pp.163- 172.
• 40: Weste, N. Private communication, 1985.
• 41: Ackland, B. and Weste, N. ~An Automatic Assembly Tool for Virtual Grid Symbolic Layout", VLSI 83, pp.457-466.
• 42: Wolf, W. ~An Experimentall Comparison of 1- D Compaction Algorithms~, Chapel Hill VLSI Conference, 1985.
• 43: Wolf, W. Private communical;ion, 1985.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS

  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  J. Computer Applications

General Terms:
Design, Performance, Theory