Estoy investigando el efecto de la vectorización en el rendimiento del programa. En este sentido, he escrito el siguiente código:
#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;
}
En este código, simplemente estoy inicializando y multiplicando dos vectores. Los resultados se guardan en el vector c . Lo que me interesa principalmente es el efecto de vectorizar el siguiente bucle:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
Compilo el código usando los siguientes dos comandos:
1) icc -O2 TestSMID.c -o TestSMID -no-vec -no-simd
2) icc -O2 TestSMID.c -o TestSMID -vec-report2
Espero ver una mejora en el rendimiento ya que el segundo comando vectoriza con éxito el ciclo. Sin embargo, mis estudios muestran que no hay una mejora en el rendimiento cuando se vectoriza el bucle.
Es posible que me haya perdido algo aquí ya que no estoy muy familiarizado con el tema. Entonces, avíseme si hay algún problema con mi código.
Gracias de antemano por su ayuda.
PD:estoy usando Mac OSX, por lo que no es necesario alinear los datos ya que todas las memorias asignadas están alineadas en 16 bytes.
Editar:
Primero me gustaría agradecerles a todos por sus comentarios y respuestas.
Pensé en la respuesta propuesta por @Mysticial y hay algunos puntos adicionales que deberían mencionarse aquí.
En primer lugar , como mencionó @Vinska, c[k]=a[k]*b[k] no toma solo un ciclo. Además del incremento del índice de bucle y la comparación realizada para garantizar que k es menor que LEN , hay otras cosas que hacer para realizar la operación. Echando un vistazo al código ensamblador generado por el compilador, se puede ver que una simple multiplicación necesita mucho más que un ciclo. La versión vectorizada se parece 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
Y la versión no vectorizada es:
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
Además de esto, el procesador no carga solo 24 bytes. En cada acceso a memoria se carga una línea completa (64 bytes). Más importante aún, dado que la memoria requerida para a , b y c es contiguo, prefetcher definitivamente ayudaría mucho y carga los siguientes bloques por adelantado.
Habiendo dicho eso, creo que el ancho de banda de la memoria calculado por @Mysticial es demasiado pesimista.
Además, el uso de SIMD para mejorar el rendimiento del programa para una adición muy simple se menciona en la Guía de vectorización de Intel. Por lo tanto, parece que deberíamos poder obtener alguna mejora en el rendimiento de este bucle muy simple.
Edit2:
Gracias de nuevo por sus comentarios. Además, gracias al código de muestra @Mysticial, finalmente vi el efecto de SIMD en la mejora del rendimiento. El problema, como mencionó Mysticial, era el ancho de banda de la memoria. Con la elección de tamaño pequeño para a , b y c que encajan en la memoria caché L1, se puede ver que SIMD puede ayudar a mejorar significativamente el rendimiento. Estos son los resultados que obtuve:
icc -O2 -o TestSMIDNoVec -no-vec TestSMID2.c: 17.34 sec
icc -O2 -o TestSMIDVecNoUnroll -vec-report2 TestSMID2.c: 9.33 sec
Y desenrollar el bucle mejora aún más el rendimiento:
icc -O2 -o TestSMIDVecUnroll -vec-report2 TestSMID2.c -unroll=8: 8.6sec
Además, debo mencionar que solo se necesita un ciclo para que mi procesador complete una iteración cuando se compila con -O2 .
PD:Mi computadora es una Macbook Pro core i5 @2.5GHz (dual core)
Respuestas:
Esta respuesta original era válida en 2013. A partir del hardware de 2017, las cosas han cambiado lo suficiente como para que tanto la pregunta como la respuesta estén desactualizadas.
Consulte el final de esta respuesta para la actualización de 2017.
Respuesta original (2013):
Porque estás atascado por el ancho de banda de la memoria.
Si bien la vectorización y otras microoptimizaciones pueden mejorar la velocidad de cómputo, no pueden aumentar la velocidad de su memoria.
En tu ejemplo:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
Estás haciendo un solo paso sobre toda la memoria haciendo muy poco trabajo. Esto está maximizando el ancho de banda de su memoria.
Entonces, independientemente de cómo esté optimizado (vectorizado, desenrollado, etc...) no será mucho más rápido.
Una máquina de escritorio típica de 2013 tiene del orden de 10 GB/s de ancho de banda de memoria*.
Tu ciclo toca 24 bytes/iteración .
Sin la vectorización, un procesador x64 moderno probablemente pueda realizar alrededor de 1 iteración por ciclo*.
Suponga que está funcionando a 4 GHz:
(4 * 10^9) * 24 bytes/iteration = 96 GB/s
Eso es casi 10 veces el ancho de banda de su memoria, sin vectorización.
*No es sorprendente que algunas personas dudaran de los números que di arriba ya que no di ninguna cita. Bueno, esos estaban fuera de mi cabeza por experiencia. Así que aquí hay algunos puntos de referencia para probarlo.
La iteración del bucle puede ejecutarse tan rápido como 1 ciclo/iteración:
Podemos deshacernos del cuello de botella de la memoria si reducimos LEN para que quepa en caché.
(Probé esto en C++ porque era más fácil. Pero no hace ninguna diferencia).
#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;
}
- Procesador:Intel Core i7 2600K a 4,2 GHz
- Compilador:Visual Studio 2012
- Tiempo:6,55 segundos
En esta prueba, ejecuté 25 600 000 000 iteraciones en solo 6,55 segundos.
6.55 * 4.2 GHz=27 510 000 000 ciclos27,510,000,000 / 25,600,000,000=1.074 ciclos/iteración
Ahora, si te preguntas cómo es posible hacer:
- 2 cargas
- 1 tienda
- 1 multiplicado
- contador de incrementos
- comparar + rama
todo en un ciclo...
Es porque los procesadores y compiladores modernos son asombrosos.
Si bien cada una de estas operaciones tiene latencia (especialmente la multiplicación), el procesador puede ejecutar múltiples iteraciones al mismo tiempo. Mi máquina de prueba es un procesador Sandy Bridge, que es capaz de soportar cargas de 2x128b, almacenamiento de 1x128b y vector FP de 1x256b multiplicando cada ciclo. Y potencialmente otra o dos operaciones vectoriales o enteras, si las cargas son operandos de fuente de memoria para uops micro-fusionados. (2 cargas + 1 rendimiento de almacenamiento solo cuando se usan cargas/almacenes 256b AVX; de lo contrario, solo dos operaciones de memoria totales por ciclo (como máximo un almacenamiento)).
Mirando el ensamblaje (que omitiré por brevedad), parece que el compilador desenrolló el bucle, reduciendo así la sobrecarga del bucle. Pero no logró vectorizarlo del todo.
El ancho de banda de la memoria es del orden de 10 GB/s:
La forma más fácil de probar esto es a través de 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;
}
- Procesador:Intel Core i7 2600K a 4,2 GHz
- Compilador:Visual Studio 2012
- Tiempo:5,811 segundos
Entonces toma mi máquina 5.811 segundos para escribir en 100 GB de memoria. Eso es alrededor de 17,2 GB/s .
Y mi procesador está en el extremo superior. Los procesadores de generación Nehalem y Core 2 tienen menos ancho de banda de memoria.
Actualización de marzo de 2017:
A partir de 2017, las cosas se han vuelto más complicadas.
Gracias a DDR4 y la memoria de cuatro canales, ya no es posible que un solo hilo sature el ancho de banda de la memoria. Pero el problema del ancho de banda no necesariamente desaparece. Aunque el ancho de banda ha aumentado, los núcleos de los procesadores también han mejorado, y hay más.
Para decirlo matemáticamente:
- Cada núcleo tiene un límite de ancho de banda
X. - La memoria principal tiene un límite de ancho de banda de
Y. - En sistemas más antiguos,
X > Y. - En los sistemas actuales de gama alta,
X < Y. PeroX * (# of cores) > Y.
En 2013:Sandy Bridge a 4 GHz + DDR3 de dos canales a 1333 MHz
- Sin vectorización (carga/almacenamiento de 8 bytes):
X = 32 GB/syY = ~17 GB/s - SSE vectorizado* (carga/almacenamiento de 16 bytes):
X = 64 GB/syY = ~17 GB/s
Ahora en 2017:Haswell-E a 4 GHz + DDR4 de cuatro canales a 2400 MHz
- Sin vectorización (carga/almacenamiento de 8 bytes):
X = 32 GB/syY = ~70 GB/s - AVX vectorizado* (carga/almacenamiento de 32 bytes):
X = 64 GB/syY = ~70 GB/s
(Tanto para Sandy Bridge como para Haswell, los límites arquitectónicos en la memoria caché limitarán el ancho de banda a unos 16 bytes/ciclo, independientemente del ancho de SIMD).
Entonces, hoy en día, un solo hilo no siempre podrá saturar el ancho de banda de la memoria. Y deberá vectorizar para lograr ese límite de X . Pero aún alcanzará el límite de ancho de banda de la memoria principal de Y con 2 o más hilos.
Pero una cosa no ha cambiado y probablemente no cambiará durante mucho tiempo:No podrá ejecutar un bucle que acapare el ancho de banda en todos los núcleos sin saturar el ancho de banda total de la memoria.