Schleife parallelisieren

[MadMax]

Hi,

ich würde mein Programm geren auf Multicore architekturen optimieren. Zuerst dachte ich da an OpenMp als Lip. Allerdings bin ich gerade nicht mehr sicher ob das überhaupt geht.
Das Problem ist das ich einen Schleife habe deren länge erst zur Laufzeit bekannt ist. Die Frage ist nun ob und wie das mit OpneMp funktioniert. Alternativ wie kann ich den in C++ dynamisch einen neuen Thrad anlegen ?

Danke
Manuel

[kimmi]

Sind die einzelnen Loopdurchläufe von dem jeweils vorherigen Durchlauf abhängig? Wenn nein : [1], wenn ja[2]. Die Datenabhängigkeiten machen das Parallelisieren so richtig knifflig. Manchmal muß man den jeweiligen Algorithmus noch etwas anpassen, um bei der Parallelisierung etwas ehrausholen zu können.

Und mit c++ Bordmitteln allein kannst du keinen Thread-Context anlegen. Dafür benötigst du betriebssystem-spezifische API-Calls. Die Boost.Thread Library ist da aber ziemlich gut und sehr zu empfehlen ( siehe [3] ).

Gruß Kimmi

[1] http://de.wikipedia.org/wiki/OpenMP
[2] http://rac.uits.iu.edu/hpc/openmp_tutorial/C/3.html
[3] http://www.boost.org/doc/libs/1_40_0/do ... hread.html

[MadMax]

Hi,

danke dir erstmal. Die einzelnen Schleifenabläufe sind völlig unabhängig voneinander. Sie lesen allerdings die selben Daten. Und OpenMp kann auch mit dynamischen schleifen umgehen ? habe bisher nur beipiele mit statischen gefunden .

[glassbear]

Hi,

danke dir erstmal. Die einzelnen Schleifenabläufe sind völlig unabhängig voneinander. Sie lesen allerdings die selben Daten. Und OpenMp kann auch mit dynamischen schleifen umgehen ? habe bisher nur beipiele mit statischen gefunden .

Ja, kann es, sonst wär es ja total nutzlos :?:

[kimmi]

Einer der Gründe, dass die Compiler C/c++ nicht so gut optimieren können wie F77/F90 ist der, daß allein schon vom Syntax die Schleifen in C/C++ variabel in der Anzahl der Durchläufe sind. Von daher kommt das echt besser, wenn OpenMP damit umzugehen weiß. Das mußte ich aber auch erst probieren, um das wirklich zu verstehen.

Gruß Kimmi

[MadMax]

Ok Danke für die Antworten. Ich habe es jetzt mal ausprobiert allerdigns mit mäßigem Erfolg. Entweder das Programm stürtz ab oder aber es wird nur ein Bruchteil der berechnungen durchgeführt.

[Aramis]

Main Ratschlag besteht darin, auf OpenMP zu verzichten und mit boost.threads manuell zu parallelisieren. Etwas mehr Arbeit, aber dafür beruht die Parallelisierung nicht auf ein paar Compiler-Hacks, nichts anderes sind #pragma's ...

[kimmi]

Grundlegend stimme ich da Aramis zu. Man kann mittels OpenMP zwar nachträglich versuchen, Parallelisierung zu seiner Anwendung hinzuzufügen. Will man aber eine optimalere Lösung haben, kommt man um die manuelle Arbeit nur schwer herum.

Gruß Kimmi

[Lord Delvin]

Main Ratschlag besteht darin, auf OpenMP zu verzichten und mit boost.threads manuell zu parallelisieren. Etwas mehr Arbeit, aber dafür beruht die Parallelisierung nicht auf ein paar Compiler-Hacks, nichts anderes sind #pragma's ...

Das Argument ist nicht wirklich gut und ehrlich gesagt kann ich dir auch nicht zustimmen, da parallelisierung mit threads natürlich bessere Ergebnisse liefert, allerdings nur wenn du genau weist, was du tust. Wenn nicht verbringst du sehr viel Zeit damit dir auf kryptische Weise in den Fuß zu schießen.
Das Problem löst OpenMP imo relativ gut. Nach eingehender Befassung mit dem Thema würde ich beides verwenden: Für gut parallisierbare Prozesse wie Ressourcenmanagement o.ä. würde ich Threads nehmen, für den hauptprozess OpenMP, weil du einfach nicht darüber nachdenken willst, wie du den weiter parallelisierst.

[glassbear]

Ok Danke für die Antworten. Ich habe es jetzt mal ausprobiert allerdigns mit mäßigem Erfolg. Entweder das Programm stürtz ab oder aber es wird nur ein Bruchteil der berechnungen durchgeführt.

Hast du vorher eine Analyse gemacht, dass die einzelnen Schleifendurchläufe auch wirklich unabhängig von einander sind? Auch Speicher-Allokationen, etc.?

[MadMax]

Code: Alles auswählen

#pragma omp parallel for private(p,i)
for( i=0;i<5826;i++){
	p = this->app_scene->get_patch(i);
	if(!p->child[0]) {
		p->exitant_anti_radiant_intensity->clear(); 
		p->exitant_anti_radiant_intensity->transform_extAntiRad(p->incident_radiance);
		p->total_radiant_intensity->transform_totalRad(p->incident_radiance);}
}

Ich bin mir eigentlich sicher das keine Abhänigkeiten innerhabl der schleife vorhanden sind. Das ist jetzt das einfachste was ich ausprobiert habe. Die Schleife berechnet einfach die abgestrahlte Radiance für jeden Patch. die einfahllende Radiance leigt vor. Jeder Thread braucht also nur zugriff auf die werte von einem Patch. Wen ich die openMp zeile rausnehme funktioniert alles. Ist sie eingeschalltet bleibt eine gewisse Anzahl der Patches schwarz.

[Chromanoid]

Wenn ich das richtig verstehe müsstest du einfach einen threadpool benutzen können...
http://en.wikipedia.org/wiki/Thread_pool_pattern

Bau einfach ein thread-Objekt, was mit i_start und i_end parametrisiert wird (+readonly variablen falls die nicht global sind). Dann macht jeder Thread nur einen Teil der Schleife. Kannst ja dann rumprobieren welche Stückelung am effektivsten ist (je nach prozessoranzahl oder so...). Die Threads haust du dann einfach in den threadpool und fertig...

vielleicht ist das nützlich: http://threadpool.sourceforge.net/

[Lord Delvin]

Sind die funktionen die du verwendest threadsafe? Also am besten als const T f(...) const deklariert?

Den Fehler den man am Anfang gerne macht ist anzunehmen, dass man nichts kaputt machen kann, wenn die Daten parallel sind. Die eigentliche Berechnung muss das auch sein.

Ich bin im übrigen grad über ompP gestolpert. War ziemlich schnell installiert, ist leicht zu bedienen und sieht ziemlich hilfreich aus:)

EDIT: Imo müsstest du in der omp Zeile auch eine Aussage über die Daten treffen die du von getpatch bekommst.

[MadMax]

Eigentlich sollte das ja ganz einfach sein jeder Prozesser bekommt pro schleifendurchlauf genau die daten von einem patch