Speculative Parallelism Improves Search?

• Author(s) / Creator(s)

  • Gao, Yaoqing
  • Marsland, Tony

• Technical report TR95-05. The extreme efficiency of sequential search, and the natural tendency of tree pruning systems to produce wide variations in workload, partly explains why it is proving difficult to achieve more than 30-50% efficiency for massively parallel implementations of the alpha-beta algorithm. Here we introduce typical enhanced sequential algorithms and address the major issues of parallel game-tree searching under conditions of severe pruning. It is this pruning that makes the parallelization difficult. After examining previous work on parallel alpha-beta algorithms, we present a new method called Dynamic Multiple Principal Variation Splitting (DM-PVSplit) and implement it on the AP1000. In this algorithm, high performance is achieved by using some novel approaches: Parallel speculative search of candidate principal variations is used to reduce re-search delay and so obtain more quickly a better estimate of the subtree value. This is achieved by configuring a flat processor arrangement as a dynamically changeable tree structure. Also, with the aid of a group-based scheduling strategy, the game tree is split dynamically at different levels. This provides better load balance and takes more advantage of parallelism. Preliminary experiments show that the scalability of the DM-PVSplit algorithm is good for massively parallel machines. | TRID-ID TR95-05

• Date created

  1995

• Subjects / Keywords

  • Massively parallel processing
  • Parallel tree splitting
  • Alpha-beta search
  • Dynamic Multiple PVSplitting

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R38X79

• License

  Attribution 3.0 International