Abstract
Traditional rule-based production systems, such as OPS5, are fundamentally constrained by a serial execution cycle that relies on global synchronization. This paper, originally presented at AAAI-91, proposes a shift toward parallel rule-firing through an asynchronous "fire-when-ready" policy. By utilizing an augmented agenda manager and localized locking mechanisms, the system achieves significant speedups on multiprocessor hardware by replacing rigid conflict resolution with heuristic-driven scheduling and functional accuracy.
Introduction
In the early 1990s, the transition of Artificial Intelligence (AI) systems to parallel hardware was hindered by the inherent design of production system interpreters. The standard execution cycle—consisting of Match, Conflict Resolution, and Act—requires a global synchronization point. In this model, every processor must wait for the slowest rule match to complete before a single "best" rule is selected for execution. This "synchronization tax" creates a significant bottleneck, often leaving processors idle and limiting the scalability of rule-based engines. This paper explores a departure from this serial paradigm, proposing a system that prioritizes asynchronous execution and localized control.
The Problem: The Synchronization Bottleneck
The primary obstacle to parallelism in systems like OPS5 is the Conflict Resolution step. Because the system must compare all eligible rules to pick a winner, it enforces a global barrier. Furthermore, traditional programming idioms used in these systems, such as "mode-changing" rules (where a single flag is updated to transition the system from one phase of logic to another), are inherently serial. In a parallel environment, a single mode-change can force the entire Rete match network to retract and re-assert thousands of partial matches, consuming a disproportionate amount of runtime.
Proposed Solution: The "Fire-When-Ready" Policy
The author introduces a parallel rule-firing system implemented in TopCL (a parallel Common Lisp) that replaces global synchronization with a "fire-when-ready" policy. Under this policy, rules are allowed to execute as soon as their conditions are satisfied, without waiting for a global conflict set to be finalized.
To manage this asynchrony, the paper proposes an Augmented Agenda Manager that handles three distinct levels of control:
- Dynamic Scheduling: Rather than firing rules at random, the system employs heuristics to prioritize rules that generate "triggering data." These are data elements likely to enable a cascade of other rules, thereby increasing the overall work available to the processors.
- Heuristic Control: In scenarios where multiple rules might solve the same subproblem, the system adopts a "Parallel Exploration of Alternatives." Instead of selecting one rule, the system fires several concurrently. This relies on the concept of functional accuracy, where the system is designed to converge on a correct solution even if some intermediate steps are redundant or slightly suboptimal.
- Algorithmic Control: To handle sequencing (e.g., ensuring Phase A completes before Phase B), the author moves mode-switching logic out of the rule-matching engine and into the agenda manager. By using meta-level specifications, the system avoids the massive overhead of updating the Rete network for simple control-flow changes.
Data Consistency and Locking
To maintain integrity without global synchronization, the system implements a read/write locking mechanism on individual memory elements. This ensures that two rules do not modify the same data simultaneously in a way that leads to inconsistency. Evaluation showed that this locking mechanism is highly efficient, adding only approximately 1% to the total rule execution time.
Experimental Results
The system was evaluated using the Toru-Waltz benchmark, a parallel implementation of the Waltz line-labeling algorithm. Key findings include:
- Scalability: The system achieved speedups of 8 to 10 times over serial execution on a 16-processor Sequent Symmetry multiprocessor.
- Latency Reduction: The "fire-when-ready" policy reduced conflict set latency by factors ranging from 1.5 to an order of magnitude.
- Overhead Elimination: In traditional OPS5, mode-changing rules accounted for up to 25% of total runtime. The meta-level sequencing method effectively eliminated this overhead.
Conclusion and Future Work
The research demonstrates that the rigid conflict resolution of traditional production systems is not a requirement for complex AI tasks. By partitioning the conflict set and embracing asynchronous execution, systems can achieve high utilization on parallel hardware. While the current locking mechanism has limitations regarding "negative references" (checking for the absence of data), and scheduling heuristics require further tuning for fine-grained rule sets, the paper provides a robust framework for the next generation of parallel rule-based AI.
Summary updated