[gelöst Danke]Parallelisierung einer For-Schleife

ComputerCarl

Haha, nein bin ich wirklich nicht, sorry.

Aber dennoch ändert sich nichts an dem was ich gesagt habe.
Ich mein eine leicht veränderte Semantik heißt für mich nicht
gleich, dass Dinge falsch werden. (Das Wort "leicht" hat für
mich irgendwie was anderes impliziert. Egal...)
Und gprof: Ja ok. Bringt mir auch nicht mehr Infos über den
zeitlichen Ablauf als clock(). Die Zeit bleibt in den
for-schleifen. Und nein, ich kopiere nichts etc. Ich berechne
nur die Forward- und Backward-MAtrix wie schon beschrieben und
so wie sie definiert sind.

Weiter habe ich die Dimensionsanzahl auf 1 reduziert. Musste aber
dennoch einen Vector nehmen, da bei einem Array die exe einfach
abbricht. Hat das was mit diesem Stack-Overflow zu tun?

Ok. Sollte also nichts mehr zu der Parallelisierung gesagt werden,
danke auf jedenfall nochmal für die Compiler-tipps und etc.

cooky451

Wenn du einfach mal den Code posten würdest, könnte man den dir auch schneller machen.

ComputerCarl

Oh, das klingt echt super.
Um es ein bisschen übersichtlicher zu machen, habe ich alle Logarithmen
und Scalierungen entfernt. Sollte irgendwo dennoch ein exp() oder log()
stehen, nicht wundern.

vector<double> forward_matrix (data.size() * max_length * states.size(),0);
vector<double> backward_matrix(data.size() * max_length * states.size(),0);
vector<double> seq_prob (data.size(), 0);

for(int n = 0; n < data.size(); n++) {
   	// Berechnung aller Forward-Matrizen
   	for(int i = 0; i < states.size(); i++)
   	{ forward_matrix[n * states.size() * max_length + i] = start[i] * emission[i][my_hash(data[n][0], alphabet)]; }	

	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[n * states.size() * max_length + (i-1) * states.size() + k] * transition[k][j]; }

			forward_matrix[n * states.size() * max_length + i * states.size() + j] = tmp_prob * emission[j][my_hash(data[n][i], alphabet)];
		}
	}

	// Berechnung aller Backward-Matrizen
        for(int i = 0; i < states.size(); i++)
	{ backward_matrix[n * states.size() * max_length + (data[n].size()-1) * states.size() + i] = 1; }

	 for(int i = data[n].size()-2; i >= 0; i--) {
		for(int j = 0; j < states.size(); j++) {

                 	double tmp_prob = 0;
			for(int k = 0; k < states.size(); k++)
			{ tmp_prob += backward_matrix[n * states.size() * max_length + (i+1) * states.size() + k] * transition[j][k] * emission[k][my_hash(data[n][i+1],alphabet)]; }

			backward_matrix[n * states.size() * max_length + i * states.size() + j] = tmp_prob;
		}
	}

	// Berechnung der Sequenz-Wahrscheinlichkeiten
	seq_prob[n] = 0;
	for(int i = 0; i < states.size(); i++)
        {seq_prob[n] += backward_matrix[n * states.size() * max_length + 1 * states.size() + i] * forward_matrix[n * states.size() * max_length + 1 * states.size() + i]);}
}

Michael E.

Du hast immer noch mehrdimensionale Vektoren.

ComputerCarl

Ich dachte, ich hätte die mehrdimensionalen Vectoren entweder
1-dimensional gemacht oder mit Arrays ersetzt. Und ich glaub,
ich bin schon ganz blind für den Code geworden, aber ich sehe
keine mehrdimensionale Vectoren mehr.
emission und transition sind eigentlich Arrays. Aber das hätte
ich wohl deutlich machen sollen. Kommt es bei Arrays auch zu
Problemen, wenn sie mehrdimensional werden?

cooky451

ComputerCarl schrieb:

Kommt es bei Arrays auch zu
Problemen, wenn sie mehrdimensional werden?

Nein.
Was ich aber meinte war kompilierbaren Code (am besten in einer Datei), dann kann man nämlich einfach nen Profiler drüber laufen lassen und muss die Arbeit nicht selbst machen. (Und bitte einheitlich einrücken..)

ComputerCarl

Hier steh ich kurz noch auf dem Schlauch.
Also ich kann schnell noch kompilierbaren Code
draus machen, würde aber auch nur data.size und
so auf irgendwelche Konstanten setzen.
Ich dachte ein Profiler ist zur Zeitmessung da.
Der kann auch Dinge parallelisieren?
Ich wollte nur Fragen bevor ich sinnlos Code
umschreibe.

SeppJ

ComputerCarl schrieb:

Ich dachte ein Profiler ist zur Zeitmessung da.
Der kann auch Dinge parallelisieren?

Der allgemeine Verdacht der hier vorherrscht ist, dass dein Programm nicht langsam ist, weil es nicht-paralllel ist, sondern dass es langsam ist, weil es schlecht geschrieben ist. Mit vollständigem Code könnten wir dies beurteilen.

ComputerCarl

Ich dachte, ich hatte schon erwähnt, dass ich sowohl mit gprof
und anfänglich mit clock Messungen vorgenommen habe. Der Teil,
der in meinem Programm mehr als 77% der Zeit in Anspruch nimmt,
habe ich oben abgetippt.
Ich sehe deshalb keine Notwendigkeit das Problem noch komplexer
zu machen indem ich den ganzen Code hochlade. Ausserdem sehe ich
irgendwie nicht, dass meine eigentliche Frage mit der
Parallelisierung diskutiert wird. Das ist auch o.k. so, aber die
ganze Compiler, Vector-Geschichte ist eigentlich wirklich nicht
das was mich gerade so interessiert.

SeppJ

Wenn du selber so gut beurteilen kannst, was das richtige ist, dann brauchst du ja keine Ratschläge mehr. Sehr erstaunlicher ist auch, dass gprof dir den Code bis auf deine for-Schleife aufgelöst hat, denn das kann es eigentlich gar nicht. Man könnte sogar meinen, du hättest es gar nicht richtig benutzt. Wenn sich jedenfalls bei so exzessiver Benutzung von vector in Schleifen mit ansonsten trivialen Rechenschritten (bis auf das uns unbekannte my_hash) kein riesiger Unterschied zwischen unoptimiert und hochoptimiert ergibt, dann ist eigentlich für jeden klar, dass da etwas nicht stimmt. vector ohne Optimierungen ist saulangsam. Kleine Schleifen auch. Aber mit Optimierung wird normalerweise beides ungeheuer schnell. Siehe auch hier:

http://www.c-plusplus.net/forum/p2215569#2215569
http://www.c-plusplus.net/forum/p2215810#2215810

Wenn das bei dir so sehr anders ist, dann machst du höchstwahrscheinlich irgendeinen ganz dicken Hauer im Programm. Jeder weiß es, jeder sagt es, nur du möchtest es nicht hören.

P.S.:
Bitte
hör
auf
selbst
die
Zeilen-
um-
brüche
in deinem
Text
zu
setzen.
Nicht
jeder
hat
so
einen
kleinen
Bildschirm
.

ComputerCarl

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

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.

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

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

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

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:

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

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

Kann mich jemand bestätigen?

Das hier:

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.

otze schrieb:

Kann mich jemand bestätigen?

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

Jo. Passt zum Algorithmus.

dimiKL

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:

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 = statesMulLength*n;
       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 + 1*numStates;

    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.