[gelöst Danke]Parallelisierung einer For-Schleife

ComputerCarl

Also ich habe erneut mit clock() Messungen durchgeführt und die meiste Zeit
geht in den 3-verschachtelten for-Schleifen drauf. (Die sind notwendig:
erste geht über alle Daten und die beiden Folgenden gehen über die Zeilen
und Spalten der Forward- und Backwardmatrix der jeweiligen Sequenz) Die Berechnung der Schätzer nimmt weniger Zeit ein. Sollte, aber vermutlich auch parallelisiert werde.
Ich werde mich jetzt einfach in die threads reinlesen. Danke nochmal an alle
Mitdiskutierer.

Michael E.

Wie sieht deine Definition von data_array aus? Sind das verschachtelte std::vector ? Wenn ja, geht dir hier die Cachelokalität flöten. Dazu findest du genügend Threads.

SeppJ

Was soll denn dieses Gemesse mit clock? GCC unterstützt nativ den gprof. Einfach mit -pg (und Optimierung!) compilieren und das Programm mit einem kleinen(!) Testfall testen. Danach hat man eine sehr genaue Auflistung was im Programm wie lange braucht. Ganz ohne eigene Annahmen die das Ergebnis verfälschen. Und viel einfacher zu bekommen.

Und wie schon gesagt, kann zwischen keine Optimierung und O3 eigentlich nicht nur ein paar Sekunden von ein paar Minuten gewonnen werden. Zumindest bei "richtigen" Rechnungen sollte O3 einen Faktor 5 bis 20 bringen. Wenn dies nicht so ist, dann wirst du höchstwahrscheinlich irgendwelche Dummheiten machen, z.B. ewig lange Systemaufrufe oder riesige Kopieraktionen, bei denen die Optimierung des eigenen Programms nicht viel ausmacht.

(Es gibt in neueren GCCs, wie dem 4.7, übrigens auch noch Ofast für noch heftigere Optimierung, aber da sollte man verstehen was dies genau tut, da es die Semantik leicht verändern kann.)

ComputerCarl

Also ich habe heute und gestern Abend noch einige Optionen mit dem Compiler
ausprobiert. die -Ofast liefert mir interessanter Weise falsche Ergebnisse.
Lasse ich diesen weg kommen wieder korrekte Ergebnisse. Das ist zumindest
für mich leicht irritierend. Ich weiß nicht was mit "richtigen" Rechner
gemeint ist, aber ich hab nur einen sehr kleinen und sehr, sehr alten Rechner.
Also vermute ich mal, dass das damit gemeint ist.

Der -pg flag ändert irgendwie nichts. Jedenfalls nicht in der Konsolenausgabe.
Nach Beendigung des Programms wird eine Datei.out beschrieben. Diese kann ich
jedoch nicht lesen, da nur kryptische Zeichen drin stehen. Ich weiß aber auch
nicht mit welchem Programm ich das öffnen muss.

Mein Data-Array war ursprünglich ein 3-Dim Vector. Nun ist es ein 2-Dim Array:
1-Dim ist die jeweilige "Datenpunkt", 2-Dim indexiere ich mit i * Spalte + j
selbst. Also dürften keine Cachelokalität mehr eine Rolle spielen. Oder doch?

cooky451

Na am besten ist alles am Stück (1-Dimensional) im Speicher zu halten und den Index zu berechnen.

SeppJ

ComputerCarl schrieb:

Also ich habe heute und gestern Abend noch einige Optionen mit dem Compiler
ausprobiert. die -Ofast liefert mir interessanter Weise falsche Ergebnisse.
Lasse ich diesen weg kommen wieder korrekte Ergebnisse. Das ist zumindest
für mich leicht irritierend. Ich weiß nicht was mit "richtigen" Rechner
gemeint ist, aber ich hab nur einen sehr kleinen und sehr, sehr alten Rechner.
Also vermute ich mal, dass das damit gemeint ist.

Der -pg flag ändert irgendwie nichts. Jedenfalls nicht in der Konsolenausgabe.
Nach Beendigung des Programms wird eine Datei.out beschrieben. Diese kann ich
jedoch nicht lesen, da nur kryptische Zeichen drin stehen. Ich weiß aber auch
nicht mit welchem Programm ich das öffnen muss.

Du bist nicht besonders gut mit diesem "Internet", oder?

http://www.tty1.net/smart-questions_de.html#answers
http://searchengineland.com/guide/how-to-use-google-to-search

SeppJ schrieb:

Was soll denn dieses Gemesse mit clock? GCC unterstützt nativ den gprof. Einfach mit -pg (und Optimierung!) compilieren und das Programm mit einem kleinen(!) Testfall testen. Danach hat man eine sehr genaue Auflistung was im Programm wie lange braucht. Ganz ohne eigene Annahmen die das Ergebnis verfälschen. Und viel einfacher zu bekommen.

Und wie schon gesagt, kann zwischen keine Optimierung und O3 eigentlich nicht nur ein paar Sekunden von ein paar Minuten gewonnen werden. Zumindest bei "richtigen" Rechnungen sollte O3 einen Faktor 5 bis 20 bringen. Wenn dies nicht so ist, dann wirst du höchstwahrscheinlich irgendwelche Dummheiten machen, z.B. ewig lange Systemaufrufe oder riesige Kopieraktionen, bei denen die Optimierung des eigenen Programms nicht viel ausmacht.

(Es gibt in neueren GCCs, wie dem 4.7, übrigens auch noch Ofast für noch heftigere Optimierung, aber da sollte man verstehen was dies genau tut, da es die Semantik leicht verändern kann.)

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.