SWT[4]#4

[Thomas]

http://openbook.galileocomputing.de/jav ... 11_001.htm
hier ist was von java ist auch eine insel zu dem thema, habs mir aba selbst noch nicht durchgelesen und werd heute abend mal anfangen

[Misda]

Also egal was ich anstelle, der parallele Code ist bei mir deutlich langsamer als der Sequentielle - gibts da irgendwie nen Ansatz wie ich bei der Aufgabe am geschicktesten Vorgehe?

[patrick]

Egal wie du dich anstellst, der parallele Code wird immer wesentlich langsamer sein. Es werden hier immerhin in jedem Rekursiven Aufruf 2 neue Threads erstellt. Dafuer muss jeweils von einer Runnable Klasse ein neues Objekt erstellt werden. Weiter erhaellt jeder Thread einen eigenen Bereich auf nem Stack, der auch erstmal beschrieben werden muss. Insgesammt ist es eigentl. grosser Schwachsinn in einem Programm soviele Threads zu starten.
Fuer Eingabegroessen wie bei Algo (ab 1<<14 oder schon weniger) reicht der Hauptspeicher der fuer Java freigegeben ist nicht mehr aus fuer den Thread Stack und die Teilarrays.

VG patrick

[Thomas]

benutzt ihr jetzt alle den code aus der algo vl? lässt der sich überhaupt gut parallelisieren?

[Dre]

benutzt ihr jetzt alle den code aus der algo vl? lässt der sich überhaupt gut parallelisieren?

Ich hab mir ein eigenen geschrieben. Steht ja nirgends, dass du den aus Algo nehmen musst (eher im Gegenteil glaub ich).
Implementier den, der dir am sinnvollsten erscheint (obwohl es da nicht sehr viele Unterschiede bei der rekursiven Variante gibt)

Es werden hier immerhin in jedem Rekursiven Aufruf 2 neue Threads erstellt.

Warum das denn? Dann hat ja dein Hauptthread gar nix mehr zu tun.
Ich lass immer nur 1 zusätzlichen Thread pro Aufruf laufen. Ich mein, das ändert im Endeffekt auch nicht viel bei großen Arrays,
aber meh, ist ja nur ne Übungsaufgabe.

Meiner Meinung nach hätten sie das auch ein wenig konkreter in die Aufgabenstellung schreiben können,
wieviele Threads sie sich vorstellen oder so.

[Chrisss]

schlies ich mich an, hätte auch gerne explizit gelesen auf welche art der algorithmus paralell sein soll, was als paralellisiert gilt etc..

[Tankwart]

kann es sein, dass dieses falsch implementiert ist?[...]

Der sortiert nur von "from" bis "to - 1".
Wenn der mit sort(array, 0, array.length) aufgerufen wird stimmen die Ergebnisse.

[Thomas]

könnte mir vllt jemand nen tipp geben wie man das parallelisieren hier bewerkstelligen soll? weil wenn ich einfach die mergeSort methode in einem run aufrufe bekomm ich ja keine gescheiten ergebnisse. muss ich split und merge aufteilen und jeweils dafür nen thread machen, oder vllt die merge methode synchronisieren so dass immer nur ein thread rein kann? jemand nen tipp vllt?^^

[Baloo]

Also ich hab mir das so gedacht:

Lässt man den Mainthread außer acht sollte man pro Prozessor einen Thread haben, denn damit holt man den größten Geschwindigkeitsvorteil raus. Wenn man sich nun ganz den Rekursions Algorithmus nochmal anschaut hat man gaaanz zum Schluss zwei sortierte Listen, die ein letztes Mal gemerget werden müssen. Da sollte es eigentlich klack machen. So bin ich zumindest draufgekommen, also zum Algorithmus:

Code: Alles auswählen

Teile das Array in n Subarrays auf, n = Anzahl Prozessoren
Erstelle für jedes Subarray einen Thread, der das Subarray sortiert, und starte ihn
Lass den MainThread solange warten, bis die SubarrayThreads fertig sind
Merge die Subarrays wieder in das Orginalarray

Nur mit der Aufteilung komm ich noch nicht ganz klar. Meine Implementierung bietet für beide Klassen (MergeSortParallel, MergeSortRecursive) eine statische Schnittstelle nach außen. Man lässt also so sortieren:
MergeSortRecursive.sort(array) oder MergeSortParallel.sort(array). Die Parallele Implementierung greift dabei auf Methoden der rekursiven Implementierung zurück. Deswegen erbe ich einfach von der Rekursiven Impl.Hab ich jetzt die Schablonenmethode angewendet??? Weil ne wirkliche hierarchie/schnittstelle oder Schablonenmethode hab ich ja damit nicht gebildet.

greetz und viel Erfolg
Baloo

[|silent]

Moin Baloo,

also das mit der Schablonenschnittstelle ist mir auch noch ein Rätsel. Ich denke aber, dass es einfach so gedacht ist, dass man eine abstrakte Klasse (bei mir "MergeSort") hat, von der die konkreten Klassen "MergeSortParallel" und "MergeSortSequentiell" erben. "MergeSort" hat als Methode nur "sort(int[] seq, int from, int to)", diese ruft wiederum eine Methode in der Unterklasse auf. Laut Aufgabenstellung soll das ja standardmäßig der Parallel-Algorithmus sein.

Nur weiß ich selber nicht, ob es in Ordnung ist, wenn ich in meiner Main-Klasse folgendes mache (da ich meine Threads nur innerhalb der MergeSortParallel-Klasse habe):

Code: Alles auswählen

IOHelper helper = new IOHelper();
array = helper.getNextIntegerArray();
MergeSort.sort(...)
helper.printResult(array);