[gelöst Danke]Parallelisierung einer For-Schleife

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.

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?

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

... sowie -march=native

ComputerCarl

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?

Ethon

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.

cooky451

Zwischen O0 und O3 liegen nur sekunden? Zeig vielleicht doch mal deinen Code.
Ansonsten mit 4.7 kannste std::thread nutzen und std::future nutzen.

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]);}
}