3. [gelöst Danke]Parallelisierung einer For-Schleife

[gelöst Danke]Parallelisierung einer For-Schleife

  • C

    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.

    0
  • M

    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?

    0
  • C

    [quote="Hacker"]

    ComputerCarl schrieb:

    Was bist du denn? Ein Höhlenmensch?

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

    0
  • C

    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.

    0
  • M

    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

    0
  • ?

    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 😃

    0
  • C

    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.

    0
  • M

    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").

    0
  • C

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

    0
  • C

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

    0
  • C

    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.

    0
  • ?

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

    0
  • C

    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.

    0
  • C

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

    0
  • M

    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.

    0
  • C

    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?

    0
  • ?

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

    0
  • ?

    ... sowie -march=native

    0
  • C

    Die Einstellungen bringen auch einige wichtige Sekunden, aber die Rechnungen
    dauern immernoch Minuten. Müssen sie auch, es geht um große Datenmengen. Aber das
    alles bringt mich wieder zurück zur Parallelisierung. Bzw. gibt es noch weitere
    Compiler-technische Vorschläge?

    0
  • E

    Nö. Jetzt solltest du einen Profiler auspacken und nachsehen, wo das Programm am Längsten braucht.
    Wenn sich das Problem gut parallelisieren lässt, mach ruhig, schau dir dazu std::thread/std::mutex/std::fure an.

    0
Anmelden zum Antworten