Vektorisierung

Ich wollte ein wenig mit SSE2 spielen und hab dabei ein paar Versuche gestartet.

2 Double-Vektoren b und c sollen addiert werden und das Ergebnis soll in den Vektor c geschrieben werden.

Ich habe verschiedene Array-Größen getestet , wobei ich mich hier mal auf
N = 10000000 beziehe.

Ich habe das ganze 100 mal durchgeführt und die Gesamtausführungszeit gemessen.

Einmal mit SSE2, einmal ohne.

Compiler gcc 4.7, -O0 als Optimierung.

Zeit wurde mit clock_gettime(CLOCK_MONOTONIC, ...) gemessen.

Leider unterscheidet sich die Gesamtausführungszeit für die 100 Additionen fast nicht. Sowohl mit als auch ohne SSE erhalte ich 4 Sekunden und ein paar zerquetschte. Hier der Code. Das einzige, das fehlt ist die Timer-Klasse, die nur die clock_gettime-Methode kapselt.

#include <iostream>
#include <vector>
using namespace std;

#include "Timer.h"

#include <emmintrin.h>

void add_vector(double *a, double *b, double *c, const unsigned int& N)
{
	__m128d *av, *bv, *cv;
	av = (__m128d *) a; // assume 16-byte aligned
	bv = (__m128d *) b; // assume 16-byte aligned
	cv = (__m128d *) c; // assume 16-byte aligned
	for (unsigned int i = 0; i < N / 2; i++)
		av[i] = _mm_add_pd(bv[i], cv[i]);
}

void add(double *a, double *b, double *c, const unsigned int& N)
{
	for (unsigned int i = 0; i < N; i++)
		a[i] = b[i] + c[i];
}

int main()
{
	Timer timer;

	const unsigned int N = 10000000;
	double *a, *b, *c;
	a = (double*) malloc(N * sizeof(double));
	b = (double*) malloc(N * sizeof(double));
	c = (double*) malloc(N * sizeof(double));

	for (unsigned int i = 0; i < N; i++)
	{
		c[i] = b[i] = i;
	}

	const unsigned int iterations = 100;

	timer.start();
	for (unsigned int i = 0; i < iterations; i++)
	{
// entweder erste oder zweite Variante, nie beide in einem Programmlauf
		add_vector(a, b, c, N);      
		add(a,b,c,N);
	}
	timer.stop();

	cout << a[N-1] << endl;

	timer.printStoppedTime();

	return 0;
}

Einmal echte Ausgaben:
Ohne Vektorisierung: 4:432148737 (Sec:nanosec)
Mit Vektorisierung : 4:103451164

Ganz vergessen hinzuschreiben, was ich eigentlich will^^

Warum sind die gemessenen Zeiten so ähnlich?

Liegt hier ein fehler in der Benutzung vor?
Ist das Beispiel zu einfach?

Werden vlt doch an irgendeiner Stelle trotz -O0 Optimierungen vorgenommen?
Eventuell "merkt" das Programm ja dass es 100 mal das selbe ausführt oder so...

Sind die Laufzeiten realistisch?
Vielleicht ist ja auch nur meine Timer-Klasse nicht ok?

SeppJ

Sind denn fast 10% mehr Speed nicht genug? Du machst schließlich fast nix mit den Daten. Das heißt, die meiste Zeit wird dein Programm bloß Daten aus dem Speicher in die CPU-Register schaufeln, ob es die normalen Register sind oder die SSE-Register: Der Unterschied ist bloß ob die CPU dann ein oder zwei Schritte pro Datenpaar braucht, aber für jedes Datenpaar werden einige CPU-Schritte zum Umherschaufeln draufgehen.

Im übrigen kann ich die Zahlen bestätigen (i7, GCC 4.8, Zeit gemessen mit Linux time Kommando):
O0: 5.6 s vs 4.2 s (bei mir also ein bisschen krasser, kann am System liegen)
O3: 2.8 s vs 2.7 s
O3, native: 2.7 s vs 2.7 s
O3, native, lto: 2.7 s vs 2.7 s

Und noch ein alter Spruch: Niemanden interessiert es, wie schnell oder langsam unoptimierter Code läuft.

krümelkacker

shisha schrieb:

Leider unterscheidet sich die Gesamtausführungszeit für die 100 Additionen fast nicht.

Schau dir doch mal an, was für ein Assemblercode da generiert wird.

Ich denke aber, dass die CPU hier gar nicht der Flaschenhals ist, sondern der Speicher. Du läufst zwar schön linear durch drei Speicherbereiche, berechnest aber nur sehr wenig. Eine Floatingpoint-Addition ist heute glaub'ich relativ billig. Das würde bedeuten: Die Berechnungen kosten zwar weniger Taktzyklen, aber nun wartet die CPU auf die neuen Daten aus dem Speicher und hat kaum etwas zu tun.

Deswegen lohnt sich std::valarray ja auch nicht wirklich, auch wenn es SSE-optimiert implementiert wurde. valarray kann gegen etwas ähnliches was per Expression-Templates implementiert wurde, heutzutage nicht mehr richtig gegen anstinken -- performancetechnisch.

knivil

Mein Compiler (Vs2012) erzeugt auch fuer die Funktion 'add' SSE2-Intruktionen. Hinzu kommt loop unrolling.

SeppJ

knivil schrieb:

Mein Compiler (Vs2012) erzeugt auch fuer die Funktion 'add' SSE2-Intruktionen. Hinzu kommt loop unrolling.

Auch in unoptimiertem Code? Das finde ich aber arg aggressiv. Wie soll man denn bei loop unrolling noch vernünftig debuggen?

knivil schrieb:

Mein Compiler (Vs2012) erzeugt auch fuer die Funktion 'add' SSE2-Intruktionen. Hinzu kommt loop unrolling.

Aber nur, wenn das in den Optionen so eingestellt ist. Aber selbst wenn ich die Erzeugung von SSE2 Instruktionen ausschalte kommen dieselben Zeiten raus. Das ist komplett memory-bound. Schneller wird es nur, wenn ich die Benchmark-Schleife (die über die Iterationen läuft) mit parallel_for (aus ppl.h) laufen lasse. Aber das optimiert den Benchmark und nicht den gebenchmarkten Algorithmus. Ein parallel_for in add() bringt hingegen nichts.

knivil

parallel_for

Das ist komplett am Thema vorbei.

Wie soll man denn bei loop unrolling noch vernünftig debuggen?

Wenn du deinen Breakpoint setzt, dann siehst du fuer gewoehnlich nur den Cpp-Code. Bei Loopunrolling haettest du dann eben 3 Breakpoints im Asm-Code. Aber so genau habe ich das nicht analysiert. Es ist halt ein kleiner ... nicht aussagekraeftiger Benchmark, da wollte ich nicht zuviel Zeit investieren.