Parallelisierung mit OpenMP / Dynamisch threads erzeugen

[earli]

Exponentiell viele Threads durch binäre Verzweigungen klingen nach einer eher blöden Idee.

Generier lieber dynamisch einen Baum und lasse die Knoten jeweils von so vielen Threads bearbeiten/weiter expandieren, wie für den Rechner sinnvoll scheint.

Oder C ist die falsche Sprache.

[Zeus]

http://wolfgang.dautermann.priv.at/OpenMP-Vortrag-CLT2008.pdf

[noobLolo]

also ich würd für sowas eher klassische threads (weniger fork, eher posix) nehmen und dann die die schleifen optimierung in den threads mit openMP machen und die anzahl in openMP auf die reale cpu kern zahl einstellen...

[Stefan_O]

Das heißt also mit OpenMP ist sowas nicht einfach machbar und es ist auch nicht sinnvoll das so mit Threads zu lösen. Ich habe wie gesagt noch nie mit Threads gearbitet, auch nicht mit "klassischen". Ich habe mich für OpenMP entschieden weil es Plattform-unabhängig ist und ich es gut fände wenn mein Programm problemlos auf Windows/Linux/Mac OS X läuft, ohne das ich OS-spezifischen Kram brauch.

Ich habe mir mal folgendes überlegt:

datentyp *liste_start, *liste_end, *ergebnisse, *var, *varb;
int weiterrechnen=1;

liste_start = liste_end = InitListe();

#create threads 
while(weiterrechnen)
{
#critical
	if (liste_start == NULL)
	{
		/*
		???
		*/
	}
	var = liste_start;
	liste_start = liste_start->next;
	liste_start->prev = NULL;
#end critical
	for(;var->i<N && weiterrechnen;var->i++)
	{
	    if(RechneWas(var))
	    {
	        varb = CopyVar(var);
	        RechneA(var);
	        RechneB(varb);
#critical
			liste_end->next = varb;
			varb->prev = liste_end;
			liste_end = varb;
#end critical
	    }
	}
	if(IstBrauchbar(var))
	{
#critical
	    ergebnisse->next = var;
	    var->prev = ergebnisse;
	    ergebnisse = var;´
#end critical
	}
	if(IstPerfekt(var))
	{
#critical
	    weiterrechnen=0;
#end critical
	}
}
#barrier
Print(ergebnisse);

Die Frage ist nun was muss bei den ??? hin. Ohne Threads ist klar, da kann ich einfach break machen (bzw. das in die while-bedingung reinziehn). Bei mehreren Threads kann das aber unterschiedliche Gründe haben:
a) Es gibt nichts mehr zun tun -> break
b) Es gibt zur Zeit nichts zu tun, aber es kommt wieder was.
Gibt es eine einfache Möglichkeit zu sagen das der Thread hier warten soll an Punkt A bis irgendein anderer Thread Punkt B erreicht hat (in dem beispiel wäre das zeile 31/32) und dann weitermachen und falls alle Threads an diesem Punkt A warten -> break;
Wenn ich das hätte wäre mein Problem denke ich gelöst, ich gehe davon aus das Speicher den ich mit malloc innerhalb eines Threads hole erhalten bleibt wenn der Thread zu ende ist (barrier erreicht) oder muss ich da was beachten?

Eine Parallelisierung der inneren Schleife ist so einfach nicht möglich, da die einzelnen Durchläufe nicht unabhängig voneinander sind und die unabhängig zu machen wäre zwar möglich, würde aber sehr viele Berechnungen verdoppeln, und da ich so bereits sehr viele Threads auslasten kann denke ich, dass das nicht sinnvoll ist. Eine Parallelisierung innerhalb der Schleife wäre immer nur für ein paar befehle machbar, da kann man eher was mit SSE2/SSE3 machen, aber das fang ich erst an wenn der Rest läuft.

Vielen Dank
Stefan

[Stefan_O]

Ich hab mal die OpenMP-Specs durchgeschaut und denke die einzige Möglichkeit ein Thread zum anhalten zu bewegen sind locks. Die Idee ist ich setze ein Lock bevor ich der Datensatz eingelesen wird und hebe den Lock wieder auf wenn dann noch ein Datensatz in der Liste ist. Dann wartet jeder Thread wenn kein Datensatz da ist.

Das Problem ist nun: Wenn ein neuer Datensatz kommt muss der Lock wieder aufgehoben werden. Das kann der Thread der den Lock gesetzt hat mit omp_unset_lock machen, hier müsste es aber jeder Thread können. Würde das mit

omp_destroy_lock(&nodata);
omp_init_lock(&nodata);

gehen oder was passiert wenn ein lock zerstört wird, der gerade gesetzt ist? Dazu schweigt sich die Spezifikation nämlich aus.

Vielen Dank
Stefan

[noobLolo]

noobLolo schrieb:

also ich würd für sowas eher klassische threads (weniger fork, eher posix) nehmen und dann die die schleifen optimierung in den threads mit openMP machen und die anzahl in openMP auf die reale cpu kern zahl einstellen...

hab mir gestern dazu ein bischen was auf mdsn durchgelesen, scheint so als könnte openMP fork und pthreads fast vollständig ersetzen, muß eingestehen das ich damit bisher nur testweise schleifen parallelisiert habe

den link will ich dir natürlich nicht vorenthalten, es ist auch ein bsp. dabei für ein Quicksort mit Parallelen Sections

void QuickSort (int numList[],  int nLower, int nUpper) 
   {
   if (nLower < nUpper)     
      {
      // create partitions
      int nSplit = Partition (numList, nLower, nUpper);
      #pragma omp parallel sections
      {
         #pragma omp section
         QuickSort (numList, nLower, nSplit - 1);

         #pragma omp section
         QuickSort (numList, nSplit + 1, nUpper);
      }
   }
}

http://msdn.microsoft.com/en-us/magazine/cc163717.aspx

lg lolo

[Stefan_O]

Das ist ja genial simpel, würde aber bei mir jedoch vermutlich mehrere hunderte, wenn nicht gar tausende Threads erzeugen, ist das performace-technisch sinnvoll?
Aber das dürfte bei Quicksort nicht anders sein wenn ich da ne Liste mit hunderttausenden Einträgen habe.
Das könnte man ungefähr so machen:

int stop=0;
datatyp *result;

void calc(datatyp *var)
{
	datatyp *varb;
	for(;var->i<N;var->i++)
	{
	    #pragma omp critical stop
	    {
			if(stop) return;
	    }
	    if(RechneWas(var))
	    {
	        #pragma omp parallel sections
	        {
	            #pragma omp parallel section
	            {
	            	RechneA(var);
					calc(var);
				}
				#pragma omp parallel section
	            {
	            	varb = CopyVar(var)
	            	RechneB(varb);
					calc(varb);
				}
			}
			return;
	    }
	}
	if(IstBrauchbar(var))
	{
	    #pragma omp critical result
	    {
		    result->next = var;
		    var->prev = result;
		    result = var;
	    }
	}
	if(IstPerfekt(var))
	{
		#pragma omp critical stop
	    	stop=1;
	}
}

Die Frage ist nun ob das mit den critical sections so funktioniert, weil das gilt ja nicht nur innerhalb der Funktion, sondern über alle Funktionsaufrufe insgesamt.

Vielen Dank
Stefan

[Blue-Tiger_loggedoff]

Stefan_O schrieb:

Das ist ja genial simpel, würde aber bei mir jedoch vermutlich mehrere hunderte, wenn nicht gar tausende Threads erzeugen, ist das performace-technisch sinnvoll?

Nein, garantiert nicht. Da geht viel zu viel Zeit fuer Verwaltungsaufwand drauf. Allerdings kannst du OpenMP ja sagen, wieviel threads maximal erzeugt werden sollen. Allerdings weiss ich grad nicht was passiert wenn du mehr sections hast als es threads gibt.
Was ich an deiner Stelle tun wuerde, ist, die Neuerungen von OpenMP 3.0 genauer anzuschauen, speziell die "tasks". Damit kannst du deine einzelnen Jobs in "Tasks" einteilen, die dann auf die vorhandenen Threads aufgeteilt werden. Allerdings koennen noch nicht alle Compiler OpenMP 3.0 (der GCC kanns ab 4.3.1, der MSVC kanns glaub ich gar nicht).

[Stefan_O]

Ich hab mein programm grob so fertig das es läuft, er erzeugt standardmäßig nur so viele Threads wie es Prozessorkerne gibt. Werde nachher mal ein paar Performance-Tests machen. Beim debuggen war das programm mit openmp angeschaltet nur ungefähr halb so schnell wie ohne, ich hoffe das lag am debugger.
Kann den GCC in MinGW auch openmp (ich hab version 4.4.1 x64)?

Noch mal eine andere Frage: wenn ich auf shared variable zugreife die auch beschrieben von threads muss ich das in ein critical tun? oder nur den bereich wo geschreiben wird? was ist der genaue unterschied zwischen critical und atomic?
muss ich flush verwenden am ende von critical um sicherzugehen das die variable gleich für alle threads geändert sichtbar ist?

Vielen Dank
Stefan

[Blue-Tiger]

Stefan_O schrieb:

Kann den GCC in MinGW auch openmp (ich hab version 4.4.1 x64)?

Obs die offiziellen Releases von mingw.org koennen, weiss ich nicht, die von TDragon konnten es zumindest frueher. Wie's heutzutage ausschaut musst du selbst probieren

Noch mal eine andere Frage: wenn ich auf shared variable zugreife die auch beschrieben von threads muss ich das in ein critical tun? oder nur den bereich wo geschreiben wird?

Auf jeden Fall in beide!!

was ist der genaue unterschied zwischen critical und atomic?

IIRC: Critical kann nicht von Threads unterbrochen werden, die auch in die Critical Section wollen. Atomic kann von keinem anderen Thread deines Programmes unterbrochen werden.

muss ich flush verwenden am ende von critical um sicherzugehen das die variable gleich für alle threads geändert sichtbar ist?

IIRC streiten sich darueber die Geister, d.h. es gibt keine "offizelle" Regel. Schaden tuts aber sicher nicht (ausser du kannst auf die paar µs Ausfuehrungszeit wirklich nicht verzichten). Bei ein paar Konstrukten macht OpenMP sowieso automatisch ein flush. Ob critical da dazu gehoert weiss ich nicht auswendig, muesstest du in der Spezifikation nachschauen.

[Stefan_O]

Mein mingw kann leider kein openmp (der kompiler schon, aber er macht keine exe, da fehlt "libgomp")

Hier ein kurzer performance test der doch einige merkwürdige überraschungen beinhaltet (Windows XP x64, AMD Athlon 64 X2 4200+):

MSVC8 x64 ohne OpenMP 0:59
MSVC8 win32 ohne OpenMP 2:51
MSVC8 x64 mit OpenMP 4:35
MSVC8 win32 mit OpenMP 4:35
MinGW x64 ohne OpenMP: 1:03

Ich habe jeweils drei Messungen gemacht und gemittelt, die Werte lagen aber auch alle +/- 3 Sekunden beieinander.
Ich habe mal gelesen x64 bringt ca. 10% mehr, bei meinem Programm ca. 290%. Wenn ich es nicht dreimal gemessen hätte würde ich es nicht glauben. Ich habe auch keine unterschiedlichen kompileroptionen für verwendet, ich habe x64 als neue Plattform angelegt und gesagt alle Einstellungen von win32 kopieren.
Ich weiß nicht ob mein Programm so stark von den 8 zusätzlichen Registern profitiert, denn ich rechne nur ein einer stelle mit einem 64-bit int.
Jedoch ist ein nicht geringer Teil meines Programms memcpy, dass verbraucht bestimmt 1/3 der gesamten zeit, vielleicht ist der zugrunde liegende code in der msvcr für x64 einfach deutlich besser als für win32.

Warum dass mit OpenMP so kontraproduktiv ist kann ich nur raten, es laufen immer nur 2 Threads, vermutlich beendet er aber einen wenn er fertig ist und legt dann wieder einen neuen an und erzeugt so ein extrem hohen overhead.
Ich habe den Testfall so konstruiert, dass er auf jeden Fall alle Pfade bis zum ende rechnet und er vorher nicht abbricht.

Ich werde mal schauen das ich das mit OpenMP 3.0 hinbekomme und versuchen das mit tasks zu machen. sonst noch ideen warum das so langsam ist und wie ich das optimieren kann?

Vielen Dank
Stefan

[Blue-Tiger]

Stefan_O schrieb:

Mein mingw kann leider kein openmp (der kompiler schon, aber er macht keine exe, da fehlt "libgomp")

Wie gesagt, zur Not mal das Release von TDragon ausprobieren.

Ich habe mal gelesen x64 bringt ca. 10% mehr, bei meinem Programm ca. 290%. Wenn ich es nicht dreimal gemessen hätte würde ich es nicht glauben. Ich habe auch keine unterschiedlichen kompileroptionen für verwendet, ich habe x64 als neue Plattform angelegt und gesagt alle Einstellungen von win32 kopieren.
Ich weiß nicht ob mein Programm so stark von den 8 zusätzlichen Registern profitiert, denn ich rechne nur ein einer stelle mit einem 64-bit int.
Jedoch ist ein nicht geringer Teil meines Programms memcpy, dass verbraucht bestimmt 1/3 der gesamten zeit, vielleicht ist der zugrunde liegende code in der msvcr für x64 einfach deutlich besser als für win32.

1. Ich mutaße mal, dass 32bit-Code auf 'ner 64bit-Plattform evtl. einen kleinen Nachteil hat.
2. Dein Programm besteht also hauptsaechlich aus memcpy. Auf 'ner 64bit-Plattform koennen wie der Name schon sagt 64bit auf einmal gelesen/geschrieben werden. Auf 'ner 32bit-Plattform nur 32. Also muesste memcpy doppelt so schnell funktionieren

Warum dass mit OpenMP so kontraproduktiv ist kann ich nur raten, es laufen immer nur 2 Threads, vermutlich beendet er aber einen wenn er fertig ist und legt dann wieder einen neuen an und erzeugt so ein extrem hohen overhead.
Ich habe den Testfall so konstruiert, dass er auf jeden Fall alle Pfade bis zum ende rechnet und er vorher nicht abbricht.

Bist du sicher dass sich die Threads ueberhaupt lohnen? Wenn die Threads nur jeweils 10 ms lang rechnen dann kostet dich das Erzeugen/Synchronisieren wesentlich mehr als das Rechnen. Aber stells mal auf Tasks um, das sollte wesentlich effizienter sein als die ganzen sections, koennt ich mir denken.

[Stefan_O]

Hab jetzt mit TDragon ausprobiert, kann openmp, aber das erzeugte programm stürzt ab wenn er in den openmp teil kommt (mit den sections).
Ohne OpenMP braucht das programm 2:50, also ziemlich genau so lange wie auch die 32-bit MSVC8 version.

Ich hab nochmal die OpenMP versionen getestet und kann meine ergebnisse von oben nicht mehr reproduzieren, die Werte schwanken jetzt zwischen 1:03 und 4:05 (das war genau die gleiche kommandozeile direkt hintereinander). Ich weiß nicht woran das liegt, beide male war prozessorauslastung von dem programm durchgängig >90%, meistens schwankte es zwischen 97 und 99.

ich hab jetzt mal das mit tasks gemacht. ich habe aber noch nicht genau verstanden wie die funktionieren, die ergebnisse sind folgende:
wenn ich es so mache wie hier in beispiel 1, kriege ich zwei threads aber nach ca. 10 sekunden ist nur noch einer ausgelastet und insgesamt brauch das programm knapp 6 minuten. Es ist auch nicht anders wenn ich die anzahl der threads erhöhe, nach 10 sekunden ist max. cpu auslastung <50%.
wenn ich es so mache wie in 2a (zwei task-constructs) stürzt es wieder ab, bei 2b (ein task-construct) bekomme ich nur ein thread.
Gibt es irgendwo eine schöne erklärung wie tasks funktionieren und wie sie sich von parallel sections unterscheiden? Die Seiten zu OpenMP die ich gefunden habe behandeln Tasks nicht.

Vielen Dank
Stefan

[Blue-Tiger]

Kann es sein dass du furchtbar viele zeitintensive Synchronisierungen hast? Poste bitte nochmal den sequentiellen Code, wenn moeglich so dass man auch sieht wie rechneA und rechneB auch wieder threads starten.

Tutorials zu tasks fallen mir grad keine ein, aber wenn du "OpenMP 3.0" googelst, findest du 'nen Haufen. Das Prinzip ist aber eigentlich nicht schwer zu verstehen: Du startest eine parallele Region, laesst da dann einen einzelnen Thread durchgehen, der jedesmal, wenn er auf einen "task" stoesst, diesen in eine Queue steckt, von wo ihn die anderen Threads rausnehmen und bearbeiten.

Spontan wuerd ich's so machen (ohne wirklich zu verstehen was der Code macht etc.)

datentyp *liste, *var;
#pragma omp parallel
{
	#pragma omp single nowait
	{
		for(i=0;i<N;i++)
		{
			if(RechneWas(var,i))
			{
				#pragma omp task firstprivate(var, i)
				RechneB(var,i);

				RechneA(var,i);
			}
		}

		#pragma omp critical
		if(IstBrauchbar(var))
		{
			liste->next = var;
			var->prev = liste;
			liste = var;

			if(IstPerfekt(var))
			{
				KillAllTherads();
			}
		}
	}
}
Print(liste);

Was ich aber nicht versteh: warum parallelisierst du nicht einfach die for-Schleife?

EDIT: es kann natuerlich auch sein, dass die Parallelisierung einfach ein paar sehr super Optimierungen des Compilers kaputt macht. Was macht denn der sequentielle Code bei -O0 ?

[Stefan_O]

Ich hoffe das ist jetzt nicht zu viel code:

void findfrequences(fcalc *v, globalvars *g)
{
	fcalc *vb;
	fsol *s;
	int stop, lim;
	if(v->fn>=g->totalfreq) return;
//#pragma omp critical (stop)
//	{
		stop = g->stop;
//	}
	if(stop) return;
	for(;v->i<g->fs_n;v->i++)
	{
		for(;v->j<g->fs[v->i].n;v->j++)
		{
			for(;v->q<g->fs[v->i].freqlist_n;v->q++)
			{
				if (checkspace(v,g->fs[v->i].freqlist[v->q],g->fs[v->i].fminim,g->fs[v->i].fmaxim)) continue;
				if (g->opt_2im3 && check2im3(v,g->fs[v->i].freqlist[v->q],g->opt_2im3)) continue;
				if (g->opt_2im5 && check2im5(v,g->fs[v->i].freqlist[v->q],g->opt_2im5)) continue;
				if (g->opt_3im3 && check3im3(v,g->fs[v->i].freqlist[v->q],g->opt_3im3)) continue;
				// freq works
				vb=copyfcalc(v,g);
#pragma omp parallel sections
				{
#pragma omp section
					{
						if(g->opt_2im3) add2im3(v, g->fs[v->i].freqlist[v->q], g->opt_2im3);
						if(g->opt_2im5) add2im5(v, g->fs[v->i].freqlist[v->q], g->opt_2im5);
						if(g->opt_3im3) add3im3(v, g->fs[v->i].freqlist[v->q], g->opt_3im3);
						addfreq(v,g->fs[v->i].freqlist[v->q],g->opt_s,g->fs[v->i].fminim,g->fs[v->i].fmaxim);
						v->q++;
						if(v->fn<g->totalfreq)
						{
							findfrequences(v,g);
							stop=2;
						}
						if(stop!=2) stop=1;
					}
#pragma omp section
					{
						vb->q++;
						findfrequences(vb,g);
					}
				}
				if(stop==2) return;
				if(stop) break;
			}
			if(stop) break;
		}
		if(stop) break;
		v->j=0;
		v->q=0;
	}
	if((v->fn==0) || v->fn<g->opt_m)
	{
		free(v);
		return;
	}
	if(v->fn>=g->totalfreq)
	{
#pragma omp critical (fullsol)
		{
			g->fullsol++;
			if(g->fullsol>=g->opt_e)
			{
#pragma omp critical (stop)
				{
					g->stop = 1;
				}
			}
		}
	}

	s = sec_malloc(sizeof(fsol));
	s->fn = v->fn;
	s->flist = sec_malloc(sizeof(int)*s->fn);
	memcpy(s->flist,v->flist,sizeof(int)*s->fn);
	s->next = NULL;
	free(v);
#pragma omp critical (result)
	{
		if(!g->sol_start)
		{
			s->prev = NULL;
			g->sol_start = g->sol_end = s;
		}
		else
		{
			s->prev = g->sol_end;
			g->sol_end->next = s;
			g->sol_end = s;
		}
	}
	return;
}

Das Problem ist, ich kann die for-Schleife nicht einfach parallelisieren, da die Rechnung des i+1-ten Durchlauf vom Ergebnis des i-ten Durchlaufs abhängig ist. Wenn i-te durchlauf
Das zeitintensive ist hier zeile 23, denn v ist selbst in meinem kurzen benchmark bereits knapp 128KB groß.

Synchronisierung habe ich fast keine, 99% der aufrufe dieser funktion werden in zeile 46 oder 58 enden. Ich habe das critical beim lesen der stop-variable mal auskommentiert, geht auch ohne problemlos. Ich mein, das ist ein int, da wird entweder der alte oder der neue wert stehen, es kann ja nicht zeitgleich ein thread auf eine int-variable zugreifen während ein anderer sie beschreibt, oder? beim array wäre das natürlich anders.

Das was du vorschlägst entspricht ja ungefär dem was bei sun unter 1 steht, nur das du nur ein task machst.

Ich hab den code mal so geändert:

void findfrequences(fcalc *v, globalvars *g)
{
	fcalc *vb;
	fsol *s;
	int stop, lim;
	if(v->fn>=g->totalfreq) return;
//#pragma omp critical (stop)
//	{
		stop = g->stop;
//	}
	if(stop) return;
	for(;v->i<g->fs_n;v->i++)
	{
		for(;v->j<g->fs[v->i].n;v->j++)
		{
			for(;v->q<g->fs[v->i].freqlist_n;v->q++)
			{
				if (checkspace(v,g->fs[v->i].freqlist[v->q],g->fs[v->i].fminim,g->fs[v->i].fmaxim)) continue;
				if (g->opt_2im3 && check2im3(v,g->fs[v->i].freqlist[v->q],g->opt_2im3)) continue;
				if (g->opt_2im5 && check2im5(v,g->fs[v->i].freqlist[v->q],g->opt_2im5)) continue;
				if (g->opt_3im3 && check3im3(v,g->fs[v->i].freqlist[v->q],g->opt_3im3)) continue;
				// freq works
				if(v->fn+1>=g->totalfreq)
				{
					vb=v;
					stop=1;
				}
				else
				{
					vb=copyfcalc(v);
					stop=0;
				}
				if(g->opt_2im3) add2im3(vb, g->fs[vb->i].freqlist[vb->q], g->opt_2im3);
				if(g->opt_2im5) add2im5(vb, g->fs[vb->i].freqlist[vb->q], g->opt_2im5);
				if(g->opt_3im3) add3im3(vb, g->fs[vb->i].freqlist[vb->q], g->opt_3im3);
				addfreq(vb,g->fs[vb->i].freqlist[vb->q],g->opt_s,g->fs[vb->i].fminim,g->fs[vb->i].fmaxim);
				vb->q++;
				if(stop) break;
#pragma omp task
				findfrequences(vb,g);
			}
		}
		v->j=0;
		v->q=0;
	}
	if((v->fn==0) || v->fn<g->opt_m)
	{
		free(v);
		return;
	}
	if(v->fn>=g->totalfreq)
	{
#pragma omp critical (fullsol)
		{
			g->fullsol++;
			if(g->fullsol>=g->opt_e)
			{
#pragma omp critical (stop)
				{
					g->stop = 1;
				}
			}
		}
	}
	s = sec_malloc(sizeof(fsol));
	s->fn = v->fn;
	s->flist = sec_malloc(sizeof(int)*s->fn);
	memcpy(s->flist,v->flist,sizeof(int)*s->fn);
	s->next = NULL;
	free(v);
#pragma omp critical (result)
	{
		if(!g->sol_start)
		{
			s->prev = NULL;
			g->sol_start = g->sol_end = s;
		}
		else
		{
			s->prev = g->sol_end;
			g->sol_end->next = s;
			g->sol_end = s;
		}
	}
	return;
}

Und beim ersten Aufruf der Funktion:

#pragma omp parallel
{
#pragma omp single nowait
	{
		findfrequences(v,&g);
	}
}

Stürzt bloß leider ab. auch wenn ich parallel/single innerhalb der funktion mache um die äußerste schleife passiert genau das gleiche. ich frag mich ob ich da was falsch mache oder openmp mit mingw nicht so toll funktioniert. schließlich stürzt auch die version mit sections, die mit msvc nur langsam ist, sofort ab.
ich werde sonst mal mein linux bemühen den code zu kompilieren, vielleicht geht es da ja.
wenn ich openmp deaktiviere ist mit diesem code die x64-version 2 sekunden und win32 version sogar 40 sek. schneller (liegt vielleicht an der calling convention).

Vielen Dank
Stefan

[Stefan_O]

Ich habs jetzt unter Linux probiert und mein verdacht hat sich bestätigt, mingw und openmp geht nicht. Unter Linux kompiliert und lief sofort.
Ohne OpenMP: 53 sek. (sehr gut reproduzierbar)
Mit OpenMP und Tasks so wie im vorherigen Post umgesetzt: 40-50 sek. (schwankend)
Alles andere ist bedeutend langsamer (sections)
Mir ist aufgefallen das die Gesamtprozessorauslastung ohne OpenMP 50%+x (x = andere Programme) beträgt, mit OpenMP aber schwankt und nicht durchgängig bei 100% ist. Ich weiß aber nicht was da bremst.
Mein Versuch memcpy durch eine selbstgeschriebene sse-asm-version zu ersetzen: geht nicht, das beste was ich geschafft hab war 1 sekunde langsamer als mit standardfunktion.

Eine Idee die ich noch hätte wäre - wenn das geht - nicht immer tasks zu erstellen, sondern ein globalen thread-counter zu machen und nur wenn ein task beendet wurde wird an der nächsten Gabelung ein Task gestartet.

Sonst noch irgendwelche Ideen? ich mein theoretisch müsste sich das Problem doch super parallelisieren lassen, da sollten doch 30 sekunden im Bereich des Machbaren liegen mit 2 threads wenn ein thread 53 sekunden braucht.

Vielen Dank
Stefan

[Blue-Tiger]

Hmm... die erste deiner 2 geposteten Versionen ist "falsch", da du bei jedem Aufruf von findfrequencies einen neuen "omp parallel"-Abschnitt hast. Und jeder "omp parallel"-Abschnitt startet dir X neue Threads.

Bei der 2. Version (der mit den Tasks) seh ich jetzt breim grob drueber schauen keinen offensichtlichen Fehler (abgesehen davon dass du 2 critical-sections ineinander verschachtelst, was eigentlich sinnlos ist. Ich schau mir's morgen nochmal genauer an.

Stefan_O schrieb:

Eine Idee die ich noch hätte wäre - wenn das geht - nicht immer tasks zu erstellen, sondern ein globalen thread-counter zu machen und nur wenn ein task beendet wurde wird an der nächsten Gabelung ein Task gestartet.

Wozu? die Threads werden ja alle beim "omp parallel" gestartet und wartn dann alle auf neue Tasks (bis auf den einen Thread, der in die "single"-Section rein kommt). D. h. OpenMP macht das eh automatisch.

[Stefan_O]

Blue-Tiger schrieb:

Hmm... die erste deiner 2 geposteten Versionen ist "falsch", da du bei jedem Aufruf von findfrequencies einen neuen "omp parallel"-Abschnitt hast. Und jeder "omp parallel"-Abschnitt startet dir X neue Threads.

Mehr Threads starten als festgelegt tut er nicht, aber es ist wie gesagt extrem langsam.

Blue-Tiger schrieb:

Bei der 2. Version (der mit den Tasks) seh ich jetzt breim grob drueber schauen keinen offensichtlichen Fehler (abgesehen davon dass du 2 critical-sections ineinander verschachtelst, was eigentlich sinnlos ist. Ich schau mir's morgen nochmal genauer an.

Wiso? Das sind doch zwei unterschiedliche critical sections, auch wenn die innere keinen Sinn mehr hat wenn sie oben auskommentiert ist.

Blue-Tiger schrieb:

Wozu? die Threads werden ja alle beim "omp parallel" gestartet und wartn dann alle auf neue Tasks (bis auf den einen Thread, der in die "single"-Section rein kommt). D. h. OpenMP macht das eh automatisch.

Natürlich um das programm schneller zu machen
So scheint es ja noch nicht optimal zu funktionieren. Desweiteren fehlt mir noch eine Lösung für windows. mingw will schon bei win32 OpenMP nicht (anscheinend funktionieren nur ältere versionen, da gibts aber noch kein OpenMP 3.0), und da x64 deutlich schneller brauch ich mingw-w64 mit openmp, dazu finde ich gar nichts. Das heißt ich brauch wohl eine Lösung die ohne tasks auskommt.

Vielen Dank
Stefan

[Blue-Tiger]

Stefan_O schrieb:

Blue-Tiger schrieb:

Hmm... die erste deiner 2 geposteten Versionen ist "falsch", da du bei jedem Aufruf von findfrequencies einen neuen "omp parallel"-Abschnitt hast. Und jeder "omp parallel"-Abschnitt startet dir X neue Threads.

Mehr Threads starten als festgelegt tut er nicht, aber es ist wie gesagt extrem langsam.

Na ja, es ist auch sehr,sehr langsam, da du durch die Verschachtelten "parallel"-sections den gleichen Code viel oefters ausfuehrst als du eigentlich willst: http://software.intel.com/en-us/articles/32-openmp-traps-for-c-developers/#IDANOQDC (allgemein sehr empfehlenswert, der Artikel).

Blue-Tiger schrieb:

Wozu? die Threads werden ja alle beim "omp parallel" gestartet und wartn dann alle auf neue Tasks (bis auf den einen Thread, der in die "single"-Section rein kommt). D. h. OpenMP macht das eh automatisch.

Natürlich um das programm schneller zu machen
So scheint es ja noch nicht optimal zu funktionieren. Desweiteren fehlt mir noch eine Lösung für windows. mingw will schon bei win32 OpenMP nicht (anscheinend funktionieren nur ältere versionen, da gibts aber noch kein OpenMP 3.0), und da x64 deutlich schneller brauch ich mingw-w64 mit openmp, dazu finde ich gar nichts. Das heißt ich brauch wohl eine Lösung die ohne tasks auskommt.

Hmm... mit MinGW/Windows kann ich dir leider nicht helfen. Ich geh davon aus dass du beim TDragon-Release alles richtig gemacht hast (du musst sowohl -gomp als auch -lpthreads als Optionen mitgben). Find es allerdings sehr komisch dass das nicht geht (zumindest mit TDragon-gcc 4.2 (oder war es 4.3?) funktionierte OpenMP noch einwandfrei (Leider gibts erst ab 4.4 support fuer omp tasks). Funktionieren denn andere Minimal-OpenMP-Beispiele mit dem TDragon-gcc?

Auf sections wuerd ich nicht zurueckgreifen, die sind einfach nicht fuer das gemacht was du vorhast. Notfalls muesstest du wohl von Hand Threads programmieren; ist auch nicht sooooo schwer (und PThreads gibts sowohl fuer Linux als auch fuer Windows, und ich vermute auch fuer Macs).

Eine (von mir nicht getestete) Moeglichkeit waer noch, von Linux aus fuer Windows crosscompilen, geht bei neueren Distris relativ einfach (die haben oft irgendwelche mingw-packages), aber k.A. wie's da mit GOMP (GNU OpenMP)-support ausschaut. Noch extremer: du koenntest dir den MinGW selbst bauen (aber eigentlich sollte das TDragon-Release schon funktionieren).

[Stefan_O]

Na ja, es ist auch sehr,sehr langsam, da du durch die Verschachtelten "parallel"-sections den gleichen Code viel oefters ausfuehrst als du eigentlich willst: http://software.intel.com/en-us/articles/32-openmp-traps-for-c-developers/#IDANOQDC (allgemein sehr empfehlenswert, der Artikel).

Ist es den möglich innerhalb einer section eine weitere zu haben? für den Fall könnte man das omp parallel ja rausziehen aus der funktion und innerhalb die sections haben.

Hmm... mit MinGW/Windows kann ich dir leider nicht helfen. Ich geh davon aus dass du beim TDragon-Release alles richtig gemacht hast (du musst sowohl -gomp als auch -lpthreads als Optionen mitgben). Find es allerdings sehr komisch dass das nicht geht (zumindest mit TDragon-gcc 4.2 (oder war es 4.3?) funktionierte OpenMP noch einwandfrei (Leider gibts erst ab 4.4 support fuer omp tasks). Funktionieren denn andere Minimal-OpenMP-Beispiele mit dem TDragon-gcc?

Nein, mit dem TDragon-gcc funktioniert nichts mit OpenMP. Ich habe gelesen das OpenMP nur bei älteren builds funktioniert hat. Und selbst wenn es gehen würde, ist es nicht 64-bit. Das problem scheint zu sein das libgomp zur Zeit nicht mit win32 threads funktioniert und libgomp->pthreads->win32 threads instabil ist. Das heißt cross-compiling hilft auch nicht.
Der Intel-Compiler kann OpenMP 3.0, ist aber für Windows nicht kostenlos, nur 30-tage demo. Und man muss ihn überlisten damit die erzeugten programme auch mit AMD prozessoren schnell sind.

Auf sections wuerd ich nicht zurueckgreifen, die sind einfach nicht fuer das gemacht was du vorhast. Notfalls muesstest du wohl von Hand Threads programmieren; ist auch nicht sooooo schwer (und PThreads gibts sowohl fuer Linux als auch fuer Windows, und ich vermute auch fuer Macs).

Muss man da was komplett anderes machen oder kann man das einfach mit #ifdef und 3 zeilen code für jedes OS lösen? Geht das mit den critical sections so einfach oder muss ich da was kompliziertes bauen?

Auch wenns off-topic ist, aber ich bin zufällig als ich nach einem schnellen memcpy gesucht habe, darauf gestoßen, dass

if (a<0 || a>=b) continue;

für schnellere ausführung durch

if ((unsigned int)a >= (unsigned int)b) continue;

ersetzt werden sollte. da das ein paar mal vorkommt in den Funktionen die innerhalb der schleife aufgerufen werden, dacht ich mir, vielleicht bringt es ja einen messbaren vorteil ansonsten schadet es nicht:
Von 59 sekunden runter auf 39! ich dachte ich bin blöd, habe aber die zeilen wieder zurückgeändert, nochmal kompiliert, aber es liegt wirklich daran. wenn man mal nachzählt taucht das auch in jeder check-funktionen je nachdem wie viel er schon gerechnet hat zwischen 4 und 45 mal auf in meinem test.

Vielen Dank
Stefan