Iterative Tiefensuche
auf einem massiv parallelen System
Next: Einleitung
Iterative Tiefensuche
auf einem massiv parallelen System
Volker Schnecke
Universität Osnabrück
Fachbereich Mathematik/Informatik
49069 Osnabrück
volker@informatik.uni-osnabrueck.de
Abstract:
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
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.
Volker Schnecke
Mon Dec 19 15:48:20 MET 1994