c++.de :: [gelöst Danke]Parallelisierung einer For-Schleife

ComputerCarl Mitglied 17:37:47 25.05.2012 Titel:

Hallo,

Ich arbeite gerade an einem Projekt, welches eine solch enorme Laufzeit hat, dass ich vermutlich gezwungen bin Abläufe zu Parallesieren. Leider habe ich das noch nie gemacht und habe kaum Hilfe im Netz gefunden.

Da der Hauptteil der Laufzeit in einer 3-fach verschachtelten for-Schleife liegt, scheint hier die Parallelisierung am sinnvollsten zu sein. Per Google habe ich oft eine parallel_for Funktion gefunden. Ich hab dort aber nie ausführbaren Code gesehen. Jedenfalls hat mein Compiler nur Fehlermeldungen ausgespuckt. Ist die Antwort auf das Problem in dieser Richtung zu finden oder ist es wirklich zu komplex, um jetzt eine "kurze" Zusammenfassung zu geben? Kennt sich hier jemand damit aus bzw. kann mir Links/Literatur empfehlen? Ich benutze ein Windows XP System mit dem Dev C++ 4.9.9.2-Commpiler.

Mein Problem vereinfacht dargestellt ist:

Code:
1 2 3 4 5 6 7 8 9 10 11	for(int n = 0; n < data_array.size(); n++) { double res; for(int i = 0; i < data_array[n]_row; i++) { for(int j = 0; j < data_array[n]_colum; j++) { res += function(data_array[n][i][j]); } } array_result[n] = res; }

cooky451 Mitglied 17:44:11 25.05.2012 Titel:

parallel_for gehört nicht zu C++, sondern ist eine Bibliotheksfunktion. VS11 (und ich glaube auch 10) hat z.B. eine solche Funktion. Siehe z.B. msdn.microsoft.com/en-us/library/dd728073.aspx

Aber um was für Berechnungen geht es denn da? Sicher, dass man das nicht noch anders optimieren kann? (Cache, Vergleiche gegen 0, etc.?)
Denn die Parallelisierung auf der CPU wird dir erstmal kaum mehr als 4x Geschwindigkeit geben. Wenn du mehr brauchst, muss man sich wohl die Grafikkarte angucken. (PS: Gibt's nen Grund dafür, dass du Dev C++ nutzt? oO)

Unregistrierter 17:46:38 25.05.2012 Titel:

ComputerCarl schrieb:

Windows XP System

Was bist du denn? Ein Höhlenmensch?

Sieht es nicht danach aus, dass er Threads will?

ComputerCarl Mitglied 17:52:40 25.05.2012 Titel:

Achso, nicht C++? Ich hab peinliche Google-Kompetenzen...

Andere Optimierungen sind mir nicht eingefallen und bekannt sind mir eigentlich keine wirklichen Tricks. Cache, Vergleiche gegen 0, etc. ist mir alles nicht bekannt. Das eigentliche Problem ist eigentlich ein Baum-Welsh über mehrere Sequenzen. Das Berechnen der Forward- und Backward-Matrix braucht bei mir die meiste Zeit, da sie für jede Sequenz ausgerechnet werden muss. Wäre es möglich diese parallel zu machen, wäre schon viel gewonnen.

Ja und Dev C++... nutze ich nur am Heim-Rechner für kleine Teilprobleme. Wohl einfach nur aus Gewohnheit und Unwissenheit über gute Alternativen.

Michael E. Mitglied 17:52:59 25.05.2012 Titel:

ComputerCarl schrieb:

Dev C++ 4.9.9.2-Commpiler.

Dev-C++ ist eine IDE und kein Compiler. Genauer gesagt ist deine Dev-C++-Version vom Febraur 2005 (!) und benutzt den GCC 3.4.2. Aktuell ist beim GCC die Version 4.7. Dein erster Schritt sollte also darin bestehen, eine zeitgemäße IDE mit modernem Compiler zu benutzen.

Zitat:

Da der Hauptteil der Laufzeit in einer 3-fach verschachtelten for-Schleife liegt, scheint hier die Parallelisierung am sinnvollsten zu sein.

Das ist geraten, richtig? Rate niemals, wo die meiste Zeit verbraucht wird, sondern miss es! Schnapp dir dazu einen Profiler.

Kannst du ein wenig Code zeigen?

Edit: Nur um sicherzugehen: Hast du als Release-Version kompiliert?

ComputerCarl Mitglied 17:54:06 25.05.2012 Titel:

[quote="Hacker"]

ComputerCarl schrieb:

Was bist du denn? Ein Höhlenmensch?

...

mehr möchte ich dazu nicht sagen :rolleyes:

...

ComputerCarl Mitglied 17:57:25 25.05.2012 Titel:

Michael E. schrieb:

Das ist geraten, richtig? Rate niemals, wo die meiste Zeit verbraucht wird, sondern miss es! Schnapp dir dazu einen Profiler.

Na ja Zeitmessungen habe ich schon gemacht. Allerdings weiß ich nicht ob dafür die clock()-Funktion die beste Alternative ist. Ja und Code würde schon gehen, aber ich weiß nicht, ob da wirklich ein Mehrwert ensteht, da er wirklich lang ist und der Baum-Welsh im Netz eigentlich gut erklärt ist.

Michael E. Mitglied 17:58:28 25.05.2012 Titel:

ComputerCarl schrieb:

Das eigentliche Problem ist eigentlich ein Baum-Welsh über mehrere Sequenzen.

Schon mal die Performance mit anderen Implementierungen verglichen? Z.B. http://www.kanungo.com/software/software.html#umdhmm

Unregistrierter 18:01:08 25.05.2012 Titel:

ComputerCarl schrieb:

Michael E. schrieb:

Das ist geraten, richtig? Rate niemals, wo die meiste Zeit verbraucht wird, sondern miss es! Schnapp dir dazu einen Profiler.

Na ja Zeitmessungen habe ich schon gemacht. Allerdings weiß ich nicht ob dafür die clock()-Funktion die beste Alternative ist.

Die geht klar. Zumindest wenn deine Laufzeit größer als ~10 Millisekunden ist

ComputerCarl Mitglied 18:07:16 25.05.2012 Titel:

Der Link für das GNU package auf der Seite geht leider nicht.
Ich habe aber Vergleiche mit Comilitonen und einer Implementierung
meines Übungsleiters. Also die nicht parallele Version von mir
und den anderen liegt wirklich weit ab vom Schuss. Leider weiß ich
nicht wo der Geschwindigkeitgewinn bei der anderen Implementierung
gerkommt, aber anders als durch Parallelisierung kann ich mir das
nicht erklären.

als Release-Version kompiliert:
Ich bin leider mit solchen Begriffen nicht vertraut... sorry.