Abstract
This paper introduces Distributed Tree Search (DTS), a decentralized framework designed to parallelize search algorithms across multiple processors without the need for shared memory. A key contribution is the Bound-and-Branch allocation strategy, which optimizes alpha-beta pruning by balancing parallel execution with the sequential dependencies necessary for effective pruning. Experimental results on an Intel Hypercube using Othello benchmarks demonstrate that DTS can achieve significant speedups, effectively scaling search tasks while minimizing the "search overhead" typically associated with parallel branch-and-bound algorithms.
Introduction
Search algorithms are fundamental to artificial intelligence, yet their computational complexity remains a significant bottleneck. While parallel processing offers a potential solution, it is notoriously difficult to apply to "branch-and-bound" algorithms like alpha-beta pruning. In these algorithms, the value discovered in one branch is used to prune other branches. Parallelizing this process often leads to "search overhead," where processors evaluate nodes that a serial algorithm would have skipped, resulting in wasted work. Previous attempts at parallelizing alpha-beta search often hit a speedup ceiling or relied on centralized control that failed to scale. Ferguson and Korf propose DTS as a scalable, decentralized alternative.
Methodology
The DTS Framework
Unlike traditional models that use a central controller, DTS treats each node in the search tree as a process managing a pool of processors. A parent process expands a node and distributes its available processors to its children based on a specific allocation strategy. Once a child process completes its task, it returns the processors to the parent for reassignment. This recursive approach naturally handles irregular trees and avoids the bottlenecks of shared memory.
Allocation Strategies
The paper evaluates two primary strategies:
- Breadth-First Allocation: Processors are distributed evenly among all children. This is effective for brute-force searches but inefficient for alpha-beta pruning as it ignores the potential for cutoffs.
- Bound-and-Branch Allocation: This novel strategy mimics serial pruning logic. It initially assigns all processors to the first child to establish a "cutoff bound" as quickly as possible. Once a bound is established, it switches to a breadth-first approach, branching the remaining processors to search other children in parallel.
Experimental Evaluation
The researchers evaluated DTS using 40 mid-game positions from Othello. The testbed was a 32-node Intel Hypercube, a message-passing multiprocessor. Performance was compared against standard uniprocessor alpha-beta search, with simulations extending the analysis up to 256 processors.
Results and Discussion
For brute-force search, DTS achieved near-perfect linear speedup (within 2% of the theoretical maximum). For alpha-beta search using the Bound-and-Branch strategy on Othello, the system achieved an actual speedup of 12 on 32 processors.
As shown in the figure above, the Bound-and-Branch strategy (Curve D) outperforms the standard breadth-first approach (Curve C). The gap between Curve E (B&B without communication overhead) and Curve D illustrates that communication and idle time account for approximately 25% of the total execution time at 32 processors. The authors also noted a "Pruning Paradox": as serial pruning efficiency improves, the relative speedup of parallel versions may appear lower because the search overhead becomes more prominent.
Conclusion
DTS provides a robust framework for scaling search algorithms. By decentralizing control and utilizing the Bound-and-Branch strategy, the authors demonstrated that significant parallel gains are possible even for algorithms with heavy sequential dependencies. Future work suggests that better move-ordering heuristics could further improve speedup, potentially reaching the "high speedup" zone where parallel efficiency is maximized. While communication overhead remains a factor as depth increases, the decentralized nature of DTS makes it a promising candidate for even larger-scale multiprocessor systems.
Summary updated