Abstract
This paper introduces the concept of a Virtual Parallel Inference Engine, a framework designed to decouple high-level AI logic (the "knowledge level") from the low-level mechanics of parallel execution (the "control level"). By utilizing an object-oriented "Protocol of Inference," the researchers demonstrate that AI rule-bases can be optimized for diverse hardware architectures—ranging from distributed clusters to shared-memory multiprocessors—simply by swapping modular software "mixins."
Introduction
In the late 1980s, parallel computing was considered a "difficult art." AI programmers faced a significant hurdle: to achieve high performance, they were forced to manually manage low-level concerns such as locks, task scheduling, and memory management. This resulted in AI logic being inextricably tangled with hardware-specific code.
Because parallel systems varied wildly in terms of "grain size" (the minimum task size worth parallelizing) and communication latency, code optimized for one machine often performed poorly on another. The authors sought a solution that would allow programmers to write AI rules once and then "plug in" different parallel strategies tailored to the target environment.
The Joshua Framework and Protocol of Inference
The authors built their solution on Joshua, an inference system that utilizes a Protocol of Inference. This architecture relies on several key object-oriented techniques:
- Generic Functions (ASK and TELL): Instead of hard-coded loops, the system uses high-level abstractions for querying and asserting knowledge.
- Mixins: Using the Common Lisp Object System (CLOS), the authors created "mixins" to provide specific parallel behaviors. For instance, a
Loosely-Coupled-Mixinhandles communication over Ethernet, while aShared-Memory-Mixinmanages locking for local data structures. - Parallel Rete Networks: The standard Rete algorithm for rule matching was adapted for parallel execution. The researchers explored various levels of granularity, from spawning tasks for every rule firing to spawning tasks for individual "merge" operations within the network.
To validate these concepts before hardware was fully available, the team employed dual simulation styles: a Multilisp simulator to track theoretical maximum parallelism and a multiprocessing simulation on the Symbolics Genera OS to emulate shared-memory environments.
Experimental Results
The system was evaluated using a rule-based circuit simulator benchmark. This application involves "deductive closure," where the order of rule execution is less critical than in other AI tasks, making it an ideal candidate for parallelization.
As shown in the execution profiles above, the system demonstrated continued speedup as the number of processors ($N$) increased from 1 to 32. However, the researchers identified a significant "overhead threshold." On 1988-era Symbolics 3600 hardware, initiating a lightweight process took approximately 45 microseconds. If a task (such as a Rete merge step) only required 16 microseconds, parallelizing it actually degraded performance.
While absolute speedup continued to 32 processors, the "cost-effectiveness" or processor utilization began to decline significantly between 8 and 16 processors. This drop-off highlights the critical importance of granularity; parallelizing at the level of individual merge operations proved fruitless because the overhead of task creation outweighed the execution time of the task itself.
Insights and Limitations
A key discovery was the bimodal task distribution in Rete merge steps: they are either very fast (failed merges) or significantly slower (successful merges). This variance makes static load balancing particularly difficult. Furthermore, the authors identified that traditional AI systems often contain a "conflict resolution" step that acts as a serial bottleneck, limiting the ultimate benefits of parallelism.
The current work focuses on problems where rule order is flexible. The authors acknowledge that many AI problems require strict ordering, which introduces complex serial bottlenecks. Future work is required to develop more sophisticated "control-level" descriptions and to find alternatives to serial conflict resolution to unlock massive parallelism in production systems.
Summary updated