Einleitung
Aufgabenstellung
Setzen Sie den vorgegebenen Algorithmus in ein C-Programm unter Einsatz von MPI um. Dabei sollen folgende Punkte Berücksichtigung finden:
- die Zahlen sind von einem Prozessor zu erzeugen und an die beteiligten Prozessoren zu verteilen
- am Ende soll ein Prozessor das sortierte Feld zu Kontrollzwecken ausgeben können
- das Programm soll mit unterschiedlich großen Datensätzen getestet werden, z.B. 20000, 40000, 80000 Zahlen
- das Programm soll mit unterschiedlich vielen Prozessoren getestet werden.
Analysieren Sie das Laufzeitverhalten Ihres Programms, wobei insbesondere Aussagen zum Speedup von Interesse sind. Des weiteren sollen Aussagen darüber getroffen werden, welchen zeitlichen Anteil das anfängliche sequenzielle Sortieren an der Gesamtlaufzeit des Programms hat und wie groß der Kommunikationsoverhead ist.
Definition PSRS
Bei Parallel Sorting by Regular Sampling (PSRS) handelt es sich um einen parallelen Sortieralgorithmus der einen verträglichen Kommunikationsaufwand und gute Balance-Eigenschaften aufweist. Der Algorithmus ist für diverse MIMD-Architekturen geeignet. Eine genaue Definition der einzelnen Phasen ist in Kapitel 2 aufgezeigt.
Die Testumgebung
Als Testumgebung für dieses Projekt diente der Glass-House Cluster (alle Knoten befinden sich im gleichen Raum) im Zusebau, Z423 der HTWK Leipzig. Dieser Cluster besteht aus 24 Knoten. Es handelt sich um einen homogenen Cluster (Hard- und Software auf allen Geräten gleich).
Einschränkungen
Da der Cluster auf den Workstations der HTWK läuft, ist kein dedizierter Zugriff auf das System möglich. Dadurch ergeben sich recht große Schwankungen bei den Laufzeitmessungen. Um mögliche Messschwankungen gering zu halten, wurden alle Messungen fünf mal nacheinander ausgeführt und anschließend daraus der Durchschnitt berechnet. Des weiteren wurden alle Tests mehrfach ausgeführt, um eine konkrete Aussage über das Verhalten des Programms treffen zu können. Durch diese Mehrfachausführung konnten Fehler in den Messreihen, welche durch die Benutzung der einzelnen Knoten als Workstation aufgetreten sind, eingeschränkt werden. Zudem wurden größere Messungen während der Nacht oder am Wochenende ausgeführt, da zu diesen Zeiten davon auszugehen ist, dass die einzelnen Knoten nicht als Workstations benutzt werden.
