3. Berechnungsgenauigkeit bei double einstellen?

Berechnungsgenauigkeit bei double einstellen?

  • ?

    die Aussage float ist schneller als double stimmt einfach so nicht (wenn nicht der Cache/Memory ein Problem ist - was hier unklar ist)

    falls mit x86 FPU gerechnet wird wirds sowiso nach 80Bit konvertiert - da schenken sich floats und doubles nichts - vor vielen vielen Jahren war das noch ganz anders (und daher kommen auch diese Float-Mythen)

    Es ist einfach sehr algorithmenabhängig was Speed bringt

    0
  • B

    Wozu diese Diskussion?

    In der Steinzeit der PCs wurde die Berechnung für Gleitkomma mit einer Software-Emulation
    gemacht (sehr langsam) oder man musste einen teuren CoProzessor hinzukaufen (deutlich schneller).

    Die Performance juckt heute nicht. Allein entscheidend ist nur die Genauigkeit, also der darstellbare
    Wertebeich, nicht die Anzahl der Nachkommastellen oder die Größe der Werte. Danach wählt man den
    Datentyp float oder double.

    0
  • M

    Gast3 schrieb:

    falls mit x86 FPU gerechnet wird wirds sowiso nach 80Bit konvertiert - da schenken sich floats und doubles nichts - vor vielen vielen Jahren war das noch ganz anders (und daher kommen auch diese Float-Mythen)

    Vor vielen Jahren war das auch noch so, dass man die x86 FPU verwendet hat. Heutzutage verwendet man als vernuenftiger Programmierer meistens SSE und dabei rechnet man mit floats schon schneller, weil eben nur mit 32 bits statt mit 80 gerechnet wird. Und wenn der Compiler auch noch vektorisieren kann, kann man mit floats sogar doppelt so viele Rechenoperationen gleichzeitig durchfuehren wie mit double.

    berniebutt schrieb:

    In der Steinzeit der PCs wurde die Berechnung für Gleitkomma mit einer Software-Emulation
    gemacht (sehr langsam) oder man musste einen teuren CoProzessor hinzukaufen (deutlich schneller).

    Die Performance juckt heute nicht. Allein entscheidend ist nur die Genauigkeit, also der darstellbare Wertebeich, nicht die Anzahl der Nachkommastellen oder die Größe der Werte. Danach wählt man den
    Datentyp float oder double.

    Mir sind ausser wissenschaftlichen Berechnungen mit hoher Genauigkeit eigentlich keine Anwendungsgebiete bekannt, bei denen man diese extrem hohen/kleinen Werte und so viele Nachkommastellen wirklich braucht. Die fuer die meisten Menschen und alltaegliche Anwendungsgebiete relevanten Groessen sind vielleicht +- 6 Groessenordnungen mit 3 Nachkommastellen. Diese Bedingungen erfuellen floats locker und auf der anderen Seite bedarf es gerade bei Bildverarbeitung, Spielen und Rendern einer hohen Geschwindigkeit.

    0

  • stud145 schrieb:

    Ist denn diese Aussage richtig?

    64-Bit Prozessoren arbeiten mit 64-Bit Datenpaketen schneller.

    Nö, ist nicht richtig.
    Mag auf manche 64-Bit Prozessoren bei manchen Befehlen zutreffen, aber so allgemein wie das da steht ist es Quatsch.

    Gast3 schrieb:

    die Aussage float ist schneller als double stimmt einfach so nicht (wenn nicht der Cache/Memory ein Problem ist - was hier unklar ist)

    Und wie die stimmt.
    Wer Anno 2014 noch die x87 Befehle verwendet gehört mit dem nassen Fetzen geschlagen.
    Und mit den diversen Vektorbefehlen sind float Berechnungen nie langsamer und so-gut-wie immer schneller als double Berechnungen.

    0
  • ?

    In der Theorie ist auf aktuell gängigen Architekturen float schneller als double:

    • Mit SSE/AVX (bzw. allgemein SIMD) lassen sich doppelt so viele Rechenschritte auf floats ausführen wie auf doubles
    • Divisonen sind für float schneller (Takte, Throughput) als für double (zumindest auf meiner CPU), alles andere ist ziemlich gleich schnell (siehe HIER Seite 200)
    • Doppelt so viele Daten liegen gleichzeitig im Cache
    • Man schont Bandbreite, weil nur die Hälfte an Bytes für die gleiche Menge Daten herangeschafft werden muss
    • [Alles unter der Annahme, dass sizeof(double) = 2*sizeof(float). Aber wo ist das nicht so...]

    In der Praxis merke ich meist keinen Unterschied:

    • Die Operationen auf Fließkommazahlen in Bottlenecks sind in der Regel komplex genug, dass nur ein kleiner Teil vernünftig vektorisiert werden kann (Branching, Overhead durch Umsortieren von Daten etc.)
    • Limitierend ist in beiden Fällen oft die Bandbreite zum Cache (vor allem, wenn man mit anderen Kernen kämpfen muss)
    • Wenn man nicht gerade in einem schönen Muster über seine Daten läuft, dann wartet man mehr auf den Speicher als auf die paar Takte zum Ziehen einer Wurzel
    • Es ist ziemlich schwer bei realen Problem die Dependency Chains so weit zu brechen, dass man die Pipelines der CPU wirklich voll nutzen kann
    • Theoretisch werden floats schneller denormalisiert. Dann kann es teuer werden

    Von daher würde ich immer zu double raten. Wenn dann alles läuft, kann man immernoch messen und mit float experimentieren. Es gibts nichts Schlimmeres als einen Bug wegen unzureichender Genauigkeit zu haben (da macht das Debuggen Spaß). Oder hat hier jemand völlig andere Ansichten? 😃 (Grafikkarten zählen nicht!)

    0
  • ?

    Vielen dank für eure Antworten. Habe jetzt das Programm von double auf float umgestellt dadurch bin ich von 24 Sekunden auf 22 Sekunden gekommen. Was für mich aber noch um den Faktor 10 zu langsam ist.

    Welche Möglichkeiten habe ich noch die Geschwindigkeit zu erhöhen? Für die Genauigkeit reichen mit float aus.

    Musste mir über die Geschwindigkeit noch nie Gedanken machen auch über Links zu dem Thema wäre ich sehr dankbar.

    int main()
{

	float *DATA = (float*)malloc(sizeof(float)*175*175*175*13);

	float TempS3Matrix[175];

	float S1Matrix[175];
	float S2Matrix[175];
	float S3Matrix[175];

	int MaxIters = 500;
	float S1, S2, S3;
	float Size;
	float Kor;
	float SSum;

	printf("Daten werden eingelesen...\n");
	int a,b,c,d;
	FILE * DATAFile;
    DATAFile = fopen("DATA.dat", "rb");
	for(a=0; a<175; a++) {
		for(b=0; b<175; b++) {
			for(c=0; c<175; c++) {
				for(d=0; d<13; d++) {
					fread(&DATA[a*175*175*13+b*175*13+c*13+d], sizeof(float), 1, DATAFile);
				}
			}
		}
	}
	fclose (DATAFile);
	printf("Daten fertig eingelesen\n");

	cout << "S1[float]: ";
	cin >> S1;
	cout << "S2[float]: ";
	cin >> S2;
	cout << "S3[float]: ";
	cin >> S3;
	cout << "Size[float]: ";
	cin >> Size;
	cout << "Kor[float]: ";
	cin >> Kor;

	SSum = S1 + S2 + S3 + 3*Kor;

	for (int I=0; I<175; I++) {
			S1Matrix[I] = 0.0;
			S2Matrix[I] = 0.0;
			S3Matrix[I] = 0.5;

	}

	for (int I=0; I<117; I++) {
			S1Matrix[I] = 1.0;
	}

	for (int I=0; I<78; I++) {
			S2Matrix[I] = 1.0;
	}

	//Hier lässt sich noch einiges optimieren ist aber nicht der Flaschenhals
	float NAP1 = 0.65f*(S3+Kor)/SSum + 0.35f*(((S1+Kor)/SSum*(S3+Kor)/(SSum-(S1+Kor)))+((S2+Kor)/SSum*(S3+Kor)/(SSum-(S2+Kor))));
	float NAP2 = 0.65f*(S3*2.0f+S2+3.0f*Kor)/SSum + 0.35f*((S1-S3)/SSum*(S3*2.0f+S2+3.0f*Kor)/(SSum-(S1-S3)));
	float NAP3 = 0.65f*(S3*2.0f+S2+3.0f*Kor)/SSum + 0.35f*((S1-S3)/SSum*(S3*2.0f+S2+3.0f*Kor)/(SSum-(S1-S3)));			
	float NAP4 = 0.65f*(S3*2.0f+S2+3.0f*Kor)/SSum + 0.35f*((S1-S3)/SSum*(S3*2.0f+S2+3.0f*Kor)/(SSum-(S1-S3)));
	float NAP5 = 0.65f*(S3+0.5f*S2+1.5f*Kor)/SSum + 0.35f*((S1+0.5f*S2+1.5f*Kor)/SSum*(S3+0.5f*S2+1.5f*Kor)/(SSum-(S1+0.5f*S2+1.5f*Kor)));
	float NAP6 = 0.35f;
	float NAP7 = 0.35f;
	float NAP8 = 0.35f;
	float NAP9 = 0.65f*(S2*3.0f/2.0f+(S3-S2)*2.0f+1.5f*Kor)/SSum + 0.35f*(((S1-S3)/SSum*(S2*3.0f/2.0f+(S3-S2)*2.0f+1.5f*Kor)/(SSum-(S1-S3)))+((S2*3.0f/2.0f+1.5f*Kor)/SSum*(S2*3.0f/2.0f+(S3-S2)*2.0f+1.5f*Kor)/(SSum-(S2*3.0f/2.0f+1.5f*Kor))));
	float NAP10 = 0.65f*((S3-S2)*2.0f)/SSum + 0.35f*(((S1-S3)/SSum*((S3-S2)*2.0f)/(SSum-(S1-S3)))+((S2*3.0f+3.0f*Kor)/SSum*((S3-S2)*2.0f)/(SSum-(S2*3.0f+3.0f*Kor))));
	float NAP11 = 0.0f;
	float NAP12 = 0.65f*(S3-S2)/SSum + 0.35f*(((S1-S2)/SSum*(S3-S2)/(SSum-(S1-S2)))+((3.0f*S2+3.0f*Kor)/SSum*(S3-S2)/(SSum-(3.0f*S2+3.0f*Kor))));
	float NAP13 = 0.0f;

	float NAPF1 = 0.65f*(S3-Size)/SSum + 0.35f*(((S1+0.5f*Size+1.5f*Kor)/SSum*(S3-Size)/(SSum-(S1+0.5f*Size+1.5f*Kor)))+((S2+0.5f*Size+1.5f*Kor)/SSum*(S3-Size)/(SSum-(S2+0.5f*Size+1.5f*Kor))));
	float NAPF2 = 0.65f*(S3-Size)/SSum + 0.35f*((S1+Size+S2+3*Kor)/SSum*(S3-Size)/(SSum-(S1+Size+S2+3*Kor)));
	float NAPF3 = 0.65f*(S3-Size)/SSum + 0.35f*(((S1-S2)/SSum*(S3-Size)/(SSum-(S1-S2)))+((S2*2+Size+3*Kor)/SSum*(S3-Size)/(SSum-(S2*2.0f+Size+3.0f*Kor))));
	float NAPF4 = 0.65f*(S3-Size)/SSum + 0.35f*(((S1+0.5f*Size+1.5f*Kor)/SSum*(S3-Size)/(SSum-(S1+0.5f*Size+1.5f*Kor)))+((S2+0.5f*Size+1.5f*Kor)/SSum*(S3-Size)/(SSum-(S2+0.5f*Size+1.5f*Kor))));
	float NAPF5 = 0.65f*(S3-Size)/SSum + 0.35f*((S1+S2+Size+3.0f*Kor)/SSum*(S3-Size)/(SSum-(S1+S2+Size+3.0f*Kor)));
	float NAPF6 = 0.65f*(S3-Size)/SSum + 0.35f*((S1+S2+Size+3.0f*Kor)/SSum*(S3-Size)/(SSum-(S1+S2+Size+3.0f*Kor)));
	float NAPF7 = 0.65f*(S3-Size)/SSum + 0.35f*((S1+S2+Size+3.0f*Kor)/SSum*(S3-Size)/(SSum-(S1+S2+Size+3.0f*Kor)));
	float NAPF8 = 0.65f*(S3-Size)/SSum + 0.35f*((S1+S2+Size+3.0f*Kor)/SSum*(S3-Size)/(SSum-(S1+S2+Size+3.0f*Kor)));
	float NAPF9 = 0.65f*(S3-Size)/SSum + 0.35f*(((S1-S2)/SSum*(S3-Size)/(SSum-(S1-S2)))+((S2*2.0f+Size+3.0f*Kor)/SSum*(S3-Size)/(SSum-(S2*2.0f+Size+3.0f*Kor))));
	float NAPF10 = 0.65f*(S3-Size)/SSum + 0.35f*(((S1-S2)/SSum*(S3-Size)/(SSum-(S1-S2)))+((S2*2.0f+Size+3.0f*Kor)/SSum*(S3-Size)/(SSum-(S2*2.0f+Size+3.0f*Kor))));
	float NAPF11 = 0.65f*(S3-Size)/SSum + 0.35f*(((S1-S2)/SSum*(S3-Size)/(SSum-(S1-S2)))+((S2*2.0f+Size+3.0f*Kor)/SSum*(S3-Size)/(SSum-(S2*2.0f+Size+3.0f*Kor))));
	float NAPF12 = 0.65f*(S3-Size)/SSum + 0.35f*(((S1-S2)/SSum*(S3-Size)/(SSum-(S1-S2)))+((S2*2.0f+Size+3.0f*Kor)/SSum*(S3-Size)/(SSum-(S2*2.0f+Size+3.0f*Kor))));
	float NAPF13 = 0.65f*(S3-Size)/SSum + 0.35f*(((S1+0.5f*Size+1.5f*Kor)/SSum*(S3-Size)/(SSum-(S1+0.5f*Size+1.5f*Kor)))+((S2+0.5f*Size+1.5f*Kor)/SSum*(S3-Size)/(SSum-(S2+0.5f*Size+1.5f*Kor))));

	for (int Iter=0; Iter<MaxIters; Iter++) {
		float WeightNew=1.0f/(float) (Iter+1);
		for (int A=0; A<175; A++) {
			float mEV = 0.0;
			float mEVFold = 0.0;

			for(int B=0; B<175; B++) {
				for(int C=0; C<175; C++) {
					float fix = S1Matrix[B] * S2Matrix[C];
					int ABC = A*175*175*13+B*175*13+C*13;
					mEV += (NAP1 * DATA[ABC] + NAP2 * DATA[ABC+1] + NAP3 * DATA[ABC+2] + NAP4 * DATA[ABC+3] + NAP5 * DATA[ABC+4] + NAP6 * DATA[A*175*175*13+B*175*13+C*13+5] + NAP7 * DATA[ABC+6] + NAP8 * DATA[ABC+7] + NAP9 * DATA[ABC+8] + NAP10 * DATA[ABC+9] + NAP12 * DATA[ABC+11]) * fix;
					mEVFold += (NAPF1 * DATA[ABC] + NAPF2 * DATA[ABC+1] + NAPF3 * DATA[ABC+2] + NAPF4 * DATA[ABC+3] + NAPF5 *DATA[ABC+4] + NAPF6 * DATA[A*175*175*13+B*175*13+C*13+5] + NAPF7 *DATA[ABC+6] + NAPF8 * DATA[ABC+7] + NAPF9 * DATA[ABC+8] + NAPF10 *DATA[ABC+9] + NAPF11 * DATA[ABC+10] + NAPF12 * DATA[ABC+11] + NAPF13 * DATA[ABC+12]) * fix;
				}
			}

			if (mEV >= mEVFold) {
				S3Matrix[A]=((1.0f-WeightNew)*S3Matrix[A]) + (WeightNew*1.0f);
			} else {
				S3Matrix[A]=((1.0f-WeightNew)*S3Matrix[A]);
			}
		}

	}
	system("pause");
	return 0;
}
    0
  • Mod

    Was tut das Programm und warum?

    0
  • ?

    1. woher weisst du welche Teile des Programmes die Zeit fressen?
    2. sind die 22Sek die komplette Laufzeit? (also mit dem fread)
    3. Release/Debug-Mode?
    4. Zeitmessung (wie) in der IDE/Konsole?

    4 Fragen => 4 Antworten

    0
  • ?

    Ist ein Ficticious Play Algorithmus.

    - Liest er Daten ein.
    - dann werden die NAP1-13 und NAPF-13 berechnet
    - dann kommt die Schleife
    hier wird für jedes A eine Summe über alle Elemente von B/C gebildet mEV und mEVFold
    - mEV und mEVFold werden dann verglichen und die S3Matrix mit Gewichten angepasst, sodass sie irgendwann auf einen festen Wert konvergiert

    0
  • ?

    zu 1. Hab einen Timer aus einen anderen Programm der mir die Microsekunden angibt für die 2x13 NAP-Werte fallen 0,3 Microsekunden, was bei 500 Iterationen nicht ins Gewicht fällt
    zu 2. Die 22 Sekunden starten nach der eingabe von Kor, also erst nachdem alle Daten eingelesen wurden
    zu 3. Release Mode 64 Bit
    zu 4. Habe das Programm in der Console ausgeführt

    0
  • ?

    solange du die Menge der Berechnungen nicht reduzieren kannst sieht nicht so aus als könnte man was mit einfachen mitteln machen

    also bleiben die Fragen an Google:
    -gibt es Optimierungsstrategien spezielle für diesen Algorithmus
    -Beschleunigung mittels SIMD-Instruktionen (SSE2,SSE3,...)
    -Parallelisierung möglich (Threads, OMP, AMP)?

    Links:

    http://msdn.microsoft.com/de-de/library/vstudio/hh265136(v=vs.110).aspx
    http://www.drdobbs.com/parallel/how-to-write-a-parallelfor-loop-matrix-m/228800433
    http://www.geeks3d.com/20100711/test-simple-x87-vs-sse2-performance-test-with-matrix-multiplication/

    und noch 1Mio andere Links

    0
  • ?

    Das Skalarprodukt in den Zeilen 106 und 107 kannst Du doch sicherlich aus der Schleife rausziehen und einmal im voraus berechnen.

    0
  • C
    Mod

    Überschlägig abgeschätzt, würde ich sagen, dass der Compiler ganz ordentlich arbeitet, wenn das Programm 22 Sekunden braucht.
    Unterstellt: Takt 3Ghz ergibt 66.000.000.000 Zyklen
    500*175*175*175 = 2679687500
    Also ca. 24.5 Zyklen/Schleifendurchgang, mit jeweils ca. 25 (Gleitkomma-)Multiplikationen und 25 Additionen. Ein paar Details könnte man ändern (Multiplikation mit fix herausziehen; gleiche Koeffizienten - z.B. NAPF9-NAPF12 sind gleich - ausnutzen: erst summieren, dann einmal multiplizieren). Ansonsten siehe Gast3.

    0
Anmelden zum Antworten