Introduction
Traditional AI production systems, such as OPS5, typically operate on a sequential inference cycle: matching rules against data, selecting a single rule for conflict resolution, and updating the database. While parallelizing the "match" phase has been a common research focus, the remaining phases often create significant bottlenecks. This paper addresses the challenges of firing multiple rules simultaneously, specifically focusing on the Compatibility Problem (data dependencies) and the Convergence Problem (maintaining logical correctness in problem-solving strategies).
The MCMR and RUBIC Models
The authors introduce the Multiple-Contexts-Multiple-Rules (MCMR) model to overcome these hurdles. This two-layered approach analyzes programs at both the rule level and the context level. At the rule level, data dependency analysis creates a parallelism matrix to ensure safe execution. At the context level, the system identifies which high-level tasks can run in parallel based on their control flow and reachable states.
To implement this, the researchers developed the RUBIC Parallel Inference Model. Unlike traditional sequential cycles, RUBIC is an asynchronous, message-driven framework consisting of seven phases, including Match, Local/Context-wide Conflict Resolution, and Compatibility Determination. A key insight is that for "converging" contexts—where any firing order leads to the same goal—conflict resolution can be bypassed entirely, allowing all matched rules to fire immediately.
Experimental Methodology
The system was implemented on an Intel iPSC/2 hypercube, a distributed-memory multiprocessor. Rules and Working Memory Elements (WMEs) were distributed across nodes, with updates handled via asynchronous message passing to minimize idle time. The model was evaluated using six benchmark programs, such as "Tournament" (scheduling), "Toru-Waltz16" (computer vision), and "Hotel" (operations modeling), representing a variety of scales and inherent parallelism levels.
Key Results and Performance
The MCMR model demonstrated significant performance improvements. In logic-level simulations with idealized hardware, speedups ranged from 3.18x to 19.45x. On the physical 8-node hypercube, the system achieved notable gains for real-world benchmarks.
As shown in the hardware tests, the "Cafeteria" program achieved a 3.67x speedup, while the "Hotel" program reached 3.79x. Most importantly, the parallel executions consistently reached the same correct solutions as sequential versions, validating the underlying MCMR logic and its ability to maintain program integrity.
Conclusion and Future Work
While the results confirm the efficacy of context-based parallelism on hypercube architectures, some limitations remain. Memory constraints on the iPSC/2 limited the testing of larger benchmarks, and rule partitioning was largely a manual process. Future research will focus on automating rule distribution using simulated annealing to better balance computational loads and further reduce communication overhead in larger-scale parallel systems.
Summary updated