Research Group Prof. Vornberger

Abstract: AIDA* - Asynchronous Parallel IDA*

A. Reinefeld, V. Schnecke

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 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.

Procs. 10th Canadian Conf. on Artificial Intelligence, AI'94, Banff, Canada, 1994, 295-302

HTML, Postscript (86 kB)