Dlaczego wektoryzacja pętli nie ma poprawy wydajności
Badam wpływ wektoryzacji na wydajność programu. W związku z tym napisałem następujący kod:
#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;
}
W tym kodzie po prostu inicjuję i mnożę dwa wektory. Wyniki są zapisywane w wektorzec. Interesuje mnie głównie efekt wektorowania następującej pętli:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
Kompiluję kod za pomocą następujących dwóch poleceń:
1) icc -O2 TestSMID.c -o TestSMID -no-vec -no-simd
2) icc -O2 TestSMID.c -o TestSMID -vec-report2
Spodziewam się poprawy wydajności, ponieważ druga komenda pomyślnie wektorizuje pętlę. Jednak moje badania pokazują, że nie ma poprawy wydajności, gdy pętla jest wektoryzowana.
Być może coś mi tu brakowało, ponieważ nie jestem zbyt dobrze zaznajomiony z tematem. Daj mi znać, jeśli coś jest nie tak z moim kodem.
Z góry dziękuje za twoją pomoc.
PS: Używam Mac OSX, więc nie ma potrzeby wyrównywania danych, ponieważ wszystkie przydzielone pamięci są wyrównane do 16 bajtów.
Edytuj: Chciałbym najpierw podziękować wszystkim za komentarze i odpowiedzi. Zastanawiałem się nad odpowiedzią zaproponowaną przez @Mysticial i jest kilka dalszych punktów, które należy tutaj wspomnieć. Po pierwsze, jak wspomniała @Vinska,c[k]=a[k]*b[k] nie zajmuje tylko jednego cyklu. Oprócz przyrostu indeksu pętli i porównania, aby to zapewnićk jest mniejszy odLEN, są inne rzeczy do zrobienia, aby wykonać operację. Patrząc na kod zespołu wygenerowany przez kompilator, można zauważyć, że proste mnożenie wymaga znacznie więcej niż jednego cyklu. Wersja wektoryzowana wygląda następująco:
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
A wersja niezaektoryzowana to:
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
Poza tym procesor nie ładuje tylko 24 bajtów. W każdym dostępie do pamięci ładowana jest pełna linia (64 bajty). Co ważniejsze, ponieważ pamięć potrzebnaa, b, ic jest ciągły, prefetcher zdecydowanie pomoże dużo i wcześnie załaduje kolejne bloki. Powiedziawszy to, myślę, że przepustowość pamięci obliczona przez @Mysticial jest zbyt pesymistyczna.
Ponadto wspomina się o wykorzystaniu SIMD do poprawy wydajności programu dla bardzo prostego dodawaniaPrzewodnik do wektorowania w Intel. Dlatego wydaje się, że powinniśmy być w stanie uzyskać pewną poprawę wydajności w tej bardzo prostej pętli.
Edit2: Jeszcze raz dziękuję za komentarze. Ponadto, dzięki przykładowemu kodowi @Mysticial, w końcu dostrzegłem wpływ SIMD na poprawę wydajności. Problemem, jak wspomniał Mysticial, była przepustowość pamięci. Z wyborem małego rozmiaru dlaa, b, ic które pasują do pamięci podręcznej L1, widać, że SIMD może znacząco poprawić wydajność. Oto wyniki, które otrzymałem:
icc -O2 -o TestSMIDNoVec -no-vec TestSMID2.c: 17.34 sec
icc -O2 -o TestSMIDVecNoUnroll -vec-report2 TestSMID2.c: 9.33 sec
A rozwinięcie pętli jeszcze bardziej poprawia wydajność:
icc -O2 -o TestSMIDVecUnroll -vec-report2 TestSMID2.c -unroll=8: 8.6sec
Powinienem też wspomnieć, że mój procesor potrzebuje tylko jednego cyklu do zakończenia iteracji po skompilowaniu-O2.
PS: Mój komputer to rdzeń MacBooka Pro i5 @ 2,5 GHz (dwurdzeniowy)