Frage zu SSE Optimierung

Hallo, ich habe vor Kurzem Assembly gelernt und wollte nun versuchen, ein vom Compiler erstelltes Programm per Hand nachzuoptimieren. Vorab: Als Compiler benutze ich Visual Studio 2012 (mit allen Optimierungen eingeschaltet), OS ist Windows 7 64bit, mein Prozessor ist ein Intel i5 M 520 mit 2.40GHz und das Programm ist eine 64bit Anwendung.
Im vom Compiler erstellten Code befinden sich in einer zeitkritischen Schleife zwei unaligned memory Zugriffe. Da ich sowohl im Intel Optimization Manual als auch in Agner Fogs Guide gelesen habe, man solle unaligned loads vermeiden, habe ich den Code ein wenig umgeschrieben, mit dem Ergebnis, dass er deutlich langsamer ist
Hier erstmal ein bisschen Code (der Code ist ein wenig vereinfacht)

;Compiler Output
test1 proc
Beginning:
	movupd	xmm1, [rdx+8]

	mov rax, rdx
	add rax, 32*100+16
	add rdx, 16
	add r8, 16
InnerLoop:					;zeitkritische Schleife
	movupd	xmm2, [rdx+8]	;unaligned load
	addpd	xmm1, xmm2

	movapd	xmm3, [rdx]		;aligned load
	addpd	xmm3, xmm1
	movapd	[r8], xmm3

	movupd	xmm1, [rdx+24]	;unaligned load
	addpd	xmm2, xmm1

	movapd	xmm4, [rdx+16]	;aligned load
	addpd	xmm4, xmm2
	movapd	[r8+16], xmm4

	add		r8,  32
	add		rdx, 32
	cmp		rdx, rax
	jne InnerLoop
	sub		r8, 32*100+16
	sub		rdx, 32*100+16
	sub		rcx, 1
	jnz Beginning
	ret
test1 endp

In dem Code gehe ich also ein Array ab und habe für jedes Element einen Memory Read (rdx, rdx+8, rdx+16, rdx+24). Meine Idee war also, die Memoryzugriffe auf rdx+8 und rdx+24 zu sparen (diese sind unaligned), und einfach die werte aus rdx und rdx+16 zusammen zu shuffeln:

test2 proc
Beginning:
	movupd	xmm1, [rdx+8]

	mov rax, rdx
	add rax, 32*100+16
	add rdx, 16
	add r8, 16
InnerLoop:
	;movupd	xmm2, [rdx+8]	;unaligned load sparen
	movapd	xmm4, [rdx+16]	;stattdessen aligned zugreifen
	movapd	xmm2, xmm3		;eine kopie von register zu register
	shufpd	xmm2, xmm4, 01b	;und ein shuffle
	addpd	xmm1, xmm2

	;movapd	xmm3, [rdx]		;der load fällt weg
	addpd	xmm3, xmm1
	movapd	[r8], xmm3

	;movupd	xmm1, [rdx+24]	;unaligned load
	movapd	xmm3, [rdx+32]	;wird oben als xmm3 wiederverwendet
	movapd	xmm1, xmm4		;hier wieder ein aligned load
	shufpd	xmm1, xmm3, 01b	;gegen eine Registerkopie und shuffle getauscht
	addpd	xmm2, xmm1

	;movapd	xmm4, [rdx+16]	;wurde schon oben geladen
	addpd	xmm4, xmm2
	movapd	[r8+16], xmm4

	add		r8,  32
	add		rdx, 32
	cmp		rdx, rax
	jne InnerLoop
	sub r8, 32*100+16
	sub rdx, 32*100+16
	sub rcx, 1

	jnz Beginning
	ret
test2 endp

Unterm Strich habe ich also in der Inneren Schleife 2 Unaligned Memory Zugriffe gegen 2 Registerkopien und 2 Shuffle's getauscht. Der zweite Code macht allerdings nicht exakt das Gleiche, da er auf ein Element mehr im Array zugreift, als der 1. Code. Aber das ist in meinem Fall nicht so schlimm. Gemessen habe ich so:

#include <iostream>
#include <ctime>
#include <cstddef>
int main()
{
	const size_t Messungen = 10;
	const size_t Laeufe = 100000000;
//Erstelle zwei Arrays mit einem extra Element hinten
	double* arr1 = (double*)_aligned_malloc(32*100+16+8, 16); // 16-byte aligned
	double* arr2 = (double*)_aligned_malloc(32*100+16+8, 16);
	size_t time1c=0, time1t=0, time2c=0, time2t=0;

	for(size_t i=0; i!=Messungen; ++i)
	{
		memset(arr1, 0, 32*100+16+8);
		time_t cs = std::time(NULL);  //Messe Wall-time
		size_t  ts = GetCPUTicks();   //Messe CPU Ticks
		test1(Laeufe, arr1, arr2);    //Version MIT unaligned Reads
		size_t  te = GetCPUTicks();
		time_t ce = std::time(NULL);

		time1c += (ce-cs);
		time1t += (te-ts);

		memset(arr1, 0, 32*100+16+8);
		cs = std::time(NULL);
		ts = GetCPUTicks();
		test2(Laeufe, arr1, arr2);   //Version ohne unaligned Reads
		te = GetCPUTicks();
		ce = std::time(NULL);

		time2c += (ce-cs);
		time2t += (te-ts);
	}
	cout<<"1: "<<time1c/(double)Messungen<<"\t"<<time1t/(double)Messungen<<endl<<"2: "<<time2c/(double)Messungen<<"\t"<<time2t/(double)Messungen<<endl;

Die Funktion GetCPUTicks sieht übrigen so aus:

GetCPUTicks proc
	push	rbx
	xor	rax,rax	;clearen für cpuid
	cpuid
	RDTSC		;schreibe ticks in edx:eax
	shl	rdx, 32	;füge edx:eax zu einem 64bit wert
	or	rax, rdx	;in rax zusammen
	pop	rbx		;rbx wiederherstellen
	RET
GetCPUTicks endp

Die Ergebnisse sind folgende:
Wenn ich nur einen Schleifenlauf messe und von sehr vielen Tests die minimale Tick-Zahl ermittle, dann braucht die Variante ohne unaligned memoryzugriffe ca. 10% Ticks mehr (ca. 500 vs. 550)
Wenn ich die Zeit von 100000000 Läufen messe, dann brauch die Version ohne unaligned memoryzugriffe fast 3 mal solange (21 sekunden vs 58 sekunden).

Wie kann es sein, dass die Version, in der ich einen unaligned memory read gegen eine Registerkopie und ein shuffle tausche, deutlich langsamer läuft?

knivil

Ohne es getest zu haben:
1.) mehr Instruktionen
2.) mehr Registerabhaengigkeiten

InnerLoop:                  
    movupd  xmm2, [rdx+8]

    addpd   xmm1, xmm2  ; unabhaengig, kann in einem Takt
    movapd  xmm3, [rdx] ; ausgefuehrt werden

    addpd   xmm3, xmm1

    movapd  [r8], xmm3      ; unabhaengig
    movupd  xmm1, [rdx+24]  ;

    addpd   xmm2, xmm1      ; unabhaengig
    movapd  xmm4, [rdx+16]  ;

    addpd   xmm4, xmm2
    movapd  [r8+16], xmm4

    add     r8,  32 ; unabhaengig
    add     rdx, 32 ; 

    cmp     rdx, rax
    jne InnerLoop

Das wuerde 8 Takte fuer Variante 1 bedeuten (keine Ahnung, wieviel die Befehle in echt jetzt verbraten. In Variante 2 gibt ee nur 2 Stellen, wo Anweisungen wegen Datenunabhaengigkeit parrall ausgefuehrt werden koennen. Das macht dann effektive 12 Anweisungen.

Könntest du mal erläutern, was die Schleife machen soll - sieht irgendwie nach horizontalen Additionen aus (-> SSE3). Eventuell könnte sich auch die skalaren Befehle (z.B. addsd) als Vorteilhaft erweisen.
Test mit hoher Wiederholungszahl sag nichts aus, da hier der kritische Speicherzugriff komplett ausgeblendet wird. Deutlich besser ist es den kompletten Algorithmus mit einem realen Datensatz zu testen.

Mein Prozessor unterstützt nur Instruktions bis SSE2. Ich kann ja mal den Originalcode posten. Das Programm macht Folgendes:

//Implementierung der finiten Differenzen Methode
//c2 und c3 sind einfach 2 Konstanten
void FDM(size_t n, double* alt, double *neu)
{
	for(std::size_t a=0; a!=n; ++a)
	{
		neu[0] = alt[1]*c3;						//Randbedingung

		for(std::size_t i=1; i!=998; ++i)		//Iteration
			neu[i] = 0.25*(alt[i-1] + alt[i+1]) + 0.5*alt[i];

		neu[998] = c2 + alt[997];				//Randbedingung

		double *tmp = alt;
		alt = neu;
		neu = tmp;
	}
}

Mit allen Optimierungen erzeugt mein Compiler daraus ungefähr folgenden Assembler Code (links).
Ich habe die beiden Codes jetzt mal nebeneinander geschrieben (ich hoffe, das macht die Unterschiede deutlicher). Die Zeilen, die nebeneinander stehen, sind komplett identisch. Bei Unterschieden habe ich Kommentare an die entsprechende Zeile geschrieben.
Der relevante Teil sind die Zeilen 40 bis 59, also die innere Schleife.

FDM_999_unaligned proc			FDM_aligned proc		
								;speichere callee-save register		
movapd reg6,  xmm6				movapd reg6,  xmm6		
movapd reg7,  xmm7				movapd reg7,  xmm7		
movapd reg12, xmm12				movapd reg12, xmm12		
movapd reg13, xmm13				movapd reg13, xmm13		
movapd reg14, xmm14				movapd reg14, xmm14		
								;konstanten aus Speicher laden		
movapd xmm5,  c2				movapd xmm5,  c2		
movapd xmm14, c3				movapd xmm14, c3		
movapd xmm13, half  			movapd xmm13, half ;xmm13 = 0.5  | 0.5		
movapd xmm12, quarter 			movapd xmm12, quarter ;xmm12 = 0.25 | 0.25		

mov rax, rdx					mov rax, rdx		
add rax, 7984					add rax, 7984 ; N*8-8, Anzahl Elemente im Array		

mov r9, rdx						mov r9, rdx		
mov r10, r8						mov r10, r8		

TimeLoop:						TimeLoop:			
movapd xmm0, [rdx]				movapd xmm0, [rdx]		
movupd xmm1, [rdx+8]			;unaligned load entfällt, dafür nächstes element laden, das aligned ist laden		
								movapd xmm3, [rdx+16]	;aligned load		
								movapd xmm1, xmm0	;Registerkopie		
								shufpd xmm1, xmm3, 01b	;Werte zusammenshuffeln		
movsd xmm7, xmm1				movsd xmm7, xmm1		
mulsd xmm7, xmm14				mulsd xmm7, xmm14		
movhlps xmm6, xmm1 				movhlps xmm6, xmm1 		
addsd xmm6, xmm0				addsd xmm6, xmm0		
mulsd xmm6, xmm12				mulsd xmm6, xmm12		
movsd xmm0, xmm1				movsd xmm0, xmm1		
mulsd xmm0, xmm13				mulsd xmm0, xmm13		
addsd xmm0, xmm6				addsd xmm0, xmm6		
movlhps xmm7, xmm0				movlhps xmm7, xmm0		
movapd xmmword ptr [r8], xmm7	movapd xmmword ptr [r8], xmm7		

add rdx, 16						add rdx, 16		
add r8,  16						add r8,  16		

InnerLoop:						InnerLoop:		
movupd xmm2, [rdx+8]			;unaligned load fällt weg		
movapd xmm4, [rdx+16]			movapd xmm4, [rdx+16]	;lade nächstes Element, das aligned ist		
								movapd xmm2, xmm3	;Registerkopie		
								shufpd xmm2, xmm4, 01b	;Werte zusammenshuffeln		
addpd xmm1, xmm2				addpd xmm1, xmm2		
mulpd xmm1, xmm12				mulpd xmm1, xmm12		
movapd xmm3, [rdx]				;wurde schon in der letzten Iteration geladen		
mulpd xmm3, xmm13				mulpd xmm3, xmm13		
addpd xmm3, xmm1				addpd xmm3, xmm1		
movapd [r8], xmm3				movapd [r8], xmm3		
movupd xmm1, [rdx+24]			;unaligned load fällt weg		
								movapd xmm3, [rdx+32]	;lade nächstes aligned element		
								movapd xmm1, xmm4	;Registerkopie		
								shufpd xmm1, xmm3, 01b	;werte zusammenshuffeln		
addpd xmm2, xmm1				addpd xmm2, xmm1		
mulpd xmm2, xmm12				mulpd xmm2, xmm12		
mulpd xmm4, xmm13				mulpd xmm4, xmm13		
addpd xmm4, xmm2				addpd xmm4, xmm2		
movapd [r8+16], xmm4				movapd [r8+16], xmm4		
add r8,  32						add r8,  32		
add rdx, 32						add rdx, 32		
cmp rdx, rax					cmp rdx, rax		
jne InnerLoop					jne InnerLoop		

								;berechne rechten Randpunkt neu[N-1]		
movsd xmm6, xmm1				movsd xmm6, xmm1		
addsd xmm6, xmm5				addsd xmm6, xmm5		
movsd qword ptr [r8], xmm6		movsd qword ptr [r8], xmm6		

;swap pointers					;swap pointers		
xchg r9,r10						xchg r9,r10		
mov rdx, r9						mov rdx, r9		
mov r8,r10						mov r8,r10		
mov rax, rdx					mov rax, rdx		
add rax, 7984					add rax, 7984		

sub  rcx, 1						sub  rcx, 1		
jnz TimeLoop					jnz TimeLoop		

								;callee-save register wieder laden		
movapd xmm6,  reg6				movapd xmm6,  reg6		
movapd xmm7,  reg7				movapd xmm7,  reg7		
movapd xmm12, reg12				movapd xmm12, reg12		
movapd xmm13, reg13				movapd xmm13, reg13		
movapd xmm14, reg14				movapd xmm14, reg14		

RET								RET		
FDM_unaligned endp				FDM_aligned endp

Falls das zu unüberischtlich ist, dann stehen die beiden Codes hier nochmal einzeln:
unaligned Version: http://pastebin.com/e9HKxeud
aligned Version: http://pastebin.com/kPFXVJ6n
Messungen der beiden Codes ergeben:
Code mit unaligned loads: 41 Sekunden
Code ohne unaligned loads: 31 Sekunden
Wenn ich wieder die minimale Tick-Zahl für einen Durchlauf messe, erhalte ich:
Code mit unaligned loads: 950 Ticks
Code ohne unaligned loads: 1100 Ticks

Mich wundert halt nur, warum der Code, der die hälfte aller Memoryready weglässt, am Ende der langsamere ist. Liegt das wirklich daran, dass die unaligned Version bessere Out-of-Order Execution ermöglicht?

camper

SSEOptimierung schrieb:

Mein Prozessor unterstützt nur Instruktions bis SSE2.

Dann handelt es sich um einen alten Athlon 64?
In dem Falle dürfte SHUFPD genauso schlecht wie MOVUPD sein, beides sind dort VectorPath-Instruktionen.
Wie ist es, wenn du das MOVUPD jeweils durch ein MOVHPD/MOVLPD-Paar ersetzt? Die Latenz der Speicherzugriffe als solche dürfte bei dieser Art Schleife irrelevant sein (im Zweifel rollt man noch etwas mehr auf), da die Ladevorgänge problemlos recht weit von ihren Konsumenten entfernt plaziert werden könen.
Die Reihenfolge der MULPD-Instruktionen sieht ungünstig aus, allerdings wird der Prozessors das von sich aus korrigieren.

Danke für deine Erklärungen, Camper!

camper schrieb:

SSEOptimierung schrieb:

Mein Prozessor unterstützt nur Instruktions bis SSE2.

Dann handelt es sich um einen alten Athlon 64?

Du hast natürlich vollkommen recht. Meine CPU Unterstützt alle Instruktionen bis inklusive SSE4.2, ich habe Mist erzählt

camper schrieb:

In dem Falle dürfte SHUFPD genauso schlecht wie MOVUPD sein, beides sind dort VectorPath-Instruktionen.

Meine Überlegung war, dass das MOVUP ja auf Speicher zugreifen muss, während SHUFPD nur mit zwei Registern arbeitet. Dadurch dachte ich, dass SHUFPD schneller sein muss.

camper schrieb:

Die Latenz der Speicherzugriffe als solche dürfte bei dieser Art Schleife irrelevant sein

Das war mir nicht bewusst. Ich dachte immer, man sollte alle Speicherzugriffe möglichst vermeiden.

camper schrieb:

Wie ist es, wenn du das MOVUPD jeweils durch ein MOVHPD/MOVLPD-Paar ersetzt?

Damit erhalte ich ziemlich genau die gleiche Performance, wie mit dem ersten, unaligned Code

camper schrieb:

Die Reihenfolge der MULPD-Instruktionen sieht ungünstig aus, allerdings wird der Prozessors das von sich aus korrigieren.

Ja, habe ich auch gedacht. Erst habe ich die Instruktionen umsortiert, mit dem Effekt, dass sich Performancetechnisch nichts verändert hat. Dann hab ich es so gelassen, wie es in der "Programmlogik" ist.

Dann ist es also wirklich so, dass die Latenz der Speicherzugriffe komplett von der Out-of-Order Execution überdeckt werden kann, während sich das SHUFPD in eine Dependancy Chain einreihen muss?

dot

An deiner Stelle würd ich mir überlegen, ob es nicht sinnvoller wäre, durch SSE vier Iterationen der Schleife parallel auszuführen, statt eine einzelne Iteration mit komplizierten horizontalen Operationen zu bearbeiten. Ich könnte mir vorstellen, dass das wesentlich schneller wäre und wundere mich ehrlich gesagt ein wenig, dass dein Compiler das nicht sowieso von selber schon so macht...

Ich weiß nicht ganz, was du damit meinst. Der Compiler bastelt effektiv das her:

//obvious code
for(std::size_t i=1; i!=998; ++i)
    neu[i] = 0.25*(alt[i-1] + alt[i+1]) + 0.5*alt[i];

//compiler generated code
for(std::size_t i=1; i!=998; i+=2)
{
    neu[i]   = 0.25*(alt[i-1] + alt[i+1]) + 0.5*alt[i];   //natürlich parallel in
    neu[i+1] = 0.25*(alt[i]   + alt[i+2]) + 0.5*alt[i+1]; //xmm registern
}

Was meinst du genau mit vier iterationen parallel ausführen? Meinst du das ganze mit single precision umzusetzen? Denn für genügend Genauigkeit brauche ich in dem Algorithmus double precision.

dot

Ah, genau das meinte ich...

camper

for(std::size_t i=1; i!=998; ++i)       //Iteration
            neu[i] = 0.25*(alt[i-1] + alt[i+1]) + 0.5*alt[i];

Das fängt allerdings schon nicht ganz optimal an.

for(std::size_t i=1; i!=998; ++i)
    neu[i] = 0.25*((alt[i-1]+alt[i]) + (alt[i]+alt[i+1]));

sieht besser aus (-1 Multiplikation und der rechte SUmmand kommt bei der nächsten Iteration wieder. Allerdings brauchen wir jetzt horizontales add.

Ohne direkte horizontale Summen:

for(std::size_t i=2; i!=997; ++i)
    neu[i]   = 0.25*((alt[i-2]+alt[i+0]) + (alt[i-1]+alt[i+1]) + (alt[i+0]+alt[i+2]) - (alt[i-2]+alt[i+2]));

(durchschnittlich 4 Additionen pro Element), dürfte schlechter sein.

Oh, das hatte ich garnicht gesehen. Danke für den Tipp! Ich werde das heute Abend mal umsetzen und nachmessen.

Allerdings habe ich noch keine endgültige Erklärung, warum der Code mit halber Anzahl Memoryreads langsamer ist