WEAVER: a knowledge-based routing expert

ABSTRACT

In this paper we describe WEAVER, a channel/switch-box knowledge-based routing program. WEAVER considers all the important routing metrics such as 100% routability, minimum routing area, minimum wire length, and minimum number of vias simultaneously. It allows pre-routed nets, and user interaction throughout the entire routing process. It also relaxes unnecessary constraint of assigning different layers to different directions, the constraint imposed by all of the current channel and switch-box routers. WEAVER is a grid-based router that utilizes two interconnection layers and can be easily expanded to route any shape routing area such as 'T' or '+'. Implemented in OPS5, a production system language, WEAVER routinely produces routings requiring less area than routers that focus on a single routing metric.

REFERENCES

• 1: Hightower D.H., The Interconnection Problem- A Tutorial IEEE Computer Society, 1980, pp. 252-272.
• 2: Breuer, M. A., Design Automation of Digital Systems, Prentice-Hall, Vol. 1, 1972.
• 3: Lee, C. Y., "An Algorithm for Path Connections and its Application", IRE Transactions on Electronic Computers, September 1961, pp. 346-365.
• 4: Persky, G., D. N. Oeutsch, and D. G. Schweikert, "LTX- A minicomputer-based System for Automatic LSI Layout", Journal of Design Automation and Fault- Tolerant Computing, VOJ. 1, No. 3, May 19;'7, pp. 217.255.
• 5: Yoshimura, T., and E. S. Kuh, "Efficient Algorithms for Channel Routing", IEEE Transactions on Computer- Aided Design of integrated Circuits and Systems, Vol, CAD. 1, No. 1, January 1982, pp. ;!5-35.
• 6: Ronald L. Rivest , Charles M. Fiduccia, A “greedy” channel router, Proceedings of the 19th conference on Design automation, p.418-424, January 1982
• 7: Gordon T. Hamachi , John K. Ousterhout, A switchbox router with obstacle avoidance, Proceedings of the 21st conference on Design automation, p.173-179, June 25-27, 1984, Albuquerque, New Mexico, United States
• 8: Burstein, M., and R. Pelavin, "Hierarchical Wire Routing" IEEE Transactions on Computer-Aided Design of Integrated Circuits and systems, Vol. CAD-2, No. 4, October 1983, pp. 223.234.
• 9: Soukup, j., "Global Router", Journal of Digital Systems, VoI. iV, No. 1, Spring 1980, pp. 59-69.
• 10: Barr, A., and E.A. Feigenbaum (~.<litors.), The Handbook of Artificial Intelligence (vols 1, 2, 3), Los Altos, CA: Kaufmann, 1981,1982.
• 11: Frederick Hayes-Roth , Donald A. Waterman , Douglas B. Lenat, Building expert systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1983
• 12: Lee D. Erman , Frederick Hayes-Roth , Victor R. Lesser , D. Raj Reddy, The Hearsay-II Speech-Understanding System: Integrating Knowledge to Resolve Uncertainty, ACM Computing Surveys (CSUR), v.12 n.2, p.213-253, June 1980 [doi>10.1145/356810.356816]
• 13: Balzer, R., L.D. Erman, P. London, and C. William, "Hearsay-Ill: A Domain Independent Framework for Expert Systems", First Annual National Conference on Artificial Intelligence1980, pp. 108-110.
• 14: Kramer, A., "Senior mask designer, Intel Corporation, Private Conversation".
• 15: Wilde, D. K., "Senior Engineer, Intel Corporation, Private Conversation".
• 16: Forgy, C.L., "OPS5 User's Manual", Tech. report, Department of Computer Science, Carnegie:Mellon University, July 1981.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.5 Programming Languages and Software

          Nouns: OPS5

General Terms:
Algorithms, Design, Languages, Measurement, Performance, Theory