Seite 2 von 3
Re: SWT[4]#4
Verfasst: Di 16. Jun 2009, 23:30
von 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
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 02:06
von 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?
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 09:58
von 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
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 11:09
von Thomas
benutzt ihr jetzt alle den code aus der algo vl? lässt der sich überhaupt gut parallelisieren?
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 11:45
von Dre
Thomas hat geschrieben: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)
patrick hat geschrieben: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.
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 12:23
von Chrisss
schlies ich mich an, hätte auch gerne explizit gelesen auf welche art der algorithmus paralell sein soll, was als paralellisiert gilt etc..
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 17:09
von Tankwart
BenTreeser hat geschrieben: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.
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 21:21
von 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?^^
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 22:53
von 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
Re: SWT[4]#4
Verfasst: Mi 17. Jun 2009, 23:06
von |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);