Alexander Reinefeld Volker Schnecke
PC - Paderborn Center for Parallel Computing
D-33095 Paderborn, Germany
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.