High-speed implementations of rule-based systems

ABSTRACT

Rule-based systems are widely used in artificial intelligence for modeling intelligent behavior and building expert systems. Most rule-based programs, however, are extremely computation intensive and run quite slowly. The slow speed of execution has prohibited the use of rule-based systems in domains requiring high performance and real-time response. In this paper we explore various methods for speeding up the execution of rule-based systems. In particular, we examine the role of parallelism in the high-speed execution of rule-based systems and study the architectural issues in the design of computers for rule-based systems. Our results show that contrary to initial expectations, the speed-up that can be obtained from parallelism is quite limited, only about tenfold. The reasons for the small speed-up are: (1) the small number of rules relevant to each change to data memory; (2) the large variation in the processing requirements of relevant rules; and (3) the small number of changes made to data memory between synchronization steps. Furthermore, we observe that to obtain this limited factor of tenfold speed-up, it is necessary to exploit parallelism at a very fine granularity. We propose that a suitable architecture to exploit such fine-grain parallelism is a shared-memory multiprocessor with 32-64 processors. Using such a multiprocessor, it is possible to obtain execution speeds of about 3800 rule-firings/set. This speed is significantly higher than that obtained by other proposed parallel implementations of rule-based systems.

REFERENCES

• 1: John R. Anderson, The Architecture of Cognition, Harvard University Press, Cambridge, MA, 1983
• 2: William C. Athas , Charles L. Seitz, Multicomputers: Message-Passing Concurrent Computers, Computer, v.21 n.8, p.9-24, August 1988 [doi>10.1109/2.73]
• 3: BROOKS, R., AND LUM, R. Yes, an SIMD machine can be used for AI. In International Joint Conference on Artificial Intelligence (Los Angeles, Aug. 1985), pp. 73-79.
• 4: Lee Brownston , Robert Farrell , Elaine Kant , Nancy Martin, Programming expert systems in OPS5: an introduction to rule-based programming, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1985
• 5: FORGY, C., GUPTA, A., NEWELL, A., AND WEDIG, R. Initial assessment of architectures for production systems. In National Conference for Artificial Intelligence (Austin, Tex., Aug. 1984). AAAI- 1984, pp. 116-120.
• 6: FORGY, C. L. Rete: A fast algorithm for the many pattern/many object pattern match problem. Artif. Intell. 19, 1 (Sept. 1982), 17-37.
• 7: FORGV, C. L. The 0PS83 Report. Tech. Rep. CMU-CS-84-133, Carnegie-Mellon Univ., Pittsburgh, May 1984.
• 8: GRIESMER, J. H., HONG, S. J., KARNAUGH, M., KASTNER, J. K., SCHOR, M. I., ENNIS, R. L., KLEIN, D. A., MILLIKEN, K. R., AND VAN WOERKOM, I-~. M. YES/MVS: A continuous real time expert system. In National Conference on Artificial Intelligence (Austin, Tex., Aug. 1984). AAAI- 1984, pp. 130-136.
• 9: GUeTA, A. Implementing OPS5 production systems on DADO. In International Conference on Parallel Processing. IEEE, New York, 1984, pp. 83-91.
• 10: Anoop Gupta, Parallelism in production systems, 1986
• 11: GUPTA, A., AND TAMBE, M. Suitability of message passing computers for implementing production systems. In National Conference on Artificial Intelligence (St. Paul, Minn., Aug. 1988). AAAI- 88, pp. 687-692.
• 12: HALEY, P., KOWALSKI, J., MCDERMOTT, J., AND McWHORTER, R. PTRANS: A rule-based management assistant. Tech. Rep., Carnegie-Mellon Univ., Pittsburgh, 1983.
• 13: HENNESSY, J. L., JouPPI, N., PRZYBYLSKI, S., ROWEN, C., AND GROSS, T. The MIPS machine. In Computer Conference, (Feb. 1982).
• 14: W. Daniel Hillis , Guy L. Steele, Jr., Data parallel algorithms, Communications of the ACM, v.29 n.12, p.1170-1183, Dec. 1986 [doi>10.1145/7902.7903]
• 15: HILLYER, B. K., AND SHAW, D. E. Execution of OPS5 production systems on a massively parallel machine. Tech. Rep., Columbia Univ., Sept. 1984.
• 16: IRANI, K. B., AND ONVUKSEL, I. H. A closed-form solution for the performance analysis of multiple-bus multiprocessor systems. IEEE Trans. Comput. C-33, 11 (Nov. i984), 1004-1012.
• 17: KAHN~ G., AND McDERMOTT, J. The MUD system. In First Conference on Artificial Intelligence Applications, IEEE Computer Society and AAAI, Dec. 1984.
• 18: KATSUKi D., ET AL. Pluribus--An operational fault-tolerant multiprocessor. Proc. IEEE 66, 10 (Oct. 1978).
• 19: R. H. Katz , S. J. Eggers , D. A. Wood , C. L. Perkins , R. G. Sheldon, Implementing a cache consistency protocol, Proceedings of the 12th annual international symposium on Computer architecture, p.276-283, June 17-19, 1985, Boston, Massachusetts, United States
• 20: KIM, J., MCDERMOTT, J., AND SIEWlOREK, D. TALIB: A knowledge-based system for IC layout design, in National Conference on Artificial Intelligence (Washington, D.C., Aug. 1983). AAAI- 1983, pp. 197-201.
• 21: T. J. Kowalski , D. E. Thomas, The VLSI Design Automation Assistant: Prototype system, Proceedings of the 20th conference on Design automation, p.479-483, June 27-29, 1983, Miami Beach, Florida, United States
• 22: John Edwin Laird, Universal subgoaling, 1984
• 23: LAIRD, J. E. Soar User's Manual. (4th ed.) Xerox PARC, 1986.
• 24: LEHR, T. F. The implementation of a production system machine. In Hawaii International Conference on System Sciences (Honolulu, Jan. 1986), pp. 177-186.
• 25: MARCUS, S., MCDERMOTT, J., ROCHE, R., THOMPSON, T., WANG, T. AND WOOD, G. Design Document for VT. Carnegie-Mellon Univ., Pittsburgh, 1984.
• 26: MCDERMOTT, J. RI: A rule-based configurer of computer systems. Tech. Rep. CMU-CS-80-119, Carnegie-Mellon Univ,, Pittsburgh, April 1980.
• 27: MCDERMOTT, J. RI: A rule-based configurer of computer systems. Artif. Intell. 19, 1 (1982), 39-88.
• 28: MCDERMOTT, J. XSEL: A computer salesperson's assistant. In Machine intelligence, D. Michie, J. E. Hayes, and Y. H. Pao, eds., Horwood, 1982.
• 29: MmANKER, D. P. TREAT: A new and efficient match algorithm for AI production systems. Ph.D. dissertation, Columbia Univ., New York, Jan. 1987.
• 30: NAYAK, P., GUPTA, A., AND ROSENBLOOM, P. Comparison of the Rete and Treat production matchers for SOAR: A summary. In National Conference on Artificial Intelligence (St. Paul, Minn., Aug. 1988). AAAI-88, pp. 693-698.
• 31: NEWELL, A. HARPY, production systems and human cognition. Tech. Rep. CMU-CS-78-140, Carnegie-Mellon Univ., Pittsburgh, Sept. 1978.
• 32: Allen Newell, Human Problem Solving, Prentice-Hall, Inc., Upper Saddle River, NJ, 1972
• 33: OFLAZER, K. Parallel execution of production systems. In International Conference on Parallel Processing (Aug. 1984). IEEE, New York, 1984, pp. 92-100.
• 34: K. Oflazer, Partitioning in parallel processing of production systems, Carnegie Mellon University, Pittsburgh, PA, 1987
• 35: PATTERSON, D. A., AND SEQUIN, C. H. A VLSI RISC. Computer 9 (1982).
• 36: QUINLAN, J. A comparative analysis of computer architectures for production system machines. In Hawaii International Conference on System Sciences (Honolulu, Jan. 1986), pp. 194-200.
• 37: RADIN, G. The 801 minicomputer, IBM J. Res. Dev. 27 (May 1983).
• 38: REED, B., JR. The ASPRO parallel inference engine (P.I.E.): A real time production rule system. Goodyear Aerospace, 1985.
• 39: Paul Simon Rosenbloom, The chunking of goal hierarchies: a model of practice and stimulus-response compatibility, 1983
• 40: ROSENBLOOM, P. S., LAIRD, J. E., MCDERMOTT, J., NEWELL, A., AND ORCIUCH, E. R1-Soar: An experiment in knowledge-intensive programming in a problem-solving architecture. In IEEE Workshop on Principles of Knowledge Based Systems, 1984.
• 41: Larry Rudolph , Zary Segall, Dynamic decentralized cache schemes for mimd parallel processors, Proceedings of the 11th annual international symposium on Computer architecture, p.340-347, January 1984
• 42: SCHREINER, F., AND ZIMMERMAN, G. Pesa-l--A parallel architecture for production systems. In International Conference on Parallel Processing (Pheasant Run, Ill., Aug. 1987), pp. 166-169.
• 43: SHAW, D. E. NON-VON's applicability to three AI task areas. In International Joint Conference on Artificial Intelligence (Los Angeles, Aug. 1985), pp. 61-72.
• 44: STOLFO, S. J. Five parallel algorithms for production system execution on the DADO machine. In National Conference on Artificial Intelligence (Austin, Tex., Aug. 1984). AAAI-1984, pp. 300-307.
• 45: STOLFO, S. J., AND SHAW, D. E. DADO: A tree-structured machine architecture for production systems. In National Conference on Artificial Intelligence (Pittsburgh, Pa., Aug. 1982). AAAI- 1982, pp. 242-246.
• 46: TALUKDAR, S. i., CARDOZO, E., LEAO, L., BANARES, R., AND JOOBBANI, R. A system for distributed problem solving. In Workshop on Coupling Symbolic and Numerical Computing in Expert Systems (Aug. 1985).
• 47: TENORIO, M. F. M., AND MOLDOVAN, D. |. Mapping production systems in multiprocessors. In International Conference on Parallel Processing (Pheasant Run, Ill., Aug. 1985). IEEE, New York, 1985, pp. 56-62.
• 48: Shinji Umeyama , Koichiro Tamura, A parallel execution model of logic programs, Proceedings of the 10th annual international symposium on Computer architecture, p.349-355, June 13-17, 1983, Stockholm, Sweden
• 49: David L. Waltz, Applications of the connection machine, Computer, v.20 n.1, p.85-97, Jan. 1987 [doi>10.1109/MC.1987.1663362]
• 50: A. W. Wilson, Jr., Hierarchical cache/bus architecture for shared memory multiprocessors, Proceedings of the 14th annual international symposium on Computer architecture, p.244-252, June 02-05, 1987, Pittsburgh, Pennsylvania, United States [doi>10.1145/30350.30378]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

  D. Software
  D.1 PROGRAMMING TECHNIQUES

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

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

          Nouns: OPS5

General Terms:
Algorithms, Design, Languages, Performance