Previous approaches to parallel iterative-deepening search include parallel window searches, tree decomposition, search space mappings and special schemes for SIMD machines.
Powley and Korf [1991] presented a Parallel Window Search, where each processor examines the entire search space, but with a different cost-bound. Depending on the application, this method works only for a hand full of processors (e.g., 5-9 in [p. 475]PowleyKorf91) and the solution cannot be guaranteed to be optimal.
Kumar and Rao's [1987,1990] parallel IDA* variant is based on a task attraction scheme that shares subtrees (taken from a donator's search stack) among the processors on demand. For a selected problem set they achieved almost linear speedups on a variety of MIMD computers. These favorable results, however, apply only for MIMD systems with small communication diameters, like a 128 processor Intel Hypercube, a 30 processor Sequent Balance and a 120 processor BBN Butterfly. On a 128-node ring topology their algorithm achieved a maximum speedup of 63. From Kumar and Rao's analysis, it is evident that these results do not scale up to systems of, say, some thousand processors.
The algorithm of Evett et al. [1990] performs a mapping of the search space onto the processing elements of a SIMD machine. This allows to eliminate duplicate states at the cost of an increased communication overhead.
Two other approaches, SIDA* by Powley et al. [1993] and IDPS by Mahanti and Daniels [1993] also run on the CM-2. From these, SIDA* is probably the fastest parallel IDA* implementation, solving all 100 problem instances [Korf, 1985] of the 15-puzzle in 2.245 hours.