Figure 1: AIDA* Algorithm Architecture
In the following we describe AIDA*, a generic adaptable scheme for highly parallel iterative-deepening search on asynchronous MIMD systems. AIDA* is based on a data partitioning scheme, where the different parts of the search space are processed asynchronously by the fastest available sequential routines running in parallel on the distributed processing elements. Existing sequential search code can be adapted to the parallel AIDA* system by linking the routines for initial tree partitioning, work-load balancing and communication. A simple, but efficient task attraction scheme combined with a `weak' synchronization mechanism ensures a high processor utilization and good scalability up to some thousand processors.
AIDA* consists of three phases (cf., Fig. 1):
None of these three phases requires a hard synchronization. Processors are allowed to proceed with the next phase as soon as they finished the previous one. Only in the third phase, some mechanism is needed to keep all processors working on about the same search iteration. However, this synchronization is a weak one (as opposed to hard barrier synchronization), allowing the processors to proceed with the next iteration after checking for work in their neighborhood only.
Figure 1: AIDA* Algorithm Architecture
Similar to Newborn's [1988] unsynchronized iteratively deepening parallel alpha-beta, each processor carries out an iterative-deepening search on its selected subset of nodes. Our work-load balancing scheme ensures that all processors finish their iterations at about the same time.