Initial Assessment of Architectures for Production Systems

Charles Forgy, Anoop Gupta, Allen Newell, Robert G. WedigAAAI 1984

In the early 1980s, production systems—forward-chaining rule-based AI like OPS5—were the standard for building expert systems. However, their performance was a major hurdle for real-time applications. This 1984 study from Carnegie-Mellon University explores how to transition these systems from slow software implementations to high-performance hardware, aiming for speedups of two orders of magnitude.

The Bottleneck: The Match Phase

The primary computational challenge in production systems is the Match phase. In this stage, the system must continuously evaluate a large database of facts, known as "working memory," against thousands of "if-then" rules. As systems grew in complexity, software optimizations reached a plateau. The Production System Machine (PSM) project was initiated to identify hardware architectures capable of overcoming this speed deficit by analyzing the Rete match algorithm.

Methodology and Datasets

The researchers evaluated six diverse, real-world production systems to understand their operational characteristics. These systems ranged from configuration tools like R1 to experimental problem-solving architectures like SOAR, representing the state-of-the-art in AI programming at the time.

Table 1: Characteristics of the six production systems evaluated in the study, showing the scale of rules and conditions.

The assessment involved empirical measurement of these systems, simulations of various levels of parallelism (production, condition, and action levels), and architectural analysis comparing CISC and RISC designs across different hardware technologies.

The Parallelism Paradox

A central finding of the study is the "Parallelism Paradox." While it might seem intuitive that matching thousands of rules in parallel would yield massive gains, the researchers found that only a small subset of rules (averaging around 35) is typically affected by any single change in working memory.

Figure 1: Speedup vs. Number of Processors for three different production systems, demonstrating diminishing returns beyond 32–64 processors.

As shown in Figure 1, adding more than 32 to 64 processors results in diminishing returns. This is due to the sequential nature of the Rete algorithm and the fact that some rules take significantly longer to process than others, creating bottlenecks that massive parallelism cannot resolve.

Architectural Insights: Simplicity and Speed

The study highlights several key architectural insights for future AI hardware:

  • Scale Independence: The amount of work required (node activations) is largely independent of the total number of rules, as human programmers naturally modularize large problems into manageable sub-problems.
  • RISC Efficiency: Because Rete operations are simple but frequent, a Reduced Instruction Set Computer (RISC) architecture is 2x to 4x more efficient than complex (CISC) architectures by reducing clock cycles per instruction.
  • Device Technology: Moving from standard TTL/MOS to high-speed logic like Emitter-Coupled Logic (ECL) or GaAs provides an additional 4x boost.

Conclusion

By combining modest parallelism (5x–10x), RISC architecture (2x–4x), and advanced device technology (4x), the authors estimate a cumulative speedup of 40x to 160x over conventional uniprocessor software. While challenges like memory latency and design complexity remain, this work established that the path to high-performance AI lay in simple, fast processors rather than massive, complex parallel arrays.

Summary updated

BibTeX
@inproceedings{forgy1984initial,
  author = {Charles Forgy and Anoop Gupta and Allen Newell and Robert G. Wedig},
  title = {{Initial Assessment of Architectures for Production Systems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure