Parallelization of Tree-Recursive Algorithms on a SIMD Machine

Curt Powley, Richart E. Korf, and Chris Ferguson

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.