This paper presents measurements made on several large OPS5 production systems (rule-based systems). The complete set of measurements is divided into three parts. The first part consists of measurements on the textual structure of the production system programs. The second part consists of measurements on the compiled form of the productions, and the third part consists of run-time measurements on the production system programs. The measurements are essential to the design of high-performance interpreters for production systems. The measurements are also designed to help explore the role of parallelism in execution of production system programs.

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.

Rule-based systems, on the surface, appear to be capable of exploiting large amounts of parallelism—it is possible to match each rule to the data memory in parallel. In practice, however, we show that the speed-up from parallelism is quite limited, less than 10-fold. 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 required by the 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 10-fold 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 bus-based shared-memory multiprocessor with 32-64 processors. Using such a multiprocessor (with individual processors working at 2 MIPS), it is possible to obtain execution speeds of about 3800 rule-firings/sec. This speed is significantly higher than that obtained by other proposed parallel implementations of rule-based systems.