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 4
4- bzw. 4
5-Puzzle gelöst.
Im Falle des 4
4-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 4
5-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