A Tree Representation for Parallel Problem Solving

Laxmikant V. KaléAAAI 1988

Abstract

This paper introduces the REDUCE-OR tree, a novel formalism for representing logic programs in parallel computing environments. By moving beyond traditional AND-OR and SLD trees, the proposed representation allows for the simultaneous exploitation of AND and OR parallelism, even in the presence of shared variables. The REDUCE-OR tree maintains the search-space pruning efficiency of sequential models while enabling high-performance parallel execution.

Introduction

In the late 1980s, parallelizing logic programming (such as Prolog) faced a fundamental conflict: how to balance execution speed with search efficiency. Traditional AND-OR trees allow for parallel exploration but often lead to redundant computation when sub-goals share variables. Conversely, SLD trees—the standard for sequential Prolog—efficiently prune the search space but are inherently sequential. L.V. Kalé's 1988 paper proposed the REDUCE-OR tree as a unified solution that captures the strengths of both approaches.

The Problem: Pruning vs. Parallelism

The core challenge lies in handling interdependent goals. For instance, in a query like Square(10, x), Cube(x, y), the two goals share the variable x.

  • Independent Parallelism: Solving them simultaneously wastes resources because the second goal lacks the constraint provided by the first.
  • Sequential Execution: Solving them one after the other allows for pruning but sacrifices the speed of parallel processing.

The paper uses a contrived logic program to demonstrate these complexities, involving predicates such as P(x,y), Q(x,y), and R(x,z).

Figure 1: A Problem Specification demonstrating complex variable bindings and the limitations of standard logic representations.

The REDUCE-OR Tree Formalism

The REDUCE-OR tree is constructed using two types of nodes:

  1. REDUCE Nodes: These represent the application of a specific Horn clause. Within these nodes, the rule body is represented as a Data Join Graph (DJG)—a partial order of literals that identifies which goals can run in parallel and which must wait for data from others.
  2. OR Nodes: These represent the task of solving a single literal.

A key feature of this model is the Partial Solution Set (PSS). Every node in the tree is an independent unit of computation. When an OR-node finds a solution (a variable substitution), it is added to its PSS. The parent REDUCE-node then uses these partial solutions to instantiate subsequent goals in its DJG. This "context-carrying" approach ensures that nodes can be processed on different processors without constant communication.

Figure 3: A REDUCE-OR Tree illustrating the integration of Data Join Graphs and Partial Solution Sets for parallel execution.

Key Insights and Advantages

  • Self-Contained Tasks: By attaching substitutions directly to OR-nodes, Kalé makes each node a self-contained task, which is essential for efficient parallel systems.
  • Partial Orders over Total Orders: Unlike traditional strict left-to-right execution, the REDUCE-OR tree uses DJGs to acknowledge that while some tasks must be sequential, all others should be parallel.
  • Optimized Search: The representation is particularly powerful for "generate-and-test" problems, allowing a generator to feed results to multiple parallel testers while maintaining pruning.
  • Redundancy Reduction: The REDUCE-OR structure can merge identical sub-problems, a feature that traditional SLD trees lack.

Conclusion

The REDUCE-OR tree provides a robust framework for parallel logic programming, successfully integrating OR-parallelism and AND-parallelism with the pruning efficiency of SLD trees. While implementation requires managing the overhead of PSS sets and DJGs, the formalism represents a significant step toward scalable parallel AI systems. Future work includes the development of heuristics to guide search in resource-constrained environments.

Summary updated

BibTeX
@inproceedings{kale1988tree,
  author = {Laxmikant V. Kalé},
  title = {{A Tree Representation for Parallel Problem Solving}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure