Warum die Vektorisierung der Schleife keine Leistungsverbesserung bringt

Warum die Vektorisierung der Schleife keine Leistungsverbesserung bringt

Ich untersuche die Auswirkung der Vektorisierung auf die Leistung des Programms. Dazu habe ich folgenden Code geschrieben:

#include <stdio.h>
 #include <sys/time.h>
 #include <stdlib.h>
 #define LEN 10000000
 int main(){
     struct timeval stTime, endTime;
     double* a = (double*)malloc(LEN*sizeof(*a));
     double* b = (double*)malloc(LEN*sizeof(*b));
     double* c = (double*)malloc(LEN*sizeof(*c));
     int k;
     for(k = 0; k < LEN; k++){
         a[k] = rand();
         b[k] = rand();
     }
     gettimeofday(&stTime, NULL);
     for(k = 0; k < LEN; k++)
         c[k] = a[k] * b[k];
     gettimeofday(&endTime, NULL);
     FILE* fh = fopen("dump", "w");
     for(k = 0; k < LEN; k++)
         fprintf(fh, "c[%d] = %f\t", k, c[k]);
     fclose(fh);
     double timeE = (double)(endTime.tv_usec + endTime.tv_sec*1000000 - stTime.tv_usec - stTime.tv_sec*1000000);
     printf("Time elapsed: %f\n", timeE);
     return 0;
 }

In diesem Code initialisiere und multipliziere ich einfach zwei Vektoren. Die Ergebnisse werden im Vektor c gespeichert . Was mich hauptsächlich interessiert, ist der Effekt der Vektorisierung der folgenden Schleife:

for(k = 0; k < LEN; k++)
     c[k] = a[k] * b[k];

Ich kompiliere den Code mit den folgenden zwei Befehlen:

1) icc -O2 TestSMID.c -o TestSMID -no-vec -no-simd
 2) icc -O2 TestSMID.c -o TestSMID -vec-report2

Ich erwarte eine Leistungsverbesserung, da der zweite Befehl die Schleife erfolgreich vektorisiert. Meine Studien zeigen jedoch, dass es keine Leistungsverbesserung gibt, wenn die Schleife vektorisiert wird.

Vielleicht habe ich hier etwas übersehen, da ich mich mit dem Thema nicht so gut auskenne. Lassen Sie mich also bitte wissen, wenn etwas mit meinem Code nicht stimmt.

Vielen Dank im Voraus für Ihre Hilfe.

PS:Ich verwende Mac OSX, daher müssen die Daten nicht ausgerichtet werden, da alle zugewiesenen Speicher 16-Byte-ausgerichtet sind.

Edit:
Ich möchte mich zuerst bei euch allen für eure Kommentare und Antworten bedanken.
Ich habe über die von @Mystcial vorgeschlagene Antwort nachgedacht und es gibt einige weitere Punkte, die hier erwähnt werden sollten.
Erstens , wie @Vinska erwähnt hat, c[k]=a[k]*b[k] dauert nicht nur einen Zyklus. Zusätzlich zum Inkrement des Schleifenindex und des durchgeführten Vergleichs wird sichergestellt, dass k kleiner als LEN ist , müssen noch andere Dinge getan werden, um die Operation durchzuführen. Wenn man sich den vom Compiler generierten Assemblercode ansieht, sieht man, dass eine einfache Multiplikation viel mehr als einen Zyklus benötigt. Die vektorisierte Version sieht so aus:

L_B1.9:                         # Preds L_B1.8
         movq      %r13, %rax                                    #25.5
         andq      $15, %rax                                     #25.5
         testl     %eax, %eax                                    #25.5
         je        L_B1.12       # Prob 50%                      #25.5
                                 # LOE rbx r12 r13 r14 r15 eax
 L_B1.10:                        # Preds L_B1.9
         testb     $7, %al                                       #25.5
         jne       L_B1.32       # Prob 10%                      #25.5
                                 # LOE rbx r12 r13 r14 r15
 L_B1.11:                        # Preds L_B1.10
         movsd     (%r14), %xmm0                                 #26.16
         movl      $1, %eax                                      #25.5
         mulsd     (%r15), %xmm0                                 #26.23
         movsd     %xmm0, (%r13)                                 #26.9
                                 # LOE rbx r12 r13 r14 r15 eax
 L_B1.12:                        # Preds L_B1.11 L_B1.9
         movl      %eax, %edx                                    #25.5
         movl      %eax, %eax                                    #26.23
         negl      %edx                                          #25.5
         andl      $1, %edx                                      #25.5
         negl      %edx                                          #25.5
         addl      $10000000, %edx                               #25.5
         lea       (%r15,%rax,8), %rcx                           #26.23
         testq     $15, %rcx                                     #25.5
         je        L_B1.16       # Prob 60%                      #25.5
                                 # LOE rdx rbx r12 r13 r14 r15 eax
 L_B1.13:                        # Preds L_B1.12
         movl      %eax, %eax                                    #25.5
                                 # LOE rax rdx rbx r12 r13 r14 r15
 L_B1.14:                        # Preds L_B1.14 L_B1.13
         movups    (%r15,%rax,8), %xmm0                          #26.23
         movsd     (%r14,%rax,8), %xmm1                          #26.16
         movhpd    8(%r14,%rax,8), %xmm1                         #26.16
         mulpd     %xmm0, %xmm1                                  #26.23
         movntpd   %xmm1, (%r13,%rax,8)                          #26.9
         addq      $2, %rax                                      #25.5
         cmpq      %rdx, %rax                                    #25.5
         jb        L_B1.14       # Prob 99%                      #25.5
         jmp       L_B1.20       # Prob 100%                     #25.5
                                 # LOE rax rdx rbx r12 r13 r14 r15
 L_B1.16:                        # Preds L_B1.12
         movl      %eax, %eax                                    #25.5
                                 # LOE rax rdx rbx r12 r13 r14 r15
 L_B1.17:                        # Preds L_B1.17 L_B1.16
         movsd     (%r14,%rax,8), %xmm0                          #26.16
         movhpd    8(%r14,%rax,8), %xmm0                         #26.16
         mulpd     (%r15,%rax,8), %xmm0                          #26.23
         movntpd   %xmm0, (%r13,%rax,8)                          #26.9
         addq      $2, %rax                                      #25.5
         cmpq      %rdx, %rax                                    #25.5
         jb        L_B1.17       # Prob 99%                      #25.5
                                 # LOE rax rdx rbx r12 r13 r14 r15
 L_B1.18:                        # Preds L_B1.17
         mfence                                                  #25.5
                                 # LOE rdx rbx r12 r13 r14 r15
 L_B1.19:                        # Preds L_B1.18
         mfence                                                  #25.5
                                 # LOE rdx rbx r12 r13 r14 r15
 L_B1.20:                        # Preds L_B1.14 L_B1.19 L_B1.32
         cmpq      $10000000, %rdx                               #25.5
         jae       L_B1.24       # Prob 0%                       #25.5
                                 # LOE rdx rbx r12 r13 r14 r15
 L_B1.22:                        # Preds L_B1.20 L_B1.22
         movsd     (%r14,%rdx,8), %xmm0                          #26.16
         mulsd     (%r15,%rdx,8), %xmm0                          #26.23
         movsd     %xmm0, (%r13,%rdx,8)                          #26.9
         incq      %rdx                                          #25.5
         cmpq      $10000000, %rdx                               #25.5
         jb        L_B1.22       # Prob 99%                      #25.5
                                 # LOE rdx rbx r12 r13 r14 r15
 L_B1.24:                        # Preds L_B1.22 L_B1.20

Und die nicht vektoisierte Version ist:

L_B1.9:                         # Preds L_B1.8
         xorl      %eax, %eax                                    #25.5
                                 # LOE rbx r12 r13 r14 r15 eax
 L_B1.10:                        # Preds L_B1.10 L_B1.9
         lea       (%rax,%rax), %edx                             #26.9
         incl      %eax                                          #25.5
         cmpl      $5000000, %eax                                #25.5
         movsd     (%r15,%rdx,8), %xmm0                          #26.16
         movsd     8(%r15,%rdx,8), %xmm1                         #26.16
         mulsd     (%r13,%rdx,8), %xmm0                          #26.23
         mulsd     8(%r13,%rdx,8), %xmm1                         #26.23
         movsd     %xmm0, (%rbx,%rdx,8)                          #26.9
         movsd     %xmm1, 8(%rbx,%rdx,8)                         #26.9
         jb        L_B1.10       # Prob 99%                      #25.5
                                 # LOE rbx r12 r13 r14 r15 eax

Außerdem lädt der Prozessor nicht nur 24 Bytes. Bei jedem Zugriff auf den Speicher wird eine volle Zeile (64 Bytes) geladen. Noch wichtiger, da der Speicherbedarf für a , b , und c zusammenhängend ist, würde Prefetcher auf jeden Fall sehr helfen und lädt die nächsten Blöcke im Voraus.
Allerdings denke ich, dass die von @Mystcial berechnete Speicherbandbreite zu pessimistisch ist.

Darüber hinaus wird die Verwendung von SIMD zur Verbesserung der Programmleistung für eine sehr einfache Hinzufügung im Intel Vectorization Guide erwähnt. Daher scheint es, dass wir in der Lage sein sollten, einige Leistungsverbesserungen für diese sehr einfache Schleife zu erzielen.

Edit2:
Nochmals vielen Dank für Ihre Kommentare. Dank des Beispielcodes von @Mystcial habe ich endlich die Auswirkung von SIMD auf die Leistungsverbesserung gesehen. Das Problem war, wie Mystcial erwähnte, die Speicherbandbreite. Bei kleiner Größe für a , b , und c die in den L1-Cache passen, zeigt sich, dass SIMD helfen kann, die Performance deutlich zu verbessern. Hier sind die Ergebnisse, die ich erhalten habe:

icc -O2 -o TestSMIDNoVec -no-vec TestSMID2.c: 17.34 sec
 icc -O2 -o TestSMIDVecNoUnroll -vec-report2 TestSMID2.c: 9.33 sec

Und das Aufrollen der Schleife verbessert die Leistung noch weiter:

icc -O2 -o TestSMIDVecUnroll -vec-report2 TestSMID2.c -unroll=8: 8.6sec

Außerdem sollte ich erwähnen, dass mein Prozessor nur einen Zyklus benötigt, um eine Iteration abzuschließen, wenn er mit -O2 kompiliert wird .

PS:Mein Computer ist ein Macbook Pro Core i5 @2.5GHz (Dual Core)

Antworten:

Diese ursprüngliche Antwort war bereits 2013 gültig. Seit 2017 haben sich die Dinge so weit geändert, dass sowohl die Frage als auch die Antwort veraltet sind.

Siehe das Ende dieser Antwort für das Update 2017.

Ursprüngliche Antwort (2013):

Weil Sie durch Speicherbandbreite einen Engpass haben.

Während Vektorisierung und andere Mikrooptimierungen die Rechengeschwindigkeit verbessern können, können sie die Geschwindigkeit Ihres Speichers nicht erhöhen.

In Ihrem Beispiel:

for(k = 0; k < LEN; k++)
     c[k] = a[k] * b[k];

Sie machen einen einzigen Durchgang über den gesamten Speicher und machen sehr wenig Arbeit. Dies maximiert Ihre Speicherbandbreite.

Unabhängig davon, wie es optimiert ist (vektorisiert, entrollt usw.), wird es nicht viel schneller.

Ein typischer Desktop-Computer von 2013 hat in der Größenordnung von 10 GB/s Speicherbandbreite*.
Ihre Schleife berührt 24 Byte/Iteration .

Ohne Vektorisierung kann ein moderner x64-Prozessor wahrscheinlich etwa 1 Iteration pro Zyklus ausführen*.

Angenommen, Sie arbeiten mit 4 GHz:

(4 * 10^9) * 24 bytes/iteration = 96 GB/s

Das ist fast das 10-fache Ihrer Speicherbandbreite - ohne Vektorisierung.

*Es überrascht nicht, dass einige Leute die Zahlen bezweifelten, die ich oben angegeben habe, da ich kein Zitat angegeben habe. Nun, die waren mir aus Erfahrung aus dem Kopf. Hier sind einige Benchmarks, um dies zu beweisen.

Die Schleifeniteration kann so schnell wie 1 Zyklus/Iteration ausgeführt werden:

Wir können den Speicherengpass beseitigen, wenn wir LEN reduzieren damit es in den Cache passt.

(Ich habe dies in C++ getestet, da es einfacher war. Aber es macht keinen Unterschied.)

#include <iostream>
 #include <time.h>
 using std::cout;
 using std::endl;
 int main(){
     const int LEN = 256;
     double *a = (double*)malloc(LEN*sizeof(*a));
     double *b = (double*)malloc(LEN*sizeof(*a));
     double *c = (double*)malloc(LEN*sizeof(*a));
     int k;
     for(k = 0; k < LEN; k++){
         a[k] = rand();
         b[k] = rand();
     }
     clock_t time0 = clock();
     for (int i = 0; i < 100000000; i++){
         for(k = 0; k < LEN; k++)
             c[k] = a[k] * b[k];
     }
     clock_t time1 = clock();
     cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;
 }

Prozessor:Intel Core i7 2600K @ 4,2 GHz

Compiler:Visual Studio 2012

Zeit:6,55 Sekunden

In diesem Test habe ich 25.600.000.000 Iterationen in nur 6,55 ausgeführt Sekunden.

6.55 * 4.2 GHz =27.510.000.000 Zyklen

27,510,000,000 / 25,600,000,000 =1.074 Zyklen/Iteration

Wenn Sie sich jetzt fragen, wie das möglich ist:

2 Ladungen

1 Geschäft

1 multiplizieren

Zähler erhöhen

vergleichen + verzweigen

alles in einem Zyklus...

Das liegt daran, dass moderne Prozessoren und Compiler großartig sind.

Während jede dieser Operationen eine Latenz hat (insbesondere das Multiplizieren), ist der Prozessor in der Lage, mehrere Iterationen gleichzeitig auszuführen. Meine Testmaschine ist ein Sandy-Bridge-Prozessor, der in der Lage ist, 2x128b-Lasten, 1x128b-Speicher und 1x256b-Vektor-FP-Multiplikation in jedem einzelnen Zyklus auszuhalten. Und möglicherweise ein oder zwei weitere Vektor- oder Integer-Operationen, wenn die Ladevorgänge Speicherquelloperanden für mikrofusionierte uops sind. (2 Ladevorgänge + 1 Speicherdurchsatz nur bei Verwendung von 256b-AVX-Ladevorgängen/-Speichervorgängen, ansonsten nur zwei Gesamtspeicheroperationen pro Zyklus (höchstens ein Speichervorgang)).

Wenn ich mir die Assembly ansehe (die ich der Kürze halber weglasse), scheint es, als hätte der Compiler die Schleife entrollt und dadurch den Schleifen-Overhead reduziert. Aber es ist nicht ganz gelungen, es zu vektorisieren.

Die Speicherbandbreite liegt in der Größenordnung von 10 GB/s:

Der einfachste Weg, dies zu testen, ist über einen memset() :

#include <iostream>
 #include <time.h>
 using std::cout;
 using std::endl;
 int main(){
     const int LEN = 1 << 30;    //  1GB
     char *a = (char*)calloc(LEN,1);
     clock_t time0 = clock();
     for (int i = 0; i < 100; i++){
         memset(a,0xff,LEN);
     }
     clock_t time1 = clock();
     cout << (double)(time1 - time0) / CLOCKS_PER_SEC << endl;
 }

Prozessor:Intel Core i7 2600K @ 4,2 GHz

Compiler:Visual Studio 2012

Zeit:5,811 Sekunden

Also braucht mein Rechner 5.811 Sekunden, um in 100 GB Speicher zu schreiben. Das sind etwa 17,2 GB/s .

Und mein Prozessor ist am oberen Ende. Die Prozessoren der Generation Nehalem und Core 2 haben weniger Speicherbandbreite.

Aktualisierung März 2017:

Seit 2017 sind die Dinge komplizierter geworden.

Dank DDR4 und Quad-Channel-Speicher ist es nicht mehr möglich, dass ein einzelner Thread die Speicherbandbreite sättigt. Aber das Problem der Bandbreite verschwindet nicht unbedingt. Obwohl die Bandbreite gestiegen ist, haben sich auch die Prozessorkerne verbessert - und es gibt mehr davon.

Mathematisch ausgedrückt:

Jeder Kern hat eine Bandbreitenbegrenzung X .

Hauptspeicher hat eine Bandbreitenbegrenzung von Y .

Auf älteren Systemen X > Y .

Auf aktuellen High-End-Systemen X < Y . Aber X * (# of cores) > Y .

Damals im Jahr 2013:Sandy Bridge @ 4 GHz + Dual-Channel DDR3 @ 1333 MHz

Keine Vektorisierung (8-Byte Laden/Speichern):X = 32 GB/s und Y = ~17 GB/s

Vektorisiertes SSE* (16-Byte Laden/Speichern):X = 64 GB/s und Y = ~17 GB/s

Jetzt im Jahr 2017:Haswell-E @ 4 GHz + Quad-Channel DDR4 @ 2400 MHz

Keine Vektorisierung (8-Byte Laden/Speichern):X = 32 GB/s und Y = ~70 GB/s

Vektorisiertes AVX* (32-Byte-Laden/Speichern):X = 64 GB/s und Y = ~70 GB/s

_{(Sowohl bei Sandy Bridge als auch bei Haswell begrenzen architektonische Beschränkungen im Cache die Bandbreite unabhängig von der SIMD-Breite auf etwa 16 Byte/Zyklus.)}

Heutzutage wird ein einzelner Thread also nicht immer in der Lage sein, die Speicherbandbreite zu sättigen. Und Sie müssen vektorisieren, um dieses Limit von X zu erreichen . Aber Sie werden immer noch das Bandbreitenlimit des Hauptspeichers von Y erreichen mit 2 oder mehr Threads.

Aber eines hat sich nicht geändert und wird sich wahrscheinlich noch lange nicht ändern:Sie werden nicht in der Lage sein, eine bandbreitenraubende Schleife auf allen Kernen auszuführen, ohne die gesamte Speicherbandbreite zu sättigen.