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.

Mon Dec 19 17:27:56 MET 1994