Massively Parallel Support for Computationally Effective Recognition Queries

Matthew P. Evett, James A. Hendler, William A. AndersenAAAI 1993

Abstract

PARKA is a frame-based knowledge representation (KR) system designed to leverage the massive parallelism of the Connection Machine (CM-2) to solve complex "recognition" queries. By transitioning from traditional serial processing to a parallel "activation wave" approach, PARKA achieves query times proportional to the depth of the knowledge base rather than its total size. This architecture enables sub-second response times even for knowledge bases containing millions of frames, addressing the computational bottlenecks that previously limited large-scale AI reasoning.

Introduction

In the early 1990s, artificial intelligence faced a significant challenge: while formalisms for knowledge representation worked well for small, "toy" domains, they were often computationally ineffective for real-world applications. A primary bottleneck was the recognition problem—the task of identifying all objects in a knowledge base (KB) that satisfy a specific set of constraints (e.g., "Find all $x$ such that $x$ is yellow, alive, and flies").

Traditional serial KR systems typically require a linear scan of the entire KB to answer such queries, resulting in $O(n)$ complexity. As KBs scale toward the millions of frames necessary for commonsense reasoning, these queries become prohibitively slow. For AI to be viable in real-time agents, recognition must be nearly instantaneous, regardless of the total volume of knowledge.

Methodology

The authors introduced PARKA, a system implemented on the Connection Machine (CM-2), a massively parallel SIMD (Single Instruction, Multiple Data) computer. PARKA utilizes several key techniques to achieve high performance:

  • Data Mapping: Each frame (concept or object) is mapped to a block of processors, with relations (slots) stored as pointers between these processors.
  • Activation Wave Propagation: To handle property inheritance, PARKA uses a "wave" of signals that starts at the root of the hierarchy and flows downward. Because the CM-2 can update all processors simultaneously, each step of the wave occurs in constant time for the entire KB.
  • Topological Disambiguation: To manage multiple inheritance, PARKA employs a parallel-friendly topological numbering scheme, a simplified version of Touretzky’s Inferential Distance Ordering (IDO).
  • Pipelining: To handle multiple constraints (conjuncts), PARKA pipelines activation waves. This allows the system to process different constraints at different levels of the hierarchy simultaneously.

Experimental Evaluation

The system was evaluated using both synthetic and real-world datasets:

  1. Synthetic KBs: Pseudo-random networks of up to 128,000 nodes with varying depths and fan-outs were used to test scalability.
  2. Cyc KB: A subset of 26,214 frames from the Cyc commonsense knowledge base was used to validate performance on human-designed hierarchies.

Results and Discussion

The primary insight of the PARKA architecture is that in a massively parallel environment, query speed is determined by the depth of the knowledge base rather than its breadth. By using pipelining, the time complexity for a recognition query is reduced to $O(d+p)$, where $d$ is the depth of the KB and $p$ is the number of properties (conjuncts).

Figure 4: Comparison of run-time between serial systems and PARKA as knowledge base size increases.

As shown in Figure 4, PARKA's performance remains nearly flat as the knowledge base size increases, whereas serial systems exhibit linear growth in run-time. On KBs with over 100,000 frames, PARKA demonstrated a speedup of over 10,000 times compared to an optimized serial version (SPARKA).

Figure 5: Run-time scaling linearly with the number of conjuncts in a query.

Furthermore, Figure 5 illustrates that the run-time increases linearly with the number of properties being searched for, confirming the $O(d+p)$ model. On the Cyc KB (depth 23), a recognition query with 22 different constraints was completed in less than one second.

Conclusion

PARKA demonstrates that trading some semantic expressiveness for computational efficiency can yield systems capable of real-time reasoning on massive datasets. While the original implementation was tied to SIMD hardware, the underlying principles of activation waves and pipelining provide a roadmap for scaling AI knowledge systems. Future work includes migrating to MIMD architectures for further speedups and deeper integration with higher-level reasoning and planning systems.

Summary updated

BibTeX
@inproceedings{evett1993massively,
  author = {Matthew P. Evett and James A. Hendler and William A. Andersen},
  title = {{Massively Parallel Support for Computationally Effective Recognition Queries}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure