<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