Abstract
Parallelizing the execution phase of production systems requires careful management of rule interference to maintain serializability. This paper evaluates three architectural approaches—synchronous compiled tests, asynchronous compiled tests, and asynchronous locking—on shared-memory machines. Results indicate that asynchronous locking (Algorithm A3) provides the highest performance, though the overhead of ensuring correctness imposes a significant "performance tax," limiting speedups to approximately half of the theoretical maximum.
Introduction
Production systems, such as OPS5, are fundamental to many AI expert systems. These systems operate through a "match-execute" cycle: identifying rules that match current data, selecting one, and firing it. While the "match" phase has been successfully parallelized, the "execute" phase remains a significant bottleneck. Simultaneous rule execution introduces the risk of interference, where one rule's actions (e.g., deleting data) conflict with another's requirements. To maintain system reliability, parallel execution must be serializable—the final state must be equivalent to some valid serial execution of the same rules.
Architectural Approaches
The study evaluates three distinct algorithms based on a "1 Scheduler / $N-1$ Demons" model, as illustrated in the basic architecture for a four-processor system.
- Algorithm A1 (Synchronous Compiled Tests): The scheduler selects a batch of rule instantiations. Demons verify interference using pre-compiled Lisp functions derived from offline rule analysis. This approach is synchronous; all demons must complete their current batch before a new cycle begins.
- Algorithm A2 (Asynchronous Compiled Tests): This evolution of A1 removes the batching constraint. Demons pull from a global queue and check for interference against currently executing rules in real-time, reducing idle time caused by rule execution variance.
- Algorithm A3 (Asynchronous Locking): Instead of pre-compiled tests, A3 employs a dynamic locking scheme for data elements. It introduces a novel method for handling "negative conditions" (rules triggered by the absence of data) by utilizing the Rete match network to generate "pseudo-tokens" that lock the non-existence of specific facts.
Experimental Results
The algorithms were benchmarked using Toru-Waltz-N, a modified version of Waltz’s constraint propagation algorithm optimized for high rule concurrency. The serial baseline execution time was 12.79 seconds, with a theoretical maximum hardware speedup of 10.7x in the absence of serialization checks.
As shown in the performance data, Algorithm A3 emerged as the most effective, achieving a maximum speedup of 5.70x. Algorithm A2 followed with 4.64x, while the synchronous A1 lagged significantly at 2.80x. The results highlight a "correctness tax": the overhead of ensuring serializability reduced the potential 10.7x speedup to approximately 5.7x.
Discussion and Conclusion
The performance gap between A1 and the asynchronous models (A2, A3) underscores the impact of "stragglers" in synchronous systems. By operating at the instantiation level rather than the rule level, these algorithms achieve higher concurrency. However, a fundamental limit exists; interference checking often requires execution within a "critical region," creating a serial bottleneck.
The study concludes that while asynchronous locking is superior for complex AI logic, the scheduler eventually becomes a bottleneck as processor counts increase. Future research should explore parallelizing the interference checks themselves or employing compilation techniques to distribute the locking process across multiple independent streams.
Summary updated