In diesem Artikel wird ein allgemeiner Parallelisierungsansatz für Baumsuchalgorithmen vorgestellt. Der Kern dieses Ansatzes liegt in einer zweiphasigen Lastverteilungsstrategie, durch die es möglich ist, ohne jede Kommunikation oder Synchronisation eine initiale Aufteilung des Suchbaumes zu erzeugen, die so ausgewogen ist, daß in weniger als 10% der Gesamtsuchzeit eine dynamische Lastverteilung erfolgt.
Als Anwendung wurde ein einfaches Spielproblem, das n x n - Puzzle gewählt.
Die Implementierung erfolgte unter PARIX und wurde sowohl auf dem Parsytec GCel als auch auf einem Netz von Parsytec Power Xplorern getestet. Dabei werden selbst für sehr kleine Instanzen mit einer parallelen Laufzeit von weit unter einer Minute Speedups von über 700 auf einem System mit 1024 Prozessoren erreicht.
HTML, Postscript (90 kB)