Cluster Praktikum

Blatt 11.2

Aufgabe 13: JavaParty-Version des Odd-Even-Transposition-Sort Algorithmus

Die Java-Version des Odd-Even-Transposition-Sort aus der Aufgabe (Blatt 9) soll nun in ein Javaparty-Programm ungewandelt werden.

Dazu müssen Sie im Wesentlichen - wenn Sie bei der Lösung des letzten Aufgabenblattes alles richtig gemacht haben - nur aus dem Objekt, mit dem Sie die Threads konstruieren, ein entferntes Objekt machen, indem Sie das Schlüsselwort remote vor die Definition schreiben.

Sie sollen aber darüberhinaus Ihr Programm hin zu einer parallelen Version mit (hoffentlich) besserer Effizienz optimieren. Dies wird im folgenden erläutert.

Die in der letzten Aufgabe programmierte Version hat in etwa folgende Struktur:

Zunächst wird die Anzahl der entfernten Methodenaufrufe reduziert. Die beiden entfernten Methodenaufrufe dienen nur der Übermittlung der Daten. Im ersten Aufruf werden die Daten aus dem Speicherbereich eines anderen Threads ausgelesen, dann lokal verarbeitet und schließlich in einem weiteren entfernten Methodenaufruf wieder zurückgeschickt. Diese drei Schritte lassen sich jedoch auch in einem einzigen entfernten Methodenaufruf durchführen: Die lokalen Daten werden als Argumente mitgeschickt, der Mischvorgang im Rumpf der entfernten Methode ausgeführt und eine Hälfte der Daten als Ergebnis des Aufrufes zurückgeschickt.

Die entfernten Objekte müssen also neben der run()-Methode noch eine mergeOtherArray()-Methode besitzen, die von den benachbarten Threads aus deren run()-Methode aufgerufen wird. Sie mischt die übergebenen Daten mit den lokalen Daten und gibt den Teil mit den kleineren Daten zurück.

Außerdem kann die globale Barriere durch eine Reihe von lokalen Barrierenoperationen auf jedem Knoten ersetzt werden. An so einer lokalen Barriere synchronisieren sich jeweils zwei Threads: Der lokale Thread und der Thread, der den Rumpf der entfernten Methode ausführt.

Um Ihr Programm zu testen, übersetzen Sie es mit dem Befehl

javaparty compile -d . RemoteSorters.java

jpinvite -cp . -nodenames carla1,carla2 RemoteSorters

Hinweise

Verwenden Sie den Praktomaten, um Ihre Lösung abzugeben. Die Main-Klasse muss den Namen RemoteSorters tragen. Ihr Programm soll diesmal die Daten nicht von der Standardeingabe lesen, sondern aus der Datei, deren Namen als erstes Argument (also in arg[0]) übergeben wird. Das Format ist unverändert geblieben: In der ersten Zeile steht die Anzahl der zu erzeugenden Sortier-Threads, in der zweiten Zeile die Anzahl der Daten und in den folgenden Zeilen die Daten selbst. Die Ausgabe der sortierten Daten erfolgt wie bisher auch über die Standardausgabe.