TL;DR
This paper introduces five parallel algorithms designed to accelerate the execution of production systems (PS) on the DADO parallel computer. The authors explore how different PS program characteristics influence the suitability of each algorithm, aiming to optimize the recognize-act cycle for faster rule firing.
What Problem Does This Paper Address?
Production systems (PS) are a powerful paradigm for knowledge representation and reasoning, widely used in artificial intelligence. However, their execution, particularly the "match" phase where rules are compared against the system's working memory (WM), can be computationally expensive. This paper addresses the challenge of speeding up PS execution by leveraging the inherent parallelism of the DADO machine, a fine-grain parallel architecture. The authors aim to identify which parallel execution strategies are most effective for different types of PS programs, considering factors like temporal redundancy, the number of affected rules, and the size of the rule and working memories.
Methods
The paper proposes five distinct parallel algorithms for PS execution on the DADO machine:
- Algorithm 1: Full Distribution of PM: Distributes a small subset of rules and relevant WM elements to each DADO processing element (PE). It alternates between MIMD (for matching) and SIMD (for selection/action) modes.
- Algorithm 2: Original DADO Algorithm: Divides the DADO tree into a PM-level (MIMD for matching) and WM-subtrees (SIMD as content-addressable memory). This algorithm was the initial design for DADO.
- Algorithm 3: Miranker's TREAT Algorithm: An enhancement of Algorithm 2 that incorporates temporal redundancy by saving state from previous match operations within the WM-subtrees, similar to the Rete algorithm.
- Algorithm 4: Fine-grain Rete: Embeds a compiled Rete network directly onto the DADO tree structure, treating the DADO PEs as nodes in the Rete network. This algorithm operates entirely in MIMD mode.
- Algorithm 5: Multiple Asynchronous Execution: This algorithm doesn't propose a new execution strategy but rather a way to leverage DADO's architecture for concurrent execution. It suggests that any DADO PE can act as a root, allowing for the concurrent execution of multiple PS programs or independent subsets of rules from a single PS program.
The authors analyze these algorithms based on various PS program characteristics, such as temporal redundancy, the number of affected rules, and memory sizes.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- No One-Size-Fits-All: The paper strongly emphasizes that different parallel execution algorithms are suited for different types of production systems. Understanding the characteristics of a PS program is crucial for selecting the most efficient algorithm.
- DADO's Architectural Strengths: The DADO machine's ability to operate in both SIMD and MIMD modes, along with its specialized "max-RESOLVE" circuit for fast selection, are key enablers for these parallel algorithms.
- Rete Algorithm's Influence: The Rete algorithm's efficiency in handling temporal redundancy is a significant factor, leading to algorithms like TREAT and Fine-grain Rete that aim to adapt its principles to parallel hardware.
- Trade-offs in Parallelism: Distributing the Production Memory (PM) across many PEs (Algorithm 1) offers parallelism but might struggle with massive WM changes. Conversely, algorithms that save state (TREAT) excel with temporal redundancy but might be less efficient for non-temporally redundant systems.
- Fine-grain Rete as a Promising Direction: Algorithm 4, embedding Rete directly onto the DADO tree, appears to be a natural fit for the architecture and is well-suited for temporally redundant systems with large rule sets.
Key Results
The paper presents a qualitative analysis of the suitability of each algorithm for different PS program characteristics. A table in the conclusion summarizes these findings:
- Algorithm 1 (Fully Distributed PM): Best for PS with temporal redundancy, few affected rules, restricted pattern matches, small PM, and large WM.
- Algorithm 2 (Original DADO): Suitable for non-temporally redundant systems, many affected rules, global WM tests, small PM, and large WM.
- Algorithm 3 (TREAT): Ideal for temporally redundant systems, many affected rules, global WM tests, and large WM.
- Algorithm 4 (Fine-grain Rete): Best for temporally redundant systems, few affected rules, large PM, and small WM.
- Algorithm 5 (Multiple Asynchronous): Applicable to all cases, enabling concurrent execution of multiple PS programs or rule subsets.
The authors state that empirical evaluation on the DADO2 prototype is ongoing to substantiate these claims.
Limitations and Future Work
- Empirical Validation Pending: The paper acknowledges that the performance statistics for most of the algorithms have yet to be analyzed in detail and are based on analytical expectations. The authors plan to implement and critically evaluate these algorithms on the DADO2 prototype.
- WM Storage Constraints: For Algorithm 1, a limitation is noted when a local WM becomes too large to be conveniently stored in a PE.
- PM Size Limitations: For Algorithm 2, the full capacity of the DADO machine for PM is underutilized due to the single-level rule storage, suggesting that systems with a few hundred rules are more appropriate.
- Coordination of Concurrent Execution: Algorithm 5 highlights the complexity of coordinating communication acts when subsets of rules infer data required by other rule sets, which is an area of ongoing research.
- RHS Action Specification: For Algorithm 4, the paper mentions that the RHS action specification is broadcast at once, suggesting potential for further optimization in how these actions are handled.
Summary updated