[gelöst Danke]Parallelisierung einer For-Schleife

[ComputerCarl]

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:

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]

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)

[Gast]

ComputerCarl schrieb:

Windows XP System

Was bist du denn? Ein Höhlenmensch?

Sieht es nicht danach aus, dass er Threads will?

[ComputerCarl]

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.]

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.

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]

[quote="Hacker"]

ComputerCarl schrieb:

Was bist du denn? Ein Höhlenmensch?

... mehr möchte ich dazu nicht sagen ...

[ComputerCarl]

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.]

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

[Gast]

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]

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.

[Michael E.]

ComputerCarl schrieb:

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

Darum solltest du dich als erstes kümmern: Finde in deiner IDE einen Schalter, bei dem du "Debug" und "Release" einstellen kannst. Stelle ihn auf "Release", kompiliere neu und teste das generierte Programm außerhalb der IDE (üblicherweise liegt es in einem Ordner namens "Release").

[cooky451]

UND VOR ALLEM: Nutze keinen Compiler aus dem letzten Programmierjahrtausend.

[ComputerCarl]

Also in Dev C++ finde ich solche Einstellungen nicht und
in dem jetzt frisch gedownloadten Eclipse finde ich mich
nicht zurecht. Könnten wir also nochmal die eigentliche
Frage in den Mittelpunkt der Diskusion stellen?
Ich mein, wichtig bleibt es ja so oder so...

[cooky451]

VS11 Beta installieren http://www.microsoft.com/visualstudio/11/en-us
parallel_for_each nutzen (Oder C++11 Features wie std::thread und std::future)
fertig.
Aber viel nützen wird dir das vermutlich nicht, ich tippe eher darauf, dass du irgendwo ganz unangenehme Performancelöcher hast. Aber ohne Code können wir dir da nicht helfen. Na zumindest hat VS11 einen Profiler, der zeigt dir dann schon was da so lange dauert.

[Tippgeber]

Wahrscheinlich löst sich das Performance-Problem schon dadurch, dass der Code mit GCC 4.7 übersetzt wird...

[ComputerCarl]

Was ist mit PerformanceLöcher gemeint? Unnötige Schleifen oder mehrfache Berechnugn gleicher Ergebnisse mache ich nicht. DP wird benutzt wo es geht.
Sonst werden nur Basisdatentypen und höchstens noch Vectoren verwendet.
Aber unabhängig davon wozu brauche ich denn noch diesen Profiler, wenn clock doch schon ausreicht?
Visual-Studio würde ich gerne vermeiden, da ich darin schon mal was gemacht hatte und einfach nicht wirklich zufrieden damit war. Ist es möglich das jemand mir das einfache Bsp. in meinem ersten Kommentar irgendwie in diese Threads umzuwandeln?
vielen Dank im voraus.

[cooky451]

Nö, das geht nicht. Warum? C++03 kennt keine Threads. Und dein Compiler kennt kein C++11.

[Michael E.]

cooky451 schrieb:

Aber viel nützen wird dir das vermutlich nicht, ich tippe eher darauf, dass du irgendwo ganz unangenehme Performancelöcher hast.

Ja, und zwar, dass er im Debug-Modus kompiliert.

ComputerCarl: Die Einstellung gibts auch bei Dev-C++. Den hab ich auch mal vor fast zehn Jahren verwendet, kann dir aber nicht mehr sagen, wo es geht. Wenn du im Release-Modus kompilierst, sind deine Performancesorgen höchstwahrscheinlich nicht mehr vorhanden.

[ComputerCarl]

Ich habe jetzt "MinGW" mit g++(GCC) 4.7.0 und mein Projekt ganz normal
compiliert wie es in Tutorials im Netz steht. (g++ Programm.cpp -o Programm.exe)
Der Geschwindigkeitsgewinn ist zwar merkbar (um die Hälfte reduziert), aber immer
noch nicht ausreichend für meine Zwecke.
Ist dieser Compiler ebenfalls nicht geeignet oder muss ich dem Compiler
noch zusätzliche Informationen geben, ähnlich der Release-Information?

[314159265358979__]

Übergib ihm mal als Flag -O3, das sollte einiges bringen.