Parallelization of Tree-Recursive Algorithms on a SIMD Machine

Innovative Applications of Massive Parallelism

Volume

Papers from the 1993 AAAI Spring Symposium

Contents

The set of tree-recursive algorithms is large, including constraint satisfaction using backtracking, iterative-deepening search such as IDA*, depth-first branch-and-bound, twoplayer game minimax search, and many divide-and-conquer algorithms. We describe a structured method for implementing such algorithms on SIMD machines, and identify measures for determining if a tree-recursive application is amenable or ill-suited for SIMD parallelization. Using these ideas, we evaluate results from four testbeds.