Parallelisierung mit OpenMP / Dynamisch threads erzeugen

[Stefan_O]

Hallo,

ich habe noch nie mit Threads programmiert und meine Kentnisse insgesamt würde vielleicht als Fortgeschritten einschätzen. Zur Zeit arbeite an einem Programm, welches sehr zeitaufwändige Berechnungen durchführt, welche nach folgendem Muster abgearbeitet werden sollen, von dem ich denke dafür ist Multithreading optimal:

Thread 0 beginnt und kommt an einen Punkt wo er in "zwei Richtungen" weitermachen kann, dazu ruft er Thread 1 auf, der mit B weiterrechnet, während Thread 0 mit A weiterrechnet. Dazu müssen Variablen (ein struct und laufvariablen i,j etc.) kopiert werden. Diesen beiden Threads können wieder an so einen Punkt kommen und so weiter, das wiederholt sich sehr oft, aber ist definitiv endlich.
Wenn an ein Thread am Ende ist soll er sein Ergebnis falls brauchbar zu einer verketteten Liste hinzufügen, unter umständen sogar alle anderen Threads abbrechen und fertig, vereinfacht ungefähr so:

datentyp *liste, *var;
for(i=0;i<N;i++)
{
	if(RechneWas(var,i))
	{
		CreateNewThread(); // soll var und i kopieren
		if(IsNewThread())
		{
			RechneB(var,i);
			continue;
		}
		RechneA(var,i);
	}
}
#critical
if(IstBrauchbar(var))
{
	liste->next = var;
	var->prev = liste;
	liste = var;
}
if(IstPerfekt(var))
{
	KillAllTherads();
}
#end critical
WaitForAllThreads();
Print(liste);

Das bedeutet, dass die kopierte Variable var entweder gelöscht wird oder dem Hauptthread zufällt.

Kann man sowas einfach mit OpenMP umsetzen? Vorraussetzung dafür ist, dass man theoretische eine beliebige endlich große Anzahl von Threads starten darf (ich vermute in meinem programm so 100 bis 1000 zeitgleich) und das das Programm dadurch nicht ausgebremst wird. Auf jeden Fall sollte, falls kein Thread mehr erzeugt werden kann, die Variablen kopiert werden und der Thread dann gestartet werden wenn ein anderer beendet wurde und wieder Platz ist.

Kann mir jemand erklären wie ich sowas mit OpenMP umsetze?

Vielen Dank
Stefan

[C++ Forumbot]

Dieser Thread wurde von Moderator/in rüdiger aus dem Forum ANSI C in das Forum Rund um die Programmierung verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[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