Ergebnisse

Die Implementierung von AIDA* unter PARIX wurde auf dem Parsytec GCel-1024 des PC und auf einem Netz von Parsytec Power Xplorern bei der ZIAM in Aachen getestet. Als Problem wurde das 44- bzw. 45-Puzzle gelöst. Im Falle des 44-Puzzles wurden die 100 Instanzen aus [4] in vier Klassen mit je 25 Instanzen eingeteilt.

  
Table: Die mittleren Werte für die Instanzen des Puzzle-Problems

Die Tabelle 1 zeigt die Mittelwerte für die einzelnen Problemklassen. Dabei werden für das 44-Puzzle nur die Klassen III und IV aufgeführt, da mit den 50 kleineren Instanzen ein System von mehr als eintausend Transputern nicht sinnvoll ausgelastet werden kann. Die durchschnittliche parallele Laufzeit auf 1024 Prozessoren liegt selbst in der Klasse IV nur bei 43 Sekunden. Es wird in dieser Klasse ein durchschnittlicher Speedup von 707 erreicht, wobei die Dauer für die erste Phase, in der alle Prozessoren redundant dieselben Knoten expandieren, etwa drei Sekunden beträgt. Für einzelne Probleme liegt der Speedup sogar über 840. Die angegebenen Speedup-Werte sind normiert über die Zahl der Knotenexpansionen in einer Sekunde und somit frei von Speedup-Anomalien. Im Falle des 45-Puzzles wurden 13 kleinere zufällig erzeugte Instanzen getestet. Die Laufzeiten und Speedup-Werte für die einzelnen Instanzen sind in Tabelle 2 aufgeführt.

  
Table 2: Die 13 Instanzen des 45-Puzzles auf dem GCel

  
Figure: Die Speedupgraphen für das Puzzle-Problem auf dem Parsytec GCel-1024 des PC

Die PARIX-Implementierung wurde auch auf einem Netz von 16 Parsytec Power Xplorern mit jeweils 4 Motorola PowerPC Prozessoren getestet. Die Leistung des PC601 liegt bei der sequentiellen Implementierung des Algorithmus IDA* für das 44-Puzzle um einen Faktor von etwa 24 höher als die des T805. Leider ist die Kommunikation in diesem System deutlich teurer im Vergleich zur Rechenzeit als etwa im GCel. Hierdurch schrumpft dieser Faktor bei den 13 kleineren Testinstanzen von 24 (sequentielle Version) auf 6 (64 Prozessoren). Die mittlere Laufzeit liegt dabei bei etwa 6 Sekunden pro Instanz (GCel: 36 Sekunden). Die Abbildung 6 zeigt die durchschnittlichen Speedups für die 13 Instanzen auf den beiden Systemen.

  
Figure: Die Speedupgraphen für AIDA* auf dem Xplorer und dem GCel