CIS: A Massively Concurrent Rule-Based System

Guy E. BlellochAAAI 1986

Introduction

In 1986, the MIT AI Lab introduced a radical departure from the traditional "expert systems" of the era. While systems like Mycin or OPS5 relied on serial processors and complex conflict resolution to manage rule firing, Guy Blelloch’s Concurrent Inference System (CIS) treated rules as a massive, static circuit. By compiling rules into an Activity Flow Network (AFN) and executing them on the 65,536-processor Connection Machine, CIS achieved the ability to process up to 100,000 rules with global inference steps taking less than two seconds.

The Serial Bottleneck in Expert Systems

During the mid-1980s, rule-based expert systems faced a significant scaling wall. The standard architecture maintained a strict separation between the "inference engine" (the execution logic) and the "rule set" (the knowledge base). This design was inherently serial: the system would scan data, identify matching rules, and apply a conflict resolution strategy to select a single rule to fire. As knowledge bases grew to tens of thousands of rules, this serial bottleneck made systems increasingly sluggish. CIS was designed to bypass this bottleneck by implementing logic using a "circuit-level" model of concurrency.

The Activity Flow Network (AFN)

The core innovation of CIS is the Activity Flow Network. Instead of treating a rule as a line of code, CIS represents it as a collection of nodes and links in a static graph.

  1. Compilation: Rules are compiled into a static network at compile time. At runtime, there is no separate inference engine; the network itself performs the computation.
  2. Simple Nodes: The network utilizes five basic node types (input, output, max, min, and sum) and two link types (inhibitory and excitatory), functioning similarly to logic gates.
  3. AFL-1 Language: Blelloch introduced AFL-1, a high-level language for defining these networks and organizing nodes into hierarchical groups.
The Animal Example network topology showing rule and parameter groups.

System Architecture and Inference

CIS was implemented on the Connection Machine, a SIMD (Single Instruction, Multiple Data) supercomputer. Each node and link in the AFN is mapped to an individual processor, enabling massive parallelism.

The system employs Dual-Flow Inference:

  • Forward Chaining: Certainty values flow from premises to conclusions.
  • Backward Chaining: "Want-to-know" activity flows from goals back to premises, allowing the system to dynamically prioritize questions for the user based on current hypotheses.
High-level architecture of the CIS system interacting with a host computer.

Key Results and Insights

The most profound insight of CIS is that symbolic logic can be reduced to activity flowing through a static circuit. By shifting complexity to compile-time, the runtime becomes fast and predictable. Unlike other parallel systems, CIS allows rules to fire simultaneously without conflict; if multiple rules reach the same conclusion, the system simply takes the maximum of their certainty values.

Empirical results demonstrated the system's efficiency:

  • Scale: Capable of handling 100,000 rules.
  • Speed: A global inference step—the time for a signal to propagate through the entire rule set—took less than two seconds.
  • Throughput: On a 64K-processor Connection Machine, a single update cycle (afl-step) took only 0.05 seconds for a network with 2 million links.

Limitations and Conclusion

Despite its speed, CIS involves trade-offs. The static nature of the network makes it difficult to create new object instances dynamically; maximum allocations must be determined at compile time. Additionally, the system is memory-intensive, requiring a massive number of processors, and is not suited for high-precision floating-point arithmetic. Nevertheless, CIS proved that massively parallel hardware could eliminate the traditional inference bottleneck, paving the way for real-time interaction with massive knowledge bases.

Summary updated

BibTeX
@inproceedings{blelloch1986cis,
  author = {Guy E. Blelloch},
  title = {{CIS: A Massively Concurrent Rule-Based System}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
}

Loading related content...

Figure