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

ComputerCarl Mitglied 13:27:21 27.05.2012 Titel:

gprof zeigt die Dauer von Funktionen an. Und diese Schleifen in eine Funktion zu schreiben ist auch für mich nicht allzu schwer. Was auch immer mit richtig benutzt gemeint ist, ich habe das Programm benutzt und meinen Code für gprof so umstrukturiert, dass die interessanten (Funktions-)Zeiten rausgeschrieben wurden.

my_hash() findet zu einem Character den jeweiligen Indexeintrag. Zeitlich gesehen verläuft die Suche in der Alphabetgröße. Bei Nukleotiden, wie bei mir ,also nur 4 Einträge. Und weiter, ich weiß auch nicht wo dieser Hauer ist. Aber wenn das Programm an diesen Schleifen die meiste Zeit verbraucht, nehme ich an ist dort der Fehler. Oder gehe ich da falsch mit meiner Annahme? Ich verstehe die ständigen Nachfragen nicht. Ich habe gemessen. Hier ist die meiste Laufzeit aufgetreten. Fertig!

cooky451 Mitglied 13:37:59 27.05.2012 Titel:

ComputerCarl schrieb:

Und weiter, ich weiß auch nicht wo dieser Hauer ist.

Und das ist das Problem. Du willst aber auch keine 5 Minuten investieren und den Code posten. Ich verstehe nicht, warum du dich so dagegen sträubst. Natürlich können wir hier jetzt weiter rätselraten spielen, aber wenn du ordentliche Hilfe willst, dann poste den Code.

Unregistrierter

Scheinbar habe ich Probleme euch zu verstehen. Der Code der lange dauert ist schon gepostet. Warum sollte der Rest-Code der unabhängig von dem geposteten Code ist und keine lange Laufzeit aufweist, die lange Laufzeit produzieren? Also warum soll den noch Code gepostet werden, wenn keine Verbindung besteht? Aber ich bin dann jetzt erstmal den Feiertag genießen. Das wünsche ich auch allen anderen hier.

Aber nur als kurzen Anhang:
Ich habe die Messung gemacht. Dort ist die Laufzeit. Ich bin wirklich dankbar für die Hilfe, aber ich seh keinen Sinn ständig über Dinge zu reden die ich nicht gefragt habe. Das ist jetzt wirklich nicht respektlos gemeint, aber mich nervt es jetzt einfach, dass ständig irgendwas mit Profiler kommt und ich schon alle Messungen gemacht habe und das auch geschrieben habe.

cooky451 Mitglied 14:08:38 27.05.2012 Titel:

Computer Carl schrieb:

Also warum soll den noch Code gepostet werden, wenn keine Verbindung besteht?

Weil niemand hier Lust hat manuell den ganzen Kram zu durchsuchen, dauernd nachzufragen von welchem Typ denn Variable xyz ist und irgendwelche Vermutungen aufzustellen. (Wie dir jetzt schon gefühlte 5kkkkkkk mal gesagt wurde.)
Dir wurde ja bereits alles gesagt wonach du gefragt hast. (std::thread etc.) So weitermachen macht also keinen Sinn. Entweder du postest den Code, oder cya.

nurf Mitglied 13:35:07 28.05.2012 Titel:

Computer Carl schrieb:

Also warum soll den noch Code gepostet werden, wenn keine Verbindung besteht?

Damit wir damit ein Schweine-Geld verdienen können. Wird dann direkt an SAP, Oracle und Microsoft verkauft und fließt direkt in das aktuelle Produkt ein.
Einmal kurz das Forum durchstöbern, Code abgrasen und schon wandert das Geld aufs Konto. Einfacher kann man einfach kein Geld verdienen.

otze Mitglied 17:30:02 28.05.2012 Titel:

Computer Carl schrieb:

Also warum soll den noch Code gepostet werden, wenn keine Verbindung besteht?

Vielleicht, aber auch nur vielleicht, weil die Leute, die sich professionell mit hochoptimiertem numerischen Code auseinander setzen, sich bereit erklärt haben, das für dich zu profilen und genau zu sehen, wo das Problem ist? Um dir dann mit ihrem Wissen helfen zu können, das zu verbessern?

ich geb dir mal ein bekanntes Beispiel: die naive Matrix-Matrix-Multiplikation kann ohne Parallelisierung und irgendwelche algorithmischen Tricks um Faktor 40 beschleunigt werden. Mit parallelisierung holst du im Vergleich < Faktor 4.

Wenn ich auf deinen Code schaue, sehe ich zum Beispiel ganz spontan sowas:

C++:
for(int k = 0; k < states.size(); k++){ tmp_prob += forward_matrix[...+ k] * transition[k][j]; }

ist states.size() groß, kann das richtig richtig langsam sein, weil du für jeden lookup einen Cachemiss kriegst (Faktor 5-40 langsamer). Da ichs net profilen kann, kann ich jetzt auch nicht überprüfen, ob man durch Schleifentausch noch was reissen kann.

Athar Mitglied 18:28:02 28.05.2012 Titel:

Wenn du einfach nur einen Weg suchst, etwas parallel auszuführen, dann ist #pragma omp parallel for vor einer for-Schleife einer der simpelsten (dann mit -fopenmp kompilieren und linken). Es gibt eine Reihe von Regeln, die du dabei einhalten musst, insbesondere müssen die Iterationen unabhängig voneinander sein (gleichzeitig ausführbar und in beliebiger Reihenfolge). So etwas wie tmp_prob += ... ginge so schon einmal nicht, allerdings kann dir OpenMP auch da helfen (reduction). Jedoch muss die Anzahl der Iterationen groß sein, damit sich das lohnt ("groß" ist allerdings auch wieder relativ).

otze Mitglied 20:56:42 28.05.2012 Titel:

Kann mich jemand bestätigen?

Das hier:

C++:
1 2 3 4 5 6 7 8 9	for(int i = 1; i < data[n].size(); i++) { for(int j = 0; j < states.size(); j++) { double tmp_prob = 0; for(int k = 0; k < states.size(); k++) { tmp_prob += forward_matrix[... + (i-1) * states.size() + k] * transition[k][j]; } } }

sieht mir sehr wie eine Matrix-Matrix multiplikation aus. Der Code ist leider etwas undurchsichtig, weswegen ich das nicht 100% validieren kann. Aber in dem Fall müsste zum beispiel ATLAS oder Eigen an der Stelle bis zu Faktor 40 raus kriegen.

Michael E. Mitglied 22:23:57 28.05.2012 Titel:

otze schrieb:

Kann mich jemand bestätigen?

Das hier: [...]
sieht mir sehr wie eine Matrix-Matrix multiplikation aus.

Jo. Passt zum Algorithmus.

dimiKL Mitglied 23:54:52 28.05.2012 Titel:

Hallo,

viele schreiben, man sollte an den Optionen für den Compiler etwas machen und hoffen,dass er dann gut optimiert. Einfache Optimierungen kann man aber auch selbst machen.
- Methoden-/Funktionsaufrufe vermeiden,
- Teil-Offsets berechnen und verwenden
- 1-dim. Felder verwenden. (Mehrdim. Felder nur bei wirklich großen Datenmenge, mehrere GB)

Zum Beispiel:

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93	int numStates = (int)states.size(); int sizeData = (int)data.size(); int statesMulLength = numStates * max_length; int matrixSize = statesMulLength * sizeData; double* forward_matrix = new double[matrixSize]; double* backward_matrix = new double[matrixSize]; double* seq_prob = new double[sizeData]; for(int i=0; i < matrixSize; i++) { forward_matrix[i] = 0; } for(int i=0; i < matrixSize; i++) { backward_matrix[i] = 0; } for(int i=0; i < sizeData; i++) { seq_prob[i] = 0; } //int matIdx; int matRowOffset; int matRowOffsetLoopConst; int data_nsize; for(int n = 0; n < sizeData; n++) { // Berechnung aller Forward-Matrizen matRowOffsetLoopConst = statesMulLengthn; data_nsize = data[n].size(); int hash_value = my_hash(data[n][0], alphabet); for(int i = 0; i < numStates; i++) { forward_matrix[matRowOffsetLoopConst + i] = start[i] emission[i][hash_value]; } matRowOffset2 = matRowOffsetLoopConst + numStates; for(int i = 1; i < data_nsize; i++) { hash_value = my_hash( data[n][i], alphabet); for(int j = 0; j < numStates; j++) { double tmp_prob = 0; for(int k = 0; k < numStates; k++) { tmp_prob += forward_matrix[matRowOffset + k] * transition[k][j]; } forward_matrix[matRowOffset2+ j] = tmp_prob * emission[j][hash_value]; } matRowOffset += numStates; matRowOffset2 += numStates; } // Berechnung aller Backward-Matrizen matRowOffset = matRowOffsetLoopConst + (data_nsize-1)numStates; for(int i = 0; i < numStates; i++) { backward_matrix[matRowOffset + i] = 1; } matRowOffset = matRowOffsetLoopConst; int matRowOffset2 = matRowOffsetLoopConst + numStates(data_nsize-1); for(int i = data_nsize-2; i >= 0; i--) { hash_value = my_hash(data[n][i+1],alphabet); for(int j = 0; j < numStates; j++) { double tmp_prob = 0; for(int k = 0; k < numStates; k++) { tmp_prob += backward_matrix[matRowOffset2 + k] * transition[j][k] * emission[k][hash_value]; } backward_matrix[matRowOffset + j] = tmp_prob; } matRowOffset += numStates; matRowOffset2 -= numStates; } // Berechnung der Sequenz-Wahrscheinlichkeiten matRowOffset = matRowOffsetLoopConst + 1numStates; double sp= 0; for(int i = 0; i < numStates; i++) { sp += backward_matrix[matRowOffset + i] forward_matrix[matRowOffset + i]; } seq_prob[n] = sp; }

Für parallele Implementierung, falls es hier möglich. Empfehle ich OpenCL oder CUDA (für NVIDIA Grafikkarten). OpenCL funktioniert nicht nur mit GPUs, sondern auch mit CPUs, wenn die entsprechenden Libs vorhanden/installiert sind.

PS: Der Code oben kann Fehler enthalten. Hoffe die Idee ist klar.