C++: Schleifenoptimierung - Array Reduction

[Gast]

Hi,

ich habe folgendes Problem: Ich gehe durch 2 Arrays von Daten, Elemente sind ein Skalar und ein 6-Vektor. Ich multipliziere Vektor*Skalar und möchte das Ergebnis über das gesamte Array in einer Variable aufsummieren, also eine Art Reduction. Das ganze ist performancekritisch und ich möchte es optimieren.


Vector6f Jtr;
__m128 r1 = _mm_set1_ps(0);
__m128 r2 = _mm_set1_ps(0);
for (; it_point < end; it_point++, it_jacobian++, it_residual++)
{
//float residual = *it_residual;
__m128 res1 = _mm_load1_ps(&(*it_residual));
__m128 j11 = _mm_load_ps(it_jacobian->data);
__m128 j12 = _mm_load_ps((it_jacobian->data+4));

r1 = _mm_add_ps(r1, _mm_mul_ps(-res1, j11));
r2 = _mm_add_ps(r2, _mm_mul_ps(-res1, j12));
//energy += residual*residual;
}
_mm_store_ps(Jtr.data(), r1);
_mm_storel_pi((__m64*)(Jtr.data()+4), r2);


Mir scheint es sehr langsam zu laufen, die Arraygröße beträgt ~300.000 und es sind in jeder Schleifeniteration 6 Multiplikationen und 6 Additionen, also eigentlich keine große Geschichte.

Ich vermute es hat mit der Struktur r1=r1+bla zu tun, welche wohl nicht optimale Speicher/Cachezugriffe produziert (Bleibt r1 zwischen Schleifeniterationen im Cache? Wird jedesmal gewartet bis in den Speicher geshrieben/gelesen wird?). Folgender Code läuft um Größenordnungen schneller:

for (; it_point < end; it_point++, it_jacobian++, it_residual++)
{
//float residual = *it_residual;
__m128 res1 = _mm_load1_ps(&(*it_residual));
__m128 j11 = _mm_load_ps(it_jacobian->data);
__m128 j12 = _mm_load_ps((it_jacobian->data+4));

volatile __m128 temp1 = _mm_add_ps(r1, _mm_mul_ps(-res1, j11));
volatile __m128 temp2 = _mm_add_ps(r2, _mm_mul_ps(-res1, j12));

//energy += residual*residual;
}

volatile müsste soweit ich weiß verhindern dass der Compiler die multiplikationen und additionen wegoptimiert.

Ich habe bereits ein manuelles loop unrolling versucht (pro Schleifeniteration um 4 elemente weiter, 4-fache Arbeit in einer Iteration) und das bringt bereits ~15% mehr Geschwindigkeit. Unterstützt die Theorie dass es an der Struktur r1=r1+bla liegt. Nur wird der Code dadurch nicht eben schöner und ich wäre an einer grundsätzlichen Lösung interessiert.

Ideen?

[Exxtreme]

Ich habe bereits ein manuelles loop unrolling versucht (pro Schleifeniteration um 4 elemente weiter, 4-fache Arbeit in einer Iteration) und das bringt bereits ~15% mehr Geschwindigkeit. Unterstützt die Theorie dass es an der Struktur r1=r1+bla liegt. Nur wird der Code dadurch nicht eben schöner und ich wäre an einer grundsätzlichen Lösung interessiert.

Ideen?
Wenn es vermutlich daran liegt dann kann man den Compiler bestimmt so einstellen, dass er loop unwindig macht, oder?

[del_4901]

Ideen?
Was sagt der Profiler?

[Gast]

Wenn es vermutlich daran liegt dann kann man den Compiler bestimmt so einstellen, dass er loop unwindig macht, oder?
Ich kenne beim gcc nur die Möglichkeit loop unrolling global einzustellen. Ich möchte es nicht global haben, wie es nur für einzelne Schleifen geht weiß ich nicht. Ein test mit -funroll-loops hat nichts gebracht.
Was sagt der Profiler?
Ich habe leider keine Erfahrung mit Profilern unter Linux, hast du da einen Tip? Welche Informationen erhoffst du dir dadurch? Ich habe einige Beobachtungen über Zeitmessung direkt im Code (Ich verwende cuda events welche auf einem timer direkt in GPU hardware basieren und eine wesentlich höhere Auflösung als der übliche CPU-Timer haben: http://docs.nvidia.com/cuda/cuda-runtime-api/group__CUDART__EVENT.html#group__CUDART__EVENT_1g14c387cc57ce2e328f6669854e6020a 5 )
*) Native Implementierung ohne SSE ist wesentlich langsamer
*) Pro Iteration 4 Elemente lokal aufaddieren aber nur einmal r1=r1+bla bringt merkbar (also deutlich mehr als Mess- bzw. statistische Ungenauigkeit) Geschwindigkeit.

Ich würde gerne mehr Einblick in das Problem dahinter gewinnen. Kann da ein profiler helfen? Soweit ich weiß sagt mir der auch nur wieviel Zeit in welchem Teil des Codes verbracht wird, also dasselbe was ich jetzt über Messung mit Timern auch habe.

[del_4901]

Ich würde gerne mehr Einblick in das Problem dahinter gewinnen. Kann da ein profiler helfen? Soweit ich weiß sagt mir der auch nur wieviel Zeit in welchem Teil des Codes verbracht wird, also dasselbe was ich jetzt über Messung mit Timern auch habe.
Ein profiler gibt dir weitaus mehr Informationen als nur die Zeit. Die Hardware hat unzaehlige HW Counter die dir genau sagen koennen wo was klemmt.

http://software.intel.com/en-us/intel-vtune-amplifier-xe

[Gast]

Ein profiler gibt dir weitaus mehr Informationen als nur die Zeit. Die Hardware hat unzaehlige HW Counter die dir genau sagen koennen wo was klemmt.

http://software.intel.com/en-us/intel-vtune-amplifier-xe
Ich muss schauen was ich da passendes finde, im Moment ist der VTune Amplifier keine Option. Gibt es noch andere profiler, vorzugsweise freie?

[mksn7]

Mach doch mal ein bisschen performance modelling. Es gibt typischerweise zwei kenngrößen, die du dir ausrechnen kannst, Flops und Bandbreite.

Die Flops vergleichst du mit der Single core single precision deines Prozessors, die du dir leicht ausrechnen kannst.

Deine 300000 *6*4= ~7Mbyte passen schonmal in keinen L2 cache, du könntest sie also direkt mit der STREAM bandbreite deines Prozessors vergleichen, die du online findest.

Wenn du eine der beiden Größen annäherend erreichst, dann kannst du erstmal aufhören, mehr ist in der Hardware nicht drin. Wenn du keine der beiden Größen erreichst, dann ist beim instruction througput noch was zu holen. Übliche, gute Compiler holen bei solchen Sachen schon echt viel raus, inklusive prefetching und unrolling. Gib doich mal ein paar mehr details her, wie genau Ausführungszeit, compiler, prozessor...


Edit: Performance counter unter Linux kann man mit likwid oder perf auslesen. Aber es dürfte so schon klar sein, dass da keine großen cachehits drin sein werden.

[Odal]

und wieso packst du nicht mal deine Laufzeitkritischen Schleifenberechnungen in eine extra klasse und baust die mit loop unrolling?

[mksn7]

Assemblercode dumpen lassen mit -S ist auch oft sehr instruktiv. Da sieht man dann auch, ob loop unrolling tatsächlich gemacht wurde.

[Marscel]

volatile müsste soweit ich weiß verhindern dass der Compiler die multiplikationen und additionen wegoptimiert.

volatile soll eigentlich sicher stellen, dass Kram nicht im Register gehalten und damit ungültig wird, weil z.B. ein anderer Thread damit arbeitet, sondern immer frisch aus dem Speicher ausgelesen wird. Und dass es da Größenordnungen schneller sein sollte, liegt vermutlich daran, dass die Add-Mul-Operationen hier komplett fehlen, weil droppable. Wie schon erwähnt, sinnvoll wäre es, wenn du dir mit -S mal das Assembly ausgeben lässt.

Sonst mal gperf oder ähnliches und, wenn Linux, Cachegrind rüberlaufen lassen. Wir sehen den Kontext ja nun nicht, aber vielleicht hilft hier auch etwas Cache-Prefetching.

[Coda]

Loop Unrolling ist bei so kleinen Schleifen schon länger kontraproduktiv.

[Gast]

Mach doch mal ein bisschen performance modelling. Es gibt typischerweise zwei kenngrößen, die du dir ausrechnen kannst, Flops und Bandbreite.

Die Flops vergleichst du mit der Single core single precision deines Prozessors, die du dir leicht ausrechnen kannst.

Deine 300000 *6*4= ~7Mbyte passen schonmal in keinen L2 cache, du könntest sie also direkt mit der STREAM bandbreite deines Prozessors vergleichen, die du online findest.

Wenn du eine der beiden Größen annäherend erreichst, dann kannst du erstmal aufhören, mehr ist in der Hardware nicht drin. Wenn du keine der beiden Größen erreichst, dann ist beim instruction througput noch was zu holen. Übliche, gute Compiler holen bei solchen Sachen schon echt viel raus, inklusive prefetching und unrolling. Gib doich mal ein paar mehr details her, wie genau Ausführungszeit, compiler, prozessor...

Ich habe einen core i7 960 mit 3.2GHz. Der hat eine Single Core FLOP-Leistung von 3.2*4=12.8GFLOP/s (4 Instructions pro Cycle mit SSE, was ich ja verwende) und eine Bandbreite von 19.2GB/s http://de.wikipedia.org/wiki/Liste_der_Intel-Core-i-Prozessoren#Core_i7

Ich habe pro Iteration zwei SSE mul und zwei SSE add = 4*4=16 Instructions -> Insgesamt 300.000*16=4.8MFLOP=0.0048GFLOP. Das ergibt eine theoretische Zeit von 0.0048GFLOP/(12.8GFLOP/s)=0.375ms.

Weiters werden pro Iteration 9 floats geladen -> Insgesamt 300000*9*4=10.3MB=0.01GB. Das ergibt theoretisch 0.01GB/(19.2GB/s)=0.524ms

Ich erreiche eine Ausführungszeit von ~9ms. Das entspricht 0.53GFLOP/s bzw. 1.12GB/s, also weit vom theoretischen Peak entfernt.

Die Arrays liegen streng linear im Speicher, beim Laden sollte also der Cache optimal arbeiten können. Selbst wenn man annimmt dass in der Praxis die Leistung halb so gut wie oben errechnete Werte ist, dann ist man bei ~1ms, also noch immer deutlich schneller.

Was ich nicht berücksichtigt habe ist dass in jeder Iteration das Ergebnis wieder auf r1/r2 zurückgeschrieben wird. Also zusätzliche Speicherzugriffe. Das ist schlecht, weil lt. obiger Rechnung die Bandbreite ohnehin der limitierende Faktor ist.

Kompiliert wird mit gcc -O3 -march=corei7 -msse4.2.


volatile soll eigentlich sicher stellen, dass Kram nicht im Register gehalten und damit ungültig wird, weil z.B. ein anderer Thread damit arbeitet, sondern immer frisch aus dem Speicher ausgelesen wird. Und dass es da Größenordnungen schneller sein sollte, liegt vermutlich daran, dass die Add-Mul-Operationen hier komplett fehlen, weil droppable. Wie schon erwähnt, sinnvoll wäre es, wenn du dir mit -S mal das Assembly ausgeben lässt.

volatile verhindert außerdem dass der Comipler eine Menge Optimierungen mit der Variable anstellt, eben aus genau dem Grund den du beschrieben hast. In diesem Fall soll es verhindern dass der Compiler die Temporary auf die ich das Ergbnis zuweise wegoptimiert.
Das scheint auch korrekt zu funktionieren, ich habe den assembly output verglichen, mit volatile werden die mul und add nicht gedroppt, ich sehe die entsprechenden mulps und addps. Der Code ist wie gesagt wesentlich schneller (~1.5ms), was eigentlich nur bedeuten kann dass der Unterschied in der Zuweisung liegt (einmal in r1/r2, einmal in den volatile temporary)


Loop Unrolling ist bei so kleinen Schleifen schon länger kontraproduktiv.
Kannst du das erklären? Ich war der Meinung dass es bei großen Schleifen kontraproduktiv ist, bei kleinen (Größenordnung <100 Iterationen) kann es schon was bringen. Ich habe hier ja 300.000 Iterationen.

[del_4901]

Ich muss schauen was ich da passendes finde, im Moment ist der VTune Amplifier keine Option. Gibt es noch andere profiler, vorzugsweise freie?
30 Tage Testversion? Ansonsten frag einfach bei dem Intel Mann deines Vertrauens nach. Ich hab so meine verguenstigte Lizens bekommen.

[Gast]

30 Tage Testversion? Ansonsten frag einfach bei dem Intel Mann deines Vertrauens nach. Ich hab so meine verguenstigte Lizens bekommen.
Die habe ich soeben istalliert? Was mache ich jetzt damit? Bzw. welche Kenngrößen möchtest du wissen? Ich habe es einmal durchlaufen lassen, Ich weiß jetzt, dass diese Schleife unverhältnismäßig viel Zeit benötigt, das habe ich vorher auch schon gewußt ;)
Kenne mich mit diesem Programm leider noch nicht gut aus, hast du vielleicht Tips auf was man achten muss oder wie man das profilen am besten angeht? Gerne auch ein Dokument oder Link?

[del_4901]

Die habe ich soeben istalliert? Was mache ich jetzt damit? Bzw. welche Kenngrößen möchtest du wissen? Ich habe es einmal durchlaufen lassen, Ich weiß jetzt, dass diese Schleife unverhältnismäßig viel Zeit benötigt, das habe ich vorher auch schon gewußt ;)
Kenne mich mit diesem Programm leider noch nicht gut aus, hast du vielleicht Tips auf was man achten muss oder wie man das profilen am besten angeht? Gerne auch ein Dokument oder Link?
Cache misses etc.? Mach mal nen screenshoot von Advanced Analysis und dem ASM.
http://software.intel.com/sites/products/collateral/hpc/vtune/performance_analysis_guide.pdf

Ich habe ja den Iterator im Verdacht.

Wenn du (intel) AVX verwenden darfst, dann hast du dort ein MADD(FMA) und ausserdem ist es auch freundlicher fuer den decoder.

[Gast]

Danke für den Link, werde das mal durchaschauen. Geht schon richtig tief zur Sache was ich so beim drüberfliegen gesehen hab, könnte ein bisschen dauern bis ich das alles intus hab :)

Die Advanced Hotspot Analysis sagt mir ich habe eine zu schlechte CPI, was ja nun auf ein Cache/Speicherproblem hindeutet wie ich es vermutet habe. Es tritt genau in dem geposteten Code Teil auf.

Was meinst du mit du hast den iterator im Verdacht? Das inkremetieren der iteratoren in jedem Schleifendurchgang?

Hier ist der Screenshot mit Assembly:
http://abload.de/thumb/screenshot4qtuvz.png (http://abload.de/image.php?img=screenshot4qtuvz.png)

Hier dasselbe mit volatile temps (Ergibt keine CPI Probleme, mulps und sub):
http://abload.de/thumb/screenshot35kuhe.png (http://abload.de/image.php?img=screenshot35kuhe.png)

Ein schneller Test ohne volatile ergibt dass die komplette Schleife wegoptimiert wird.

[del_4901]

Die Advanced Hotspot Analysis sagt mir ich habe eine zu schlechte CPI, was ja nun auf ein Cache/Speicherproblem hindeutet wie ich es vermutet habe. Es tritt genau in dem geposteten Code Teil auf.

Was meinst du mit du hast den iterator im Verdacht? Das inkremetieren der iteratoren in jedem Schleifendurchgang?

Kannst du die anderen Counter mal mit anzeigen? Irgendwas ist mit it_residual fishy, vllt. ein Problem mit Store-forwarding. Was macht der itterator intern?

[Gast]

Welche anderen Counter meinst du?

it_residual ist ein normaler std::vector<>::iterator, was der intern genau macht weiß ich nicht:

typedef std::vector<float> PixelVector;
PixelVector::iterator it_residual = <blub>


Es könnte ein load-hit-store issue sein, ja. Nur wie kann ich das beheben?

[del_4901]

Welche anderen Counter meinst du?

it_residual ist ein normaler std::vector<>::iterator, was der intern genau macht weiß ich nicht:

typedef std::vector<float> PixelVector;
PixelVector::iterator it_residual = <blub>


Es könnte ein load-hit-store issue sein, ja. Nur wie kann ich das beheben?

LHS auf nem i7 ist sehr sehr selten. Aber ich wuerde mal versuchen den itterator wegzuschmeissen und anstelle mit pointern arbeiten.
1) r1 und r2 sind normale xmm register oder sind die irgendwie komisch definiert?
2) Und was ich mich auch grad frage wo wird den bitteschoen xmm2 geladen? Hast du vllt. undefined behaviour (nicht initialisierte Variable) in deinem code? r1 und r2 waehren Kandidaten. Dann macht der Compiler naemlich was er will.
3) Die indirection in it_jacobian->data koennte auch cache unfreundlich sein.

[Gast]

LHS auf nem i7 ist sehr sehr selten. Aber ich wuerde mal versuchen den itterator wegzuschmeissen und anstelle mit pointern arbeiten.
1) r1 und r2 sind normale xmm register oder sind die irgendwie komisch definiert?

Ja, normale __m128. Die werden direkt vor der Schleife definiert (s. 1. Beitrag, in dem Screenshot sieht mans nur nicht weil noch anderer Code dazwischen ist.

2) Und was ich mich auch grad frage wo wird den bitteschoen xmm2 geladen? Hast du vllt. undefined behaviour (nicht initialisierte Variable) in deinem code? r1 und r2 waehren Kandidaten. Dann macht der Compiler naemlich was er will.

Wird soweit ich das verstehe in Block2 geladen. Block 2 springt zu Block8, dort werden xmm1 und xmm2 mit 0 initialisiert.

3) Die indirection in it_jacobian->data koennte auch cache unfreundlich sein.
Ist nur zwecks Lesbarkeit, ich könnte auch &(*it_jacobian) laden. Die Datenstruktur ist sehr einfach aufgebaut (std::vector, Elemente sind struct {float data[6]; }), daran liegt es mit ziemlicher Sicherheit nicht.

Ich vermute nach wie vor dass es mit der Struktur r1=r1+bla in jeder Iteration zusammenhängt. Wenn r1 im Cache bleibt zwischen den Iterationen passt alles, aber wenn jedesmal ins RAM geschrieben und wieder gelesen wird ist es klar dass es langsam ist... würde auch erklären warum es mit volatile temps (mulps und addps werden nicht wegoptimiert!) so viel schneller ist.

[Gast]

p.s: Pointer statt iterator ändert nichts.

[Marscel]

Ich vermute nach wie vor dass es mit der Struktur r1=r1+bla in jeder Iteration zusammenhängt. Wenn r1 im Cache bleibt zwischen den Iterationen passt alles, aber wenn jedesmal ins RAM geschrieben und wieder gelesen wird ist es klar dass es langsam ist... würde auch erklären warum es mit volatile temps (mulps und addps werden nicht wegoptimiert!) so viel schneller ist.

Im nicht volatile-Fall. r1: xmm1, r2: xmm2. Die werden im Schleifenkörper (Block 5) weder reingeladen noch zurückgeschrieben, schneller gehts kaum.

Mir sieht das eher etwas nach Pipeline-Stalling/Flushes aus.

[del_4901]

Wird soweit ich das verstehe in Block2 geladen. Block 2 springt zu Block8, dort werden xmm1 und xmm2 mit 0 initialisiert.
Und wo wird dann j11 und j12 geladen?

[Marscel]

Und wo wird dann j11 und j12 geladen?

[RDX] und [RDX+10h] liegen da doch nahe.

[del_4901]

[RDX] und [RDX+10h] liegen da doch nahe.
Stimmt, die intel notation mit Dest hinten bringt mich jedesmal wieder durcheinander

[Gast]

Im nicht volatile-Fall. r1: xmm1, r2: xmm2. Die werden im Schleifenkörper (Block 5) weder reingeladen noch zurückgeschrieben, schneller gehts kaum.

Mir sieht das eher etwas nach Pipeline-Stalling/Flushes aus.
Ja das kann auch sein...

Ein bisschen weiteres profilen hat das hier ergeben:
http://abload.de/thumb/screenshot5ryyx4.png (http://abload.de/image.php?img=screenshot5ryyx4.png)

Was bedeutet das? Wie kann ich das beheben?

Bzw. seht ihr einen offensichtlichen Grund warum die Version mit volatile temps soviel schneller ist als die andere? Müsste sich ja am assembly code festmachen lassen.

[Marscel]

Bzw. seht ihr einen offensichtlichen Grund warum die Version mit volatile temps soviel schneller ist als die andere? Müsste sich ja am assembly code festmachen lassen.

Ja, Pipeline-Stalls. Zugegeben, ich weiß nicht, wie lang die bei x86/CISC in der Praxis ist, aber:

movssl (%rax), %xmm3
add $0x4, %rax

Ist möglicherweise Write-After-Read. Der Add-Befehl könnte schneller dran sein, als das Lesen des ursprünglichen Wertes aus RAX. Hingegen hat:

movssl (%rax), %xmm0
xorps %xmm3, %xmm3
xorps %xmm6, %xmm6
movaps (%rdx), %xmm2
add $0x4, %rax

wohl genügend voneinander unabhängige Instruktionen in Reihe, wo nichts warten oder geflusht werden muss. Das lassen jedenfalls die Ausführungszeiten vermuten.

[Coda]

WAR hazards sind irrelevant in einer Out-Of-Order-Architektur mit register renaming.

[del_4901]

In dem Fall sollte Loop unrolling doch ordentlich was bringen, breitere Register mit AVX auch.

WAR hazards sind irrelevant in einer Out-Of-Order-Architektur mit register renaming.
Kommt drauf an, da war doch was mit unterschiedlichen registergroessen, wo nicht renamed werden kann.

[Coda]

Ja, zu Pentium-III-Zeiten. Bei den neuen Intel ist das auch kein Problem mehr iirc. Aber bei sowas wie Jaguar vielleicht noch.

[Gast]

In dem Fall sollte Loop unrolling doch ordentlich was bringen, breitere Register mit AVX auch.

Ja, ich schrieb ja bereits am Anfang, wenn ich pro Iteration 4 Elemente weitergehe, diese lokal aufsummiere und das Ergebnis auf r1/r2 addiere (einmal r1=r1+bla stat viermal), dann ist es messbar schneller. Nur wird der Code dadurch grauenvoll:

for (; it_point < end; it_point+=4, it_jacobian+=4, it_residual+=4)
{
__m128 res1 = _mm_load1_ps(&(*it_residual));
__m128 j11 = _mm_load_ps(it_jacobian->data);
__m128 j12 = _mm_load_ps((it_jacobian->data+4));

__m128 res2 = _mm_load1_ps(&(*(it_residual+1)));
__m128 j21 = _mm_load_ps((it_jacobian+1)->data);
__m128 j22 = _mm_load_ps(((it_jacobian+1)->data+4));

__m128 res3 = _mm_load1_ps(&(*(it_residual+2)));
__m128 j31 = _mm_load_ps((it_jacobian+2)->data);
__m128 j32 = _mm_load_ps(((it_jacobian+2)->data+4));

__m128 res4 = _mm_load1_ps(&(*(it_residual+3)));
__m128 j41 = _mm_load_ps((it_jacobian+3)->data);
__m128 j42 = _mm_load_ps(((it_jacobian+3)->data+4));

r1 = _mm_add_ps(r1,
_mm_add_ps(
_mm_add_ps(
_mm_mul_ps(-res1, j11), _mm_mul_ps(-res2, j21)),
_mm_add_ps(
_mm_mul_ps(-res3, j31), _mm_mul_ps(-res4, j41)))
);

r2 = _mm_add_ps(r2,
_mm_add_ps(
_mm_add_ps(
_mm_mul_ps(-res1, j12), _mm_mul_ps(-res2, j22)),
_mm_add_ps(
_mm_mul_ps(-res3, j32), _mm_mul_ps(-res4, j42)))
);

}

Deshalb bin ich an einer mehr grundsätzlichen Lösung interessiert. AVX kann die CPU nicht.

Ich verstehe auch noch nicht ganz wo das Problem liegt, wär super wenn sich jemand die Zeit nimmt mir das zu erklären :)
Danke

[del_4901]

Ja, ich schrieb ja bereits am Anfang, wenn ich pro Iteration 4 Elemente weitergehe, diese lokal aufsummiere und das Ergebnis auf r1/r2 addiere (einmal r1=r1+bla stat viermal), dann ist es messbar schneller. Nur wird der Code dadurch grauenvoll:

for (; it_point < end; it_point+=4, it_jacobian+=4, it_residual+=4)
{
__m128 res1 = _mm_load1_ps(&(*it_residual));
__m128 j11 = _mm_load_ps(it_jacobian->data);
__m128 j12 = _mm_load_ps((it_jacobian->data+4));

__m128 res2 = _mm_load1_ps(&(*(it_residual+1)));
__m128 j21 = _mm_load_ps((it_jacobian+1)->data);
__m128 j22 = _mm_load_ps(((it_jacobian+1)->data+4));

__m128 res3 = _mm_load1_ps(&(*(it_residual+2)));
__m128 j31 = _mm_load_ps((it_jacobian+2)->data);
__m128 j32 = _mm_load_ps(((it_jacobian+2)->data+4));

__m128 res4 = _mm_load1_ps(&(*(it_residual+3)));
__m128 j41 = _mm_load_ps((it_jacobian+3)->data);
__m128 j42 = _mm_load_ps(((it_jacobian+3)->data+4));

r1 = _mm_add_ps(r1,
_mm_add_ps(
_mm_add_ps(
_mm_mul_ps(-res1, j11), _mm_mul_ps(-res2, j21)),
_mm_add_ps(
_mm_mul_ps(-res3, j31), _mm_mul_ps(-res4, j41)))
);

r2 = _mm_add_ps(r2,
_mm_add_ps(
_mm_add_ps(
_mm_mul_ps(-res1, j12), _mm_mul_ps(-res2, j22)),
_mm_add_ps(
_mm_mul_ps(-res3, j32), _mm_mul_ps(-res4, j42)))
);

}

Deshalb bin ich an einer mehr grundsätzlichen Lösung interessiert. AVX kann die CPU nicht.

Ich verstehe auch noch nicht ganz wo das Problem liegt, wär super wenn sich jemand die Zeit nimmt mir das zu erklären :)
Danke

nimm mal anstatt 4x _mm_load1_ps 1x _mm_load_ps und shifte die werte entsprechend. Unaligned loads sind nicht gerade eine staerke von SSE. Und wenn du gleich dabei bist sorge dafuer das die source daten 16byte aligned sind.

Und ja, optimierter code ist selten schoen.

[Gast]

nimm mal anstatt 4x _mm_load1_ps 1x _mm_load_ps und shifte die werte entsprechend. Unaligned loads sind nicht gerade eine staerke von SSE. Und wenn du gleich dabei bist sorge dafuer das die source daten 16byte aligned sind.

Ich brauche aber an allen 4 elementen des __m128 den gleichen Wert (Ich will Skalar*Vector6f berechnen). _mm_load1_ps macht einen broadcast von einem einzelnen float auf alle 4 elemente, ich wüsste nicht wie ich das mit shift machen kann.

Um die unaligend loads zu vermieden kann ich mir nur folgendes vorstellen:

__m128 res1 = _mm_load_ps(&(*it_residual)); // load data[x], data[x+1], data[x+2], data[x+3]
__m128 res2 = res1; __m128 res3 = res1; __m128 res4=res1;
_MM_TRANSPOSE4_PS(res1, res2, res3, res4); // AoS -> SoA

aber ich glaube nicht dass das schneller ist.

Daten sind alle 16byte aligned, ja (sonst würde es bei den SSE-loads krachen).

Und ja, optimierter code ist selten schoen.
:(

[del_4901]

aber ich glaube nicht dass das schneller ist.

Probiern und messen.

[Gast]

Ich werds morgen probieren.
Es ändert vielleicht ein bisschen, aber das grundsätzliche Problem bleibt bestehen, die Version mit volatile temps verwendet genauso _mm_load1_ps und ist trotzdem 10 mal so schnell.

[del_4901]

__m128 res1 = _mm_load_ps(&(*it_residual)); // load data[x], data[x+1], data[x+2], data[x+3]
__m128 res2 = res1; __m128 res3 = res1; __m128 res4=res1;
_MM_TRANSPOSE4_PS(res1, res2, res3, res4); // AoS -> SoA


__m128 res = _mm_load_ps(&(*it_residual)); // load data[x], data[x+1], data[x+2], data[x+3]
__m128 res1 = _mm_shuffle_ps(res, res, _MM_SHUFFLE(0, 0, 0, 0));
__m128 res2 = _mm_shuffle_ps(res, res, _MM_SHUFFLE(1, 1, 1, 1));
...


sollte auch gehen und ist bestimmt schneller als Transpose

[del_4901]

Es ändert vielleicht ein bisschen, aber das grundsätzliche Problem bleibt bestehen, die Version mit volatile temps verwendet genauso _mm_load1_ps und ist trotzdem 10 mal so schnell.
Die instuktionen sind mit den beiden temp Variablen ja auch komplett unabhaenig. Klar, dass die besser in die Pipeline passen.

Du kannst versuchen (wenn moeglich) n-mal r1 und r2 zu berechnen und nach der Schleife die n-Werte zusammenrechnen. Damit bekommst du mehr unabhaenige Instuktionen zusammen. Soweit ich weiss haben die SSE Instuktionen relativ hohe Latenzen (zumindest bei AMD).

http://software.intel.com/sites/landingpage/IntrinsicsGuide/