Multithreading oder wie denke ich in parallelen Prozessen/Datenstrukturen...

Winn

Servus Folks,

derzeit arbeit ich mich in die Welt des Multithreading über die "Intel Threading Building Blocks" Bibliothek (TBB, http://threadingbuildingblocks.org/) ein, welche extrem einfach in der Umsetzung/Erlernung ist.

Allerdings muss ich feststellen, das meine Datenstrukturen bzw. meine Denkweise wohl eher für Single Threads entwickelt ist, so dass ich mich mal umhören wollte, welchen grobe Blaupause bzw. Denkweise für eine effiziente Parallelisierung notwendig ist ?

Dabei ist die Vorstellung über diverse Abhängigkeiten in einem Algorithmus für mich kein Problem, aber ich stelle fest, daß unabhängig von der Anzahl der Threads irgendwann eine Sättigung der Performanc eintritt - hier vermute ich einen steigenden Organisations Aufwand, wegen meiner benutzten Datenstruktur...

Welche Erfahrungen, Tipps und im Speziellen zur TBB hättet ihr ?

Winn

hustbaer

Ich kann dir erstmal nur einen grundsätzlichen Tip geben, und zwar: die Blockgrösse ("grainsize") ist wichtig. Zu kleine Blöcke führen dazu dass der Verwaltungs-Overhead Überhand nimmt, zu grosse Blöcke führen dazu dass nicht alle "hardware-threads" ausgenutzt werden können.

Vielleicht postest du etwas Code, dann können sich vermutlich mehr Leute etwas darunter vorstellen was du da machst.

Winn

hustbaer schrieb:

Vielleicht postest du etwas Code, dann können sich vermutlich mehr Leute etwas darunter vorstellen was du da machst.

Der untigen Quellcode berechnet eine elektromagnetische Ebene-Welle (1D) nach dem FDTD-Algorithmus...

for(unsigned int i=0; i<uiQtyOfTimesteps; ++i)
{
parallel_for(blocked_range<size_t>(0,Ex_D_Hy[0].sQtyOfTargets,10000), applyParallelDerivation(dField,&(Ex_D_Hy[0])));
dField[2*(uiNumberOfCells/2-1)] += dExcitation[i];
dField[Hy_D_Ex[0].sTarget[0]]+=Hy_D_Ex[0].dCoeff[0]*dField[Hy_D_Ex[0].sTarget[0]+Hy_D_Ex[0].iDelta[0]];
dField[Hy_D_Ex[2].sTarget[0]]+=Hy_D_Ex[2].dCoeff[0]*dField[Hy_D_Ex[2].sTarget[0]+Hy_D_Ex[2].iDelta[0]];
parallel_for(blocked_range<size_t>(0,Hy_D_Ex[1].sQtyOfTargets,10000), applyParallelDerivation(dField,&(Hy_D_Ex[1])));
}

mit dem Template "applyParallelDerivation"

class applyParallelDerivation
{
	double *myfield;
	my_operator *const op;

	public:
		applyParallelDerivation(double *field, my_operator *mop):myfield(field),op(mop)
			{}
		void operator() (const blocked_range<size_t> &r) const
		{
			double *field = myfield;
			const my_operator *mop = op;
			switch (mop->sQtyOfDeltas)
			{
				case 1:
				{
					for(size_t i=r.begin(); i!=r.end(); ++i)
					{
						field[mop->sTarget[i]]+=mop->dCoeff[0]*field[mop->sTarget[i]+mop->iDelta[0]];
					}
					break;
				}
				case 2:
				{
					for(size_t i=r.begin(); i!=r.end(); ++i)
					{
						field[mop->sTarget[i]]+=mop->dCoeff[0]*field[mop->sTarget[i]+mop->iDelta[0]];
						field[mop->sTarget[i]]+=mop->dCoeff[1]*field[mop->sTarget[i]+mop->iDelta[1]];
					}
					break;
				}
			};
		}
};

Ich kann dir erstmal nur einen grundsätzlichen Tip geben, und zwar: die Blockgrösse ("grainsize") ist wichtig. Zu kleine Blöcke führen dazu dass der Verwaltungs-Overhead Überhand nimmt, zu grosse Blöcke führen dazu dass nicht alle "hardware-threads" ausgenutzt werden können.

Die Grainsize und die Anzahl an Threads habe ich in zwei Schleifen-Durchläufen parametrisiert (Grainsize 500 <-> 100000, Threads 1 <-> 8), um zu schauen welche Settings optimal sind... dabei viel auf das ab einer Grainsize von 10.000 unabhängig von der Threadanzahl die Sättigung erreicht ist (gilt nur für den obigen Code-Schnipsel). Dann las ich etwas von "Amdahls Law", fand es sehr passend, aber frage mich noch immer, wie man durch entsprechend geschickte Programmierung seine Parallelisierung bis zur theoretischen Grenze ausbauen kann...

hustbaer

OK, ich habe genau garkeine Ahnung was du da machst

Aber...

Bist du sicher dass sich die parallel laufenden "Blöcke" nicht gegenseitig in die Quere kommen? Für parallel_for müssen alle Schleifendurchläufe unabhängig voneinander sein. D.h. z.B. wenn ein Element von "field" bei irgendeinem Schleifendurchlauf geschrieben wird darf es nie gelesen werden (ausser im gleichen Schleifendurchlauf wo es geschrieben wird, oder natürlich in einem weiteren, unabhängigen parallel_for Durchlauf).

Wenn das soweit OK ist, wieso schreibst du die Werte in dasselbe Array zurück wo du sie auch ausliest? Und nochdazu nicht einfach mit ansteigendem Index ("offset + i" oder sowas), sondern mit etwas was kompliziert genug ist in einem Array gespeichert zu werden ("mop->sTarget[i]")?

Eine Sache die nämlich auch mächtig bremsen kann ist wenn die CPUs/Cores sich gegenseitig um Cache-Lines "streiten".
Also z.B. wenn CPU 1 "field[100]" schreibt und CPU 2 danach "field[101]" (oder auch 99, 100, 102...) liest oder schreibt.

Falls du dich damit noch nicht auskennst und es wissen möchtest kannst du mal ein paar Artikel zum MESI Protokoll suchen. Es gibt zwar noch andere Systeme als MESI, aber MESI ist IMO relativ einfach zu verstehen. Und ein auf ein MESI System optimiertes Programm wird vermutlich auch auf allen anderen Systemen schneller laufen als ein garnicht "Cache-optimiertes" Programm.

BTW: guck da mal rein falls du es noch nicht kennst:

http://www.ddj.com/hpc-high-performance-computing/205900309?pgno=1

Winn

hustbaer schrieb:

OK, ich habe genau garkeine Ahnung was du da machst

Aber...

Bist du sicher dass sich die parallel laufenden "Blöcke" nicht gegenseitig in die Quere kommen?

Sagen wir, ich bin mir unsicher - was ich hätte zum Quellcode sagen sollen, ist, dass in dem Array Field die Feldkomponente Ex und Hy über einen geraden bzw. ungeraden Index steckt, d.h. eigentlich steht dort

Ex[gerader Index]+=Koeffizient*Hy[ungerader Index]

in welcher Form die CPU die Daten aus dem Speicher zieht, keine Ahnung, denn wenn sich die CPU mehrere Double gleichzeitig ziehen würde, geht das Gekloppe los... den Link vom Sutter lese ich mir gleich mal genauer durch.

hustbaer schrieb:

Eine Sache die nämlich auch mächtig bremsen kann ist wenn die CPUs/Cores sich gegenseitig um Cache-Lines "streiten".
Also z.B. wenn CPU 1 "field[100]" schreibt und CPU 2 danach "field[101]" (oder auch 99, 100, 102...) liest oder schreibt.

Kann diese Problematik einen Grund darin finden, daß mein parallelisierter Code mit steigender Anzahl an Threads eher langsamer wird ?

hustbaer

Sagen wir, ich bin mir unsicher - was ich hätte zum Quellcode sagen sollen, ist, dass in dem Array Field die Feldkomponente Ex und Hy über einen geraden bzw. ungeraden Index steckt, d.h. eigentlich steht dort

Ex[gerader Index]+=Koeffizient*Hy[ungerader Index] in welcher Form die CPU die Daten aus dem Speicher zieht, keine Ahnung, denn wenn sich die CPU mehrere Double gleichzeitig ziehen würde, geht das Gekloppe los...

Also wenn das so ist ist das Programm auf jeden Fall "korrekt" in dem Sinn dass es richtig funktionieren muss. Das gleichzeitige Lesen/Schreiben von benachbarten Werten kann zwar bremsen, allerdings sorgt das Cache-Coherency Protokoll dafür dass trotzdem alles "funktioniert" (also die richtigen Werte im Speicher landen).

(OK, eigentlich ist es etwas komplizierter. z.B. dürfte ein C++ Compiler Code generieren der auf einem RISC mit 4 Byte Worten das Schreiben von Bytes über Read-Modify-Write implementiert, also als 3 getrennte Befehle. Das wäre dann allerdings ein Compiler mit dem Multi-Threading nur mit argen Bauchschmerzen möglich ist -- damit würden schätze ich einige Programme nicht klarkommen)

Kann diese Problematik einen Grund darin finden, daß mein parallelisierter Code mit steigender Anzahl an Threads eher langsamer wird ?

Ja, das kann leicht sein.
Ideal wäre IMO folgendes:

//field[mop->sTarget[i]]+=mop->dCoeff[0]*field[mop->sTarget[i]+mop->iDelta[0]];
ex[i] += mop->dCoeff[0]*hy[...]; // mit einfach nur "i" als Index kommen sich die einzelnen CPUs beim Schreiben nicht in die Quere
                                 // da die "Blöcke" ja ausreichend gross sein werden, und daher nur jeweils eine Cache-Line
                                 // pro Blockgrenze von 2 CPUs verwendet wird

Wenn du dann "ex" danach "umsortieren" musst kann es natürlich sein dass dies wieder viel Zeit frisst, und es im Endeffekt gleich schnell/langsam ist wie du es jetzt machst. Aber du kannst es ja mal ausprobieren.

Winn schrieb:

Kann diese Problematik einen Grund darin finden, daß mein parallelisierter Code mit steigender Anzahl an Threads eher langsamer wird ?

Threading macht ein Programm nicht schneller. Threads erzeugen einen Overhead an Verwaltung, kosten also zusätzliche Performance. Daher stimmt es schon, daß mit steigender Anzahl der Threads mehr Performance für die Threadverwaltung (context-switches etc) verbraucht wird, also das Gesamtsystem langsamer wird.

Sollte dein Code z.B. bereits im SIngle-Thread den Prozessor zu 100% auslasten, dann können mehr Threads das System insgesamt nur langsamer machen, nicht schneller.

Der Sinn von Threads liegt auch nicht wirklich in der Steigerung von Performance, sondern in der (optimalen) Verteilung der vorhandenen Performance auf mehrere Programme. Innerhalb eines Programms machen Threads imho nur dann Sinn, wenn es darum geht bestimmte Programmabläufe zu "entkoppeln". Als Beispiel um eine Datenbankabfrage von der GUI abzukoppeln, damit die GUI auch dann noch reaktiv bleibt wenn die DB-Abfrage läuft.

Im Prinzip gilt der Satz: So wenig (Threads) wie möglich, soviele wie nötig.

Wohlgemerkt, wir reden hier von Multithreading, nicht von Multiprozessing.

hustbaer

Ich gehe doch stark davon aus dass der OP ein multi-CPU oder multi-Core System verwendet. Und da machen mehrere Threads mächtig Sinn

Also, OP, wie viele "hardware Threads" (CPUs x Cores x Hyperthreading) hat dein System?

Winn

hustbaer schrieb:

Also, OP, wie viele "hardware Threads" (CPUs x Cores x Hyperthreading) hat dein System?

Ich hab einen Core 2 Duo 2.4 GHz - führe ich mein Prog. im Single Mode aus, sehe ich 100% Auslastung, führe ich das Programm mit 2 Threads, sehe ich wiederum 100% Auslastung je Kern, aber keine verkürzte Laufzeit, eher das Gegenteil...

hustbaer

Was meinst du mit "single mode"? Mit nur einem Thread? Kann nicht gut sein...

Ich habe selbst einen Core 2 Quad und in der Firma einen Core 2 Duo, und wenn ich ein Programm mit nur einem Thread laufen lasse geht auf beiden auch nur ein Core auf 100% (bzw. die Gesamtauslastung auf 25% bzw. 50%).

Winn

hustbaer schrieb:

Was meinst du mit "single mode"? Mit nur einem Thread? Kann nicht gut sein...

Genau das, Single Mode = Single Thread ... habe ich mehr als einen Thread steigt die Laufzeit... habe nun auch schon verschiedene Datenstrukturen ausprobiert, aber die Grundtendenz bleibt erhalten

Meine Vermutung bzw. Abarbeitung sieht wie folgt aus

for(unsigned int iTime=0; iTime < uiQtyOfTimestepe; ++iTime)
{
parallel_for("Berechne die Ex Komponente");
parallel_for("Berechne die Hy Komponente");
}

die Erstellung von 2 Threads und anschließende Terminierung nach Beendigung von parallel_for kostet zuviel und muß für die zweite parallel_for erneut erstellt werden, wieder terminiert werden, usw.

hustbaer

Soweit ich weiss werden beim Aufruf von parallel_for keine Threads erstellt, sondern beim Anlegen des task_scheduler_init Objekts. Alles andere wäre auch ziemlich ineffizient.

Die einzelnen Konstrukte ala parallel_for verwenden dann den intern angelegten Scheduler, der die Worker-Threads verwaltet, und die einzelnen "Tasks" an die Threads verteilt.

Und was ich meinte mit "kann nicht gut sein" ist ... es kann nicht sein dass deine CPU _gesamt_ auch 100% geht wenn du nur einen Thread verwendest für die Berechnung. Der 2. Core langweilt sich dann ja, und der Task Manager müsste dir 50% (oder geringfügig mehr) anzeigen.

Winn

hustbaer schrieb:

... es kann nicht sein dass deine CPU _gesamt_ auch 100% geht wenn du nur einen Thread verwendest für die Berechnung. Der 2. Core langweilt sich dann ja, und der Task Manager müsste dir 50% (oder geringfügig mehr) anzeigen.

Okay, gg... es ist schlampig formuliert, 100% Auslastung auf einem Kern, macht 50 % Auslastung auf dem gesamten System...

Was ich beobachte ist das folgende:
1 Thread arbeitet zu 100% auf einem Kern und ist schneller als
2 Threads verteilt auf zwei Kernen bei einer 100% System-Auslastung, wobei diese Konf. schneller ist als
3 Threads verteilt... usw.