<b>AIDA* - Asynchronous Parallel IDA*
</b>

** Next:** Introduction

**AIDA* - Asynchronous Parallel IDA*
**

**Alexander Reinefeld Volker Schnecke**

PC - Paderborn Center for Parallel Computing

D-33095 Paderborn, Germany

{ar|ossi}@uni-paderborn.de

### Abstract:

*We present AIDA*, a generic adaptable scheme for highly parallel
iterative-deepening search on large-scale asynchronous MIMD systems.
AIDA* is based on a data partitioning scheme, where the different parts of the
search space are processed asynchronously in parallel.
Existing
sequential solution algorithms can be linked to the AIDA* routines
to build a fast, highly parallel search program.
*
Taking the 15-puzzle as an application domain,
we achieved an average speedup of 807 on a 1024 processor system,
corresponding to an efficiency of 79% on Korf's [1985] 25 largest
problem instances.
Specific problem instances yield more than 90% efficiency.

*
The total time taken by AIDA* to solve Korf's 100 random puzzles
on a 1024-node system was 24.2 minutes.
This is 5.7 times faster than the most efficient parallel
algorithm on a 32K CM-2 machine, SIDA* by Powley **et al.*

* Volker Schnecke*

Mon Dec 19 17:27:56 MET 1994