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).
The REDUCE-OR Tree Formalism
The REDUCE-OR tree is constructed using two types of nodes:
- 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.
- 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.
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