Berechnung mit OpenMP zu langsam



  • Guten Tag,

    ich versuche mein Berechnungsprogramm zu beschleunigen.
    Es wurde mit unterschiedlicher Anzahl an Threads ausgeführt.
    1 Thread: ~13s
    2 Threads: ~ 7s
    8 Threads: ~ 4s
    16 Threads: ~ 2s
    32 Threads: ~ 1,5s
    Das Verhältnis 1Thread zu 32 Threads ist nur ~8.5 und das möchte ich verbessern.
    Vielleicht lässt sich auch die Berechnungszeit von 1 Thread verkürzen.
    Ich habe hier einen Pseudocode des Berechnungsprogramm geschrieben, der die Struktur abbilden soll. Ich vermute ich mache dort einige grundlegende Sachen falsch im Bezug auf Geschwindigkeit, da ich die Programmierung sehr selten benötige sind meine Kenntnisse leider auch nicht die besten.

    Ich hoffe ihr könnt mir helfen, mein Programm zu beschleunigen. Falls irgendwelche Informationen fehlen, liefere ich diese natürlich gerne nach.

    //Global Variablen
    float matrix1[175];
    float matrix2[175];
    float matrix3[175];
    float matrix4[175];
    
    void RunApproximation(float lut3Linear[], float iterations1, float iterations2, float iterations3)
    {
    	//RunApproximation führt eine approximierte Berechnung aus und liefert gute Startwerte für die RunFull-Funktion. Die Startwerte werden in den Matrizen 1-4 gespeichert. 
    }
    
    void RunFull(float lut3Linear[], float iterations1, float iterations2, float iterations3)
    {
    	//Anzahl der Threads für openMP wird festgelegt
    	omp_set_num_threads(32);
    
    	//Die Iteration startet, welche nahezu die gesamte Berechnungszeit beansprucht
    	for (int iter=1; iter<500; iter++) {
    
    		//Ein Gewicht wird berechnet, für die spätere Aktuallisierung der gloablen Matrizen 1-4
    		float gewicht = 1.0f / (float)Iter;
    
    		//Es werden ein paar einfache schnelle Berechnungen ausgeführt.
    		float matrix1Prozent = 0.0f;
    		for (int I=0; I<175; I++) {
    				matrix1Prozent = matrix1Prozent+2.0f*matrix1[I];
    
    		}
    		matrix1Prozent = matrix1Prozent*0.145f;
    		...
    
    		//Hier startet meine Parallelisierung
    		#pragma omp parallel for
    		for (int a=0; a<175; a++) {
    			//Es werden bei jedem Schleifendurchlauf bestimmte Berechnungswerte auf 0 gesetzt
    			float berechnung1 = 0.0f;
    			float berechnung2 = 0.0f;
    			float berechnung3 = 0.0f;
    			...
    			for(int b=0; b<175; b++) {
    				for(int c=0; c<175; c++) {
    					//Es werden ein paar Zwischenergebnisse berechnet die häufiger benötigt werden
    					float zwischenErgebnis1 = a*85683+b*507+c*3;
    					float zwischenErgebnis2 = matrix1[b] * matrix2[c];
    					float zwischenErgebnis3 = matrix3[b] * matrix4[c];
    					...
    
    					//Mehrer Berechnungen finden statt und werden jeweils aufaddiert
    					berechnung1 = berechnung1 + ((3.0f*iterations1) * lut3Linear[zwischenErgebnis1] - iterations2) * zwischenErgebnis2;
    					berechnung2 = berechnung2 + ((2.0f*iterations1) * lut3Linear[zwischenErgebnis1+1] - iterations2) * zwischenErgebnis3;
    					berechnung3 = berechnung3 + ((3.0f*iterations2) * lut3Linear[zwischenErgebnis1] - iterations3) * zwischenErgebnis2;
    					...
    				}
    			}
    			//Wieder einige Berechnungen
    			berechnung1 = berechnung1 / berechnung2;
    
    			//Hier findet ein Vergleich statt und anschließend werden die gloalen Matrizen 1-4 aktuallisiert
    			if (berechnung1 > (-1.0f)) {
    				matrix1[a]=((1.0f-gewicht)*matrix1[a]) + gewicht;
    			} else {
    				matrix1[a]=((1.0f-gewicht)*matrix1[a]);
    			}
    			...
    		}
    		//Hier endet die Parallelisierung
    		#pragma omp barrier
    	}
    	//Hier werden dann noch die berechneten Matrizen ausgegeben
    	....
    }
    
    int main(int argc, char *argv[])
    {
    	//Daten werden aus Datei einlesen
    	float *lut3Linear = (float*)malloc(sizeof(float)*175*175*175*9);
    	FILE * lut3LinearFile;
       	lut3LinearFile = fopen("LUT3linearFloat.dat", "rb");
    	for(int a=0; a<175; a++) {
    		for(int b=0; b<175; b++) {
    			for(int c=0; c<175; c++) {
    				for(int d=0; d<9; d++) {
    					fread(&lut3Linear[a*175*175*9+b*175*9+c*9+d], sizeof(float), 1, lut3LinearFile);
    				}
    			}
    		}
    	}
    	fclose (lut3LinearFile);
    	...
    
    	//Der Benutzer soll solange Berechnungen durchführen können, bis die Anwendung gekillt wird
    	while(1)
    	{
    		//Daten werden per Console vom Benutzer abgefragt
    		float eingabe1, eingabe2;
    
    		cin >> eingabe1;
    		cin >> eingabe2;
    		...
    
    		//Aus der Eingaben vom Benutzer werden neue Werte für die Iteration berechnet
    		float iterations1, iteration2, iteration3;
    		...
    
    		//Iteration wird aufgerufen
    		RunApproximation(lut3Linear, iterations1, iteration2, iteration3);
    		RunFull(lut3Linear, iterations1, iteration2, iteration3);
    	}
    
    }
    


  • Wie viele echte Kerne hat diene CPU?



  • Hab das bei Amazon getestet.

    http://aws.amazon.com/ec2/instance-types/

    Compute Optimized c3.8xlarge

    High Frequency Intel Xeon E5-2680 v2 (Ivy Bridge) Processors

    http://ark.intel.com/products/64583/Intel-Xeon-Processor-E5-2680-(20M-Cache-2_70-GHz-8_00-GTs-Intel-QPI)

    Der hat 8 Kerne



  • Warum gibt es keine Messung zu 4 Threads?
    Ist dieses Ergebnis Reproduzierbar? Vielleicht ist die elastic cloud ja etwas zu elastisch.
    Abgesehen von der Lücke mit 4 Threads halbiert sich die Laufzeit mit Verdopplung der Kerne. Mehr kann man nicht erwarten.



  • manni66 schrieb:

    Warum gibt es keine Messung zu 4 Threads?
    Ist dieses Ergebnis Reproduzierbar? Vielleicht ist die elastic cloud ja etwas zu elastisch.
    Abgesehen von der Lücke mit 4 Threads halbiert sich die Laufzeit mit Verdopplung der Kerne. Mehr kann man nicht erwarten.

    Danke für deine Antworten.
    Habe die Berechnungen mehrmals ausgeführt und bis auf ein paar Zentel auch immer die gleichen Werte erhalten. Es ist also Reproduzierbar.

    Ja von 1 -> 2 und von 8 -> 16 hab ich eine Verdopplung aber insgesamt werde ich ja nur ~8,5x schneller bei 32x mehr Kernen, damit bin ich nicht wirklich zufrieden :(.

    Die 4 Threads wären interessant, hab ich aber vergessen zu berechnen.

    In meinem Code ist kein "Geschwindigkeitsfehler" enthalten?
    So wie ich das verstanden habe, teilen sich z.b. alle Threads das Array lut3Linear[] auf das häufig während der Iteration zugegriffen wird. Kommt es da evtl. zu Konflikten und wäre es nicht besser wenn jeder Thread sein eigenen Array hat. Wie gesagt kenne mich mit der Programmierung nicht so gut aus und ich kann eigentlich nicht glauben das ich da alles richtig gemacht habe 🙂



  • Simon S. schrieb:

    In meinem Code ist kein "Geschwindigkeitsfehler" enthalten?

    Fehler ist relativ. Der Grund ist vermutlich der 183 MB grosse Lookup Table. Der passt halt nicht in den Cache. Dadurch ist dein Code stark von der Speichergeschwindigkeit abhängig. Und wenn sich 32 Cores den selben Speicher teilen müssen wird der deswegen ja nicht schneller.

    Wenn du den LUT auf <= 20 MB runterbringen kannst, sollte alles deutlich schneller werden.

    Simon S. schrieb:

    So wie ich das verstanden habe, teilen sich z.b. alle Threads das Array lut3Linear[] auf das häufig während der Iteration zugegriffen wird.

    Ja, die teilen sich den selben Lookup Table, und das ist auch gut so. Der ist eh schon viel zu gross, würde alles noch viel schlimmer machen wenn jeder Thread nen eigenen hätte.
    Wenn da reingeschrieben würde sähe die Sache anders aus, aber die Threads lesen da ja alle nur -- daher gibt's auch keine Performance-Probleme wenn mehrere Threads zugreifen.

    Davon abgesehen...
    Für mich sieht das so aus als ob die Berechnung nichtmal deterministisch ist:

    #pragma omp parallel for
            for (int a=0; a<175; a++) {
                ...
                for(int b=0; b<175; b++) {
                    for(int c=0; c<175; c++) {
                        float zwischenErgebnis1 = a*85683+b*507+c*3;
                        float zwischenErgebnis2 = matrix1[b] * matrix2[c]; // b läuft von 0 bis 175, d.h. hier wird das ganze array matrix1 gelesen
                        ...
                    }
                }
                ...
                if (berechnung1 > (-1.0f)) {
                    matrix1[a]=((1.0f-gewicht)*matrix1[a]) + gewicht;      // und hier wird was in matrix1 reingeschrieben
                } else {
                    matrix1[a]=((1.0f-gewicht)*matrix1[a]);
                }
                ...
            }
            #pragma omp barrier
    

    Ich wüsste nicht wie das funktionieren soll.

    Soviel zum Thema OpemMP ist einfach und sicher 🤡



  • hustbaer schrieb:

    Simon S. schrieb:

    In meinem Code ist kein "Geschwindigkeitsfehler" enthalten?

    Fehler ist relativ. Der Grund ist vermutlich der 183 MB grosse Lookup Table. Der passt halt nicht in den Cache. Dadurch ist dein Code stark von der Speichergeschwindigkeit abhängig. Und wenn sich 32 Cores den selben Speicher teilen müssen wird der deswegen ja nicht schneller.

    Wenn du den LUT auf <= 20 MB runterbringen kannst, sollte alles deutlich schneller werden.

    Simon S. schrieb:

    So wie ich das verstanden habe, teilen sich z.b. alle Threads das Array lut3Linear[] auf das häufig während der Iteration zugegriffen wird.

    Ja, die teilen sich den selben Lookup Table, und das ist auch gut so. Der ist eh schon viel zu gross, würde alles noch viel schlimmer machen wenn jeder Thread nen eigenen hätte.
    Wenn da reingeschrieben würde sähe die Sache anders aus, aber die Threads lesen da ja alle nur -- daher gibt's auch keine Performance-Probleme wenn mehrere Threads zugreifen.

    Davon abgesehen...
    Für mich sieht das so aus als ob die Berechnung nichtmal deterministisch ist:

    #pragma omp parallel for
            for (int a=0; a<175; a++) {
                ...
                for(int b=0; b<175; b++) {
                    for(int c=0; c<175; c++) {
                        float zwischenErgebnis1 = a*85683+b*507+c*3;
                        float zwischenErgebnis2 = matrix1[b] * matrix2[c]; // b läuft von 0 bis 175, d.h. hier wird das ganze array matrix1 gelesen
                        ...
                    }
                }
                ...
                if (berechnung1 > (-1.0f)) {
                    matrix1[a]=((1.0f-gewicht)*matrix1[a]) + gewicht;      // und hier wird was in matrix1 reingeschrieben
                } else {
                    matrix1[a]=((1.0f-gewicht)*matrix1[a]);
                }
                ...
            }
            #pragma omp barrier
    

    Ich wüsste nicht wie das funktionieren soll.

    Soviel zum Thema OpemMP ist einfach und sicher 🤡

    Danke für deine Antwort.
    Ich könnte den LUT auf 170MB reduzieren. Würde es dann was bringen, wenn ich den LUT in 9 Teile zerlege -> ich bin mit jedem Teil unter 20MB und dann nacheinander 9x die 3er for-schleife ausführe. In jeder 3er for-schleife wird dann nur einer der 9 LUTs verwenden. Somit müsste ich pro Iteration nur 9x einen anderen LUT in den cache laden?

    Es wird doch die a-schleife auf mehrer Threads aufgeteilt und jeder Teil durchläuft die vollen 175 Durchläufe von b&c am Ende wird dann auch nur das Matrixelement des entsprechenden a's aktuallisiert und das wurde ja voll berechnet. Dann wird gewartet bis alle a's voll berechnet sind und der nächste Iterationsschritt beginnt.



  • Simon S. schrieb:

    Es wird doch die a-schleife auf mehrer Threads aufgeteilt und jeder Teil durchläuft die vollen 175 Durchläufe von b&c am Ende wird dann auch nur das Matrixelement des entsprechenden a's aktuallisiert und das wurde ja voll berechnet. Dann wird gewartet bis alle a's voll berechnet sind und der nächste Iterationsschritt beginnt.

    Das Problem, welches hustbaer anspricht, besteht darin, dass die Ausführungsreihenfolge nicht garantiert ist. In dem von ihm zitierten Codestück schreibst du in Zeile 13/15 in matrix1. Außerdem wird in Zeile 7 matrix1 gelesen. Es ist aber zu diesem Zeitpunkt nicht klar, ob das Element welches gelesen wird von einem anderen Thread schon berechnet und aktualisiert wurde.
    Ohne eine zusätzliche Synchronisation (omp barrier) zwischen diesen beiden Codeteilen ist deine Berechnung also mit ziemlicher Sicherheit nicht korrekt.



  • ananas schrieb:

    Simon S. schrieb:

    Es wird doch die a-schleife auf mehrer Threads aufgeteilt und jeder Teil durchläuft die vollen 175 Durchläufe von b&c am Ende wird dann auch nur das Matrixelement des entsprechenden a's aktuallisiert und das wurde ja voll berechnet. Dann wird gewartet bis alle a's voll berechnet sind und der nächste Iterationsschritt beginnt.

    Das Problem, welches hustbaer anspricht, besteht darin, dass die Ausführungsreihenfolge nicht garantiert ist. In dem von ihm zitierten Codestück schreibst du in Zeile 13/15 in matrix1. Außerdem wird in Zeile 7 matrix1 gelesen. Es ist aber zu diesem Zeitpunkt nicht klar, ob das Element welches gelesen wird von einem anderen Thread schon berechnet und aktualisiert wurde.
    Ohne eine zusätzliche Synchronisation (omp barrier) zwischen diesen beiden Codeteilen ist deine Berechnung also mit ziemlicher Sicherheit nicht korrekt.

    Jetzt verstehe ich, dass muss ich natürlich ändern. Speichere ich die Werte beim start jedes neuen Iterationsschritt einfach zwischen.



  • Simon S. schrieb:

    Ich könnte den LUT auf 170MB reduzieren. Würde es dann was bringen, wenn ich den LUT in 9 Teile zerlege -> ich bin mit jedem Teil unter 20MB und dann nacheinander 9x die 3er for-schleife ausführe. In jeder 3er for-schleife wird dann nur einer der 9 LUTs verwenden. Somit müsste ich pro Iteration nur 9x einen anderen LUT in den cache laden?

    Wenn ich dich richtig verstehe würdest du dann 9x so viel rechnen wie jetzt...?
    Dann wird das auch 9x langsamer.
    Da brauchst du dann schon mächtig viele Cores damit du das wieder aufholst, selbst wenn es dann (was nicht gesagt ist) perfekt skalieren sollte.

    Und natürlich müsstest du den Loop der die Wiederholungen für die 9 LUT Teile macht ganz aussen machen. Also ausserhalb der "a" Schleife

    for (int LUT = ...)
    {
         #pragma omp parallel for
        for (int a = ...)
        {
        }
    }
    

    Ich vermute so hast du das eh gemeint, nur damit kein Misverständnis passiert.

    ps: Du kannst das auch einfach lokal testen. Mit nem Quad-Core solltest du auch schon sehen ob und wie gut es skaliert. (Bloss nicht den Fehler machen Hyper-Threading "Hardware-Threads" mit vollständigen Cores zu verwechseln. Also bei nem Hyper-Threading Quad-Core (8 Threads) kann es mit 8 Threads niemals doppelt so schnell laufen wie mit 4.)

    Und da du mit float rechnest: welchen Compiler verwendest du, und hast du die nötigen Compiler-Switches für "fast math" und SSE2+ in Verwendung?



  • Also...
    Ein paar mehr Fragen. Ich vermute nämlich dass du doch nicht durch die Speicherbandbreite limitiert bist.

    1. Welche Zeit misst du, nur die die für RunFull() benötigt wird, oder was das gesamte Programm braucht?
    2. Wird die Berechnung zwischenErgebnis1 = a*85683+b*507+c*3; + darauffolgenden Zugriff auf den LUT mit zwischenErgebnis1 als Index genau so gemacht, oder das du das "verbeispielt"?
    3. Warum float zwischenErgebnis1 - der Wert ist immer ganzzahlig, und wenn du die Variable als Index in ein Array verwendest solltest du auch nen int (oder unsigned int, size_t ) verwenden.
    4. Wie viele echte Cores und wie viele "Hardware Threads" hat die Maschine auf der das läuft. Auf nem Quad-Core mit 32 Threads wird das z.B. nicht deutlich schneller werden. Der von dir genannte E5-2680 hat ja 10 Kerne -- ist dann halt die Frage wie viele solche E5-2680 in dem Teil drinstecken das deinen Code ausführt.

    Abhängig von den Antworten auf diese Fragen dann
    a) Miss mal getrennt nur die Zeit die RunFull() benötigt und was das gesamte Programm braucht. Kann ja sein dass der RunFull() Teil bereits perfekt skaliert, nur der Rest halt nicht.
    b) Ersetze mal das "jeden Float einzeln mit fread einlesen" durch einen einzigen fread Aufruf.
    c) Was du probieren kannst, aber vermutlich nicht viel bringen wird (oder u.U. sogar schaden kann): setz mal das #pragma omp parallel for eins weiter nach innen, also vor die "b" Schleife. Falls du wirklich (was ich wie gesagt nicht mehr glaube) durch die Speicherbandbreite limitiert bist, sollte das was bringen. Siehste dann ja.
    d) Geh nochmal den gesamten Code durch und guck ob du noch weitere " float wo int sein sollte" Fälle o.Ä. findest.



  • Danke für deine Antwort.
    Ich habe den LUT aufgeteilt sodass in jeder 3er for-Schleife max 20MB sind.
    Außerdem habe ich einige if's vor die Iteration gezogen.
    Der Geschwindigkeitsboost von 12,8s -> 6,3s kommt aber von den vorgezogenen if's nicht von der Aufteilung.

    Habe jetzt folgende Werte:
    1 Thread: 6,3s
    2 Threads: 3,3s
    4 Threads: 2,1s
    8 Threads: 1,4s
    16 Threads: 1,3s
    32 Threads: 1,3s

    Keine Verbesserung ab 8 Threads 😕

    Ich verwende den Intel Compiler mit folgen flags -O3 -openmp -xCORE-AVX-I
    Die flags -no-prec-div -ansi-alias haben nichts gebracht.
    Gibt es denn noch andere flags die ich benutzen soll. Ich habe nach einer Single precision flag gesucht aber nichts gefunden.

    //Global Variablen
    float matrix1[175];
    float matrix2[175];
    float matrix3[175];
    float matrix4[175];
    
    void RunApproximation(float lut3Linear[], float iterations1, float iterations2, float iterations3)
    {
    	//RunApproximation führt eine approximierte Berechnung aus und liefert gute Startwerte für die RunFull-Funktion. Die Startwerte werden in den Matrizen 1-4 gespeichert. 
    }
    
    void RunFull(float lut3Linear[], float iterations1, float iterations2, float iterations3)
    {
    	//Anzahl der Threads für openMP wird festgelegt
    	omp_set_num_threads(32);
    
    	//Die Iteration startet, welche nahezu die gesamte Berechnungszeit beansprucht
    	for (int iter=1; iter<500; iter++) {
    
    		//Matrix zwischenspeichern damit deterministisch
    		float matrix1Det[175];
    		for (int I=0; I<175; I++) {
    			matrix1Det[I] = matrix1[I];
    		}
    
    		//Ein Gewicht wird berechnet, für die spätere aktuallisierung der gloablen Matrizen 1-4
    		float gewicht = 1.0f / (float)Iter;
    
    		//Es werden ein paar einfache schnelle Berechnungen ausgeführt.
    		float matrix1Prozent = 0.0f;
    		for (int I=0; I<175; I++) {
    				matrix1Prozent = matrix1Prozent+2.0f*matrix1Det[I];
    
    		}
    		matrix1Prozent = matrix1Prozent*0.145f;
    		...
    
    		//Hier startet meine Parallelisierung
    		#pragma omp parallel for
    		for (int a=0; a<44; a++) {
    			//Es werden bei jedem Schleifendurchlauf bestimmte Berechnungswerte auf 0 gesetzt
    			float berechnung1 = 0.0f;
    			float berechnung2 = 0.0f;
    			float berechnung3 = 0.0f;
    			...
    			for(int b=0; b<175; b++) {
    				for(int c=0; c<175; c++) {
    					//Es werden ein paar Zwischenergebnisse berechnet die häufiger benötigt werden
    					float zwischenErgebnis1 = a*85683+b*507+c*3;
    					float zwischenErgebnis2 = matrix1Det[b] * matrix2Det[c];
    					float zwischenErgebnis3 = matrix3Det[b] * matrix4Det[c];
    					...
    
    					//Mehrer Berechnungen finden statt und werden jeweils aufaddiert
    					berechnung1 = berechnung1 + ((3.0f*iterations1) * lut3Linear[zwischenErgebnis1] - iterations2) * zwischenErgebnis2;
    					berechnung2 = berechnung2 + ((2.0f*iterations1) * lut3Linear[zwischenErgebnis1+1] - iterations2) * zwischenErgebnis3;
    					berechnung3 = berechnung3 + ((3.0f*iterations2) * lut3Linear[zwischenErgebnis1] - iterations3) * zwischenErgebnis2;
    					...
    				}
    			}
    			//Wieder einige Berechnungen
    			berechnung1 = berechnung1 / berechnung2;
    
    			//Hier findet ein Vergleich statt und anschließend werden die gloalen Matrizen 1-4 aktuallisiert
    			if (berechnung1 > (-1.0f)) {
    				matrix1[a]=((1.0f-gewicht)*matrix1[a]) + gewicht;
    			} else {
    				matrix1[a]=((1.0f-gewicht)*matrix1[a]);
    			}
    			...
    		}
    		//Hier endet die Parallelisierung
    		#pragma omp barrier
    		#pragma omp parallel for
    		for (int a=0; a<44; a++) {
    			//Hier steht das gleiche, wie in der ersten for-Schleife nur mit LUT für diese a's
    		#pragma omp barrier
    		#pragma omp parallel for
    		for (int a=0; a<44; a++) {
    			//Hier steht das gleiche, wie in der ersten for-Schleife nur mit LUT für diese a's
    		#pragma omp barrier
    		#pragma omp parallel for
    		for (int a=0; a<43; a++) {
    			//Hier steht das gleiche, wie in der ersten for-Schleife nur mit LUT für diese a's
    		#pragma omp barrier
    	}
    	//Hier werden dann noch die berechneten Matrizen ausgegeben
    	....
    }
    
    int main(int argc, char *argv[])
    {
    	//Daten werden aus Datei einlesen
    	float *lut3Linear = (float*)malloc(sizeof(float)*175*175*175*9);
    	FILE * lut3LinearFile;
        lut3LinearFile = fopen("LUT3linearFloat.dat", "rb");
    	for(int a=0; a<175; a++) {
    		for(int b=0; b<175; b++) {
    			for(int c=0; c<175; c++) {
    				for(int d=0; d<9; d++) {
    					fread(&lut3Linear[a*175*175*9+b*175*9+c*9+d], sizeof(float), 1, lut3LinearFile);
    				}
    			}
    		}
    	}
    	fclose (lut3LinearFile);
    	...
    
    	//Der Benutzer soll solange Berechnungen durchführen können, bis die Anwendung gekillt wird
    	while(1)
    	{
    		//Daten werden per Console vom Benutzer abgefragt
    		float eingabe1, eingabe2;
    
    		cin >> eingabe1;
    		cin >> eingabe2;
    		...
    
    		//Aus der Eingaben vom Benutzer werden neue Werte für die Iteration berechnet
    		float iterations1, iteration2, iteration3;
    		...
    
    		//Iteration wird aufgerufen
    		RunApproximation(lut3Linear, iterations1, iteration2, iteration3);
    		RunFull(lut3Linear, iterations1, iteration2, iteration3);
    	}
    
    }
    


  • hustbaer schrieb:

    Also...
    Ein paar mehr Fragen. Ich vermute nämlich dass du doch nicht durch die Speicherbandbreite limitiert bist.

    1. Welche Zeit misst du, nur die die für RunFull() benötigt wird, oder was das gesamte Programm braucht?
    2. Wird die Berechnung zwischenErgebnis1 = a*85683+b*507+c*3; + darauffolgenden Zugriff auf den LUT mit zwischenErgebnis1 als Index genau so gemacht, oder das du das "verbeispielt"?
    3. Warum float zwischenErgebnis1 - der Wert ist immer ganzzahlig, und wenn du die Variable als Index in ein Array verwendest solltest du auch nen int (oder unsigned int, size_t ) verwenden.
    4. Wie viele echte Cores und wie viele "Hardware Threads" hat die Maschine auf der das läuft. Auf nem Quad-Core mit 32 Threads wird das z.B. nicht deutlich schneller werden. Der von dir genannte E5-2680 hat ja 10 Kerne -- ist dann halt die Frage wie viele solche E5-2680 in dem Teil drinstecken das deinen Code ausführt.

    Abhängig von den Antworten auf diese Fragen dann
    a) Miss mal getrennt nur die Zeit die RunFull() benötigt und was das gesamte Programm braucht. Kann ja sein dass der RunFull() Teil bereits perfekt skaliert, nur der Rest halt nicht.
    b) Ersetze mal das "jeden Float einzeln mit fread einlesen" durch einen einzigen fread Aufruf.
    c) Was du probieren kannst, aber vermutlich nicht viel bringen wird (oder u.U. sogar schaden kann): setz mal das #pragma omp parallel for eins weiter nach innen, also vor die "b" Schleife. Falls du wirklich (was ich wie gesagt nicht mehr glaube) durch die Speicherbandbreite limitiert bist, sollte das was bringen. Siehste dann ja.
    d) Geh nochmal den gesamten Code durch und guck ob du noch weitere " float wo int sein sollte" Fälle o.Ä. findest.

    zu 1) habe die Gesamtzeit gemessen. Habe aber auch schon mal getrennt gemessen und RunFull() hat nur gewicht
    zu 2) das wird wirklich so gemacht
    zu 3) das stimmt, ist immer ganzzahlig
    zu 4) stimmt der hat 10, hab htops während der Berechnung laufen lassen und das zeigt mir 32 Kerne an. Allerdings haben diese eine max. Auslastung von ~70%. Könnte auch an der Trägheit liegen, da die Berechnung ja nur kurz ist.

    zu a) siehe 1)
    zu b) die LUT werden ja nur einmal eingelesen, diese Zeit wurde auch nicht gemessen und ist eigt. auch egal
    zu c) muss ich dann noch testen
    zu d) sonst nichts weiter gefunden. ist es eigt. besser float * float zu machen anstatt float * int, weil theoretisch könnte ich meine LUTs auch auf int umstellen, da es bei der ganzen Sache nur um Verhältnisse geht



  • Ist openmp wirklich akzeptabel für sowas? So allgemein unter Entwicklern meine ich.

    Ich würde das nie machen, allein schon weil ich nicht weiß was genau das Ding im Hintergrund macht. Ich würde auf jeden Fall von Hand threads starten und Funktionspointer übergeben.



  • randa schrieb:

    Ist openmp wirklich akzeptabel für sowas? So allgemein unter Entwicklern meine ich.

    Ich würde das nie machen, allein schon weil ich nicht weiß was genau das Ding im Hintergrund macht. Ich würde auf jeden Fall von Hand threads starten und Funktionspointer übergeben.

    Und wie würdest du eine Schleife parallisieren?

    #pragma omp parallel for
    for(int i = 0; i < n; i++)
    {
        arr[i] = func();
    }
    

    Das mit (std::)Threads nachzubauen sollte gehen, ist aber ziemlich viel Arbeit, dafür dass du dich gegen einen Standard durchsetzen willst. (Und du kannst nicht durch ein Compilerflag sämtliche Parallelisierung rausnehmen...)

    Und die Jungs, die OpenMP implementieren auf den einzelnen Compilern, haben gewöhnlich schon ein bisschen Ahnung und wissen, was sie machen.

    Es ist halt für High Performance Computing und nicht um mal eben in ner Business Application einen Thread Pool für Requests zu managen.

    Ich hab mir jetzt zwar nicht den den Code vom OP im Detail angeschaut, aber das sieht schon ganz gut aus, was die Zuständigkeit von OpenMP angeht.



  • Skym0sh0 schrieb:

    Und wie würdest du eine Schleife parallisieren?

    #pragma omp parallel for
    for(int i = 0; i < n; i++)
    {
        arr[i] = func();
    }
    

    naja ich würde jeden Thread n/n_threads elemente durchlaufen lassen

    Es ist halt für High Performance Computing und nicht um mal eben in ner Business Application einen Thread Pool für Requests zu managen.

    gerade da würde ich darauf bestehen dass ich alles von Hand mache. Deswegen frage ich ob das in computing projekten auch wirklich einfach mit einer handvoll #pragmas abgekanzelt wird, ich zweifle.



  • randa schrieb:

    Skym0sh0 schrieb:

    Und wie würdest du eine Schleife parallisieren?

    #pragma omp parallel for
    for(int i = 0; i < n; i++)
    {
        arr[i] = func();
    }
    

    naja ich würde jeden Thread n/n_threads elemente durchlaufen lassen

    Und wie siehts aus mit?

    #pragma omp parallel for schedule(guided)
    for(int i = 0; i < n; i++)
    {
        arr[i] = func();
    }
    

    randa schrieb:

    Es ist halt für High Performance Computing und nicht um mal eben in ner Business Application einen Thread Pool für Requests zu managen.

    gerade da würde ich darauf bestehen dass ich alles von Hand mache. Deswegen frage ich ob das in computing projekten auch wirklich einfach mit einer handvoll #pragmas abgekanzelt wird, ich zweifle.

    Naja, es gibt ja noch andere Tricks/Frameworks, z.B. MPI.
    OpenMP bietet halt noch sehr viel Stuff mehr als nur eine kleine Kapsel um Threads.

    Umgekehrt gebe ich dir Recht, dass gerade mit der std::Threading Bibliothek viele coole Sachen hinzugekommen sind wie der Mutex-Lock im RAII Objekt gekapselt



  • randa schrieb:

    Deswegen frage ich ob das in computing projekten auch wirklich einfach mit einer handvoll #pragmas abgekanzelt wird, ich zweifle.

    Wieso nicht?
    Der OpenMP/Cilk/AMP/TBB/... Scheduler ist weitaus performanter als alles was man selbst mit vertretbarem Aufwand hinbekommt.



  • @Simon S.
    Hast du mal probiert num_threads beim #pragma parallel for zu verwenden statt bzw. zusätzlich zu omp_set_num_threads ?
    Oder mal nen anderen Compiler probiert (MSVC, GCC)?



  • hustbaer schrieb:

    Wieso nicht?

    man kann nicht sehen was konkret am Ende für ein Code produziert wird. Und bei parallelisierung und kritischen Anwendungen will ich das genau wissen.


Log in to reply