Sto studiando l'effetto della vettorizzazione sulle prestazioni del programma. A questo proposito, ho scritto il seguente codice:
#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 questo codice, sto semplicemente inizializzando e moltiplicando due vettori. I risultati vengono salvati nel vettore c . Quello che mi interessa principalmente è l'effetto della vettorizzazione del seguente ciclo:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
Compilo il codice usando i seguenti due comandi:
1) icc -O2 TestSMID.c -o TestSMID -no-vec -no-simd
2) icc -O2 TestSMID.c -o TestSMID -vec-report2
Mi aspetto di vedere un miglioramento delle prestazioni poiché il secondo comando vettorializza correttamente il ciclo. Tuttavia, i miei studi mostrano che non vi è alcun miglioramento delle prestazioni quando il ciclo è vettorializzato.
Forse mi sono perso qualcosa qui poiché non ho molta familiarità con l'argomento. Quindi, per favore fatemi sapere se c'è qualcosa di sbagliato nel mio codice.
Grazie in anticipo per il tuo aiuto.
PS:sto usando Mac OSX, quindi non è necessario allineare i dati poiché tutte le memorie allocate sono allineate a 16 byte.
Modifica:
Vorrei innanzitutto ringraziarvi tutti per i commenti e le risposte.
Ho pensato alla risposta proposta da @Mysticial e ci sono alcuni ulteriori punti che dovrebbero essere menzionati qui.
Innanzitutto , come menzionato da @Vinska, c[k]=a[k]*b[k] non richiede un solo ciclo. Oltre all'incremento dell'indice del ciclo e al confronto effettuato per garantire che k è inferiore a LEN , ci sono altre cose da fare per eseguire l'operazione. Dando un'occhiata al codice assembly generato dal compilatore, si può notare che una semplice moltiplicazione richiede molto più di un ciclo. La versione vettorializzata è simile a:
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
E la versione non vettoriale è:
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
Oltre a questo, il processore non carica solo 24 byte. In ogni accesso alla memoria viene caricata una riga intera (64 byte). Ancora più importante, poiché la memoria richiesta per a , b e c è contiguo, il prefetcher aiuterebbe sicuramente molto e carica i blocchi successivi in anticipo.
Detto questo, penso che la larghezza di banda della memoria calcolata da @Mysticial sia troppo pessimistica.
Inoltre, l'utilizzo di SIMD per migliorare le prestazioni del programma per un'aggiunta molto semplice è menzionato in Intel Vectorization Guide. Pertanto, sembra che dovremmo essere in grado di ottenere un miglioramento delle prestazioni per questo ciclo molto semplice.
Edit2:
Grazie ancora per i tuoi commenti. Inoltre, grazie al codice di esempio @Mysticial, ho finalmente visto l'effetto di SIMD sul miglioramento delle prestazioni. Il problema, come menzionato da Mysticial, era la larghezza di banda della memoria. Con la scelta della taglia piccola per a , b e c che si inseriscono nella cache L1, si può vedere che SIMD può aiutare a migliorare significativamente le prestazioni. Ecco i risultati che ho ottenuto:
icc -O2 -o TestSMIDNoVec -no-vec TestSMID2.c: 17.34 sec
icc -O2 -o TestSMIDVecNoUnroll -vec-report2 TestSMID2.c: 9.33 sec
E lo svolgimento del ciclo migliora ulteriormente le prestazioni:
icc -O2 -o TestSMIDVecUnroll -vec-report2 TestSMID2.c -unroll=8: 8.6sec
Inoltre, dovrei ricordare che il mio processore impiega solo un ciclo per completare un'iterazione quando viene compilato con -O2 .
PS:il mio computer è un Macbook Pro core i5 a 2,5 GHz (dual core)
Risposte:
Questa risposta originale era valida nel 2013. A partire dal 2017 l'hardware è cambiato abbastanza che sia la domanda che la risposta non sono aggiornate.
Vedi la fine di questa risposta per l'aggiornamento 2017.
Risposta originale (2013):
Perché sei bloccato dalla larghezza di banda della memoria.
Sebbene la vettorizzazione e altre micro-ottimizzazioni possano migliorare la velocità di calcolo, non possono aumentare la velocità della tua memoria.
Nel tuo esempio:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
Stai facendo un solo passaggio su tutta la memoria facendo pochissimo lavoro. Questo sta massimizzando la larghezza di banda della tua memoria.
Quindi, indipendentemente da come è ottimizzato (vettorizzato, srotolato, ecc...) non diventerà molto più veloce.
Una tipica macchina desktop del 2013 ha dell'ordine di 10 GB/s di larghezza di banda della memoria*.
Il tuo ciclo tocca 24 byte/iterazione .
Senza la vettorizzazione, un moderno processore x64 può probabilmente fare circa 1 iterazione per ciclo*.
Supponiamo di essere in esecuzione a 4 GHz:
(4 * 10^9) * 24 bytes/iteration = 96 GB/s
È quasi 10 volte la larghezza di banda della tua memoria, senza vettorizzazione.
*Non sorprende che alcune persone abbiano dubitato dei numeri che ho fornito sopra poiché non ho fornito alcuna citazione. Bene, quelli erano fuori dalla mia testa per esperienza. Quindi ecco alcuni benchmark per dimostrarlo.
L'iterazione del ciclo può essere eseguita alla velocità di 1 ciclo/iterazione:
Possiamo eliminare il collo di bottiglia della memoria se riduciamo LEN in modo che rientri nella cache.
(l'ho testato in C++ poiché era più semplice. Ma non fa differenza.)
#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;
}
- Processore:Intel Core i7 2600K a 4,2 GHz
- Compilatore:Visual Studio 2012
- Tempo:6,55 secondi
In questo test, ho eseguito 25.600.000.000 di iterazioni in soli 6,55 secondi.
6.55 * 4.2 GHz=27.510.000.000 di cicli27,510,000,000 / 25,600,000,000=1.074 cicli/iterazione
Ora se ti stai chiedendo come è possibile fare:
- 2 carichi
- 1 negozio
- 1 moltiplicare
- contatore incrementale
- confronta + ramo
tutto in un ciclo...
È perché i moderni processori e compilatori sono fantastici.
Sebbene ciascuna di queste operazioni abbia latenza (in particolare la moltiplicazione), il processore è in grado di eseguire più iterazioni contemporaneamente. La mia macchina di prova è un processore Sandy Bridge, che è in grado di sostenere carichi 2x128b, 1x128b store e 1x256b vector FP moltiplicano ogni singolo ciclo. E potenzialmente un'altra o due operazioni vettoriali o intere, se i carichi sono operandi di origine di memoria per operazioni micro-fuse. (2 carichi + 1 velocità effettiva di archiviazione solo quando si utilizzano 256b caricamenti/memorizza AVX, altrimenti solo due operazioni di memoria totali per ciclo (al massimo un negozio)).
Osservando l'assembly (che ometterò per brevità), sembra che il compilatore abbia svolto il ciclo, riducendo così il sovraccarico del ciclo. Ma non è riuscito a vettorializzarlo.
La larghezza di banda della memoria è dell'ordine di 10 GB/s:
Il modo più semplice per verificarlo è tramite un 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;
}
- Processore:Intel Core i7 2600K a 4,2 GHz
- Compilatore:Visual Studio 2012
- Tempo:5.811 secondi
Quindi ci vuole la mia macchina 5.811 secondi per scrivere su 100 GB di memoria. Si tratta di 17,2 GB/s .
E il mio processore è di fascia alta. I processori di generazione Nehalem e Core 2 hanno una larghezza di banda di memoria inferiore.
Aggiornamento marzo 2017:
A partire dal 2017, le cose si sono complicate.
Grazie alla memoria DDR4 e quad-channel, non è più possibile che un singolo thread satura la larghezza di banda della memoria. Ma il problema della larghezza di banda non va necessariamente via. Anche se la larghezza di banda è aumentata, anche i core del processore sono migliorati e ce ne sono di più.
Per dirla matematicamente:
- Ogni core ha un limite di larghezza di banda
X. - La memoria principale ha un limite di larghezza di banda di
Y. - Sui sistemi meno recenti,
X > Y. - Sugli attuali sistemi di fascia alta,
X < Y. MaX * (# of cores) > Y.
Nel 2013:Sandy Bridge a 4 GHz + DDR3 a doppio canale a 1333 MHz
- Nessuna vettorizzazione (caricamento/memorizza 8 byte):
X = 32 GB/seY = ~17 GB/s - SSE vettoriale* (caricamento/memorizza 16 byte):
X = 64 GB/seY = ~17 GB/s
Ora nel 2017:Haswell-E a 4 GHz + DDR4 a quattro canali a 2400 MHz
- Nessuna vettorizzazione (caricamento/memorizza 8 byte):
X = 32 GB/seY = ~70 GB/s - AVX vettorizzato* (caricamento/negozi a 32 byte):
X = 64 GB/seY = ~70 GB/s
(Sia per Sandy Bridge che per Haswell, i limiti dell'architettura nella cache limiteranno la larghezza di banda a circa 16 byte/ciclo indipendentemente dalla larghezza della SIMD.)
Quindi al giorno d'oggi, un singolo thread non sarà sempre in grado di saturare la larghezza di banda della memoria. E dovrai vettorializzare per raggiungere quel limite di X . Ma continuerai a raggiungere il limite di larghezza di banda della memoria principale di Y con 2 o più thread.
Ma una cosa non è cambiata e probabilmente non cambierà per molto tempo:Non sarai in grado di eseguire un ciclo di monopolizzazione della larghezza di banda su tutti i core senza saturare la larghezza di banda totale della memoria.