Por qué vectorizar el bucle no mejora el rendimiento
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 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 desde el segundo comando vectoriza con éxito el bucle. Sin embargo, mis estudios muestran que no hay mejora en el rendimiento cuando el bucle se vectoriza.
Puede que me haya perdido algo aquí, ya que no estoy muy familiarizado con el tema. Por lo tanto, por favor hágamelo saber si hay algo mal con mi código.
Gracias de antemano por su ayuda.
PD: Estoy usando Mac OSX, por lo que no hay necesidad de alinear los datos, ya que todas las memorias asignadas están alineadas de 16 bytes.
Editar:
Me gustaría primero gracias a todos por sus comentarios y respuestas.
Pensé en la respuesta propuesta por @ Mysticial y hay algunos puntos más que deben mencionarse aquí.
En primer lugar, como @Vinska mencionó, 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 se deben hacer para realizar la operación. Echando un vistazo al código de ensamblado generado por el compilador, se puede ver que una simple multiplicación necesita mucho más de un ciclo. La versión vectorizada se ve así:
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 vectoizada 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 la memoria, se carga una línea completa (64 bytes). Más importante aún, ya que la memoria necesaria para a, b, y c es contiguo, prefetcher definitivamente ayudaría mucho y carga los siguientes bloques por adelantado.
Dicho esto, creo que el ancho de banda de 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 Intel Vectorization Guide. Por lo tanto, parece que deberíamos ser capaces de obtener alguna mejora de rendimiento para 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 tamaño pequeño para a, b, y c que encajan en la caché L1, se puede ver que SIMD puede ayudar a mejorar el rendimiento significativamente. Aquí están 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.5 GHz (dual core)
4 answers
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.
Ver 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.
Mientras que la vectorización y otras micro-optimizaciones pueden mejorar la velocidad de la computación, no pueden aumentar la velocidad de su memoria.
En su ejemplo:
for(k = 0; k < LEN; k++)
c[k] = a[k] * b[k];
Estás haciendo una sola pasada sobre toda la memoria haciendo muy poco trabajo. Esto está maximizando el ancho de banda de tu memoria.
Así que independientemente de cómo se optimice, (vectorizado, desenrollado, etc... no va a ser mucho más rápido.
Una máquina de escritorio típica de 2013 tiene en el orden de 10 GB/s de ancho de banda de memoria*.
El bucle toca 24 bytes/iteración.
Sin vectorización, un procesador x64 moderno puede probablemente hacer alrededor de 1 iteración un ciclo*.
Supongamos que estás corriendo 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 anteriormente 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 de 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 la caché.
(Probé esto en C++ ya que era más fácil. Pero no hay 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 @ 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 ciclos -
27,510,000,000 / 25,600,000,000= 1.074 ciclos/iteración
Ahora, si te preguntas cómo es posible hacerlo:
- 2 cargas
- 1 tienda
- 1 multiplicar
- contador de incrementos
- comparar + rama
Todo en un ciclo...
Es porque los procesadores y compiladores modernos son impresionantes.
Mientras que cada una de estas operaciones tienen latencia (especialmente la multiplicación), el procesador es capaz de ejecute varias iteraciones al mismo tiempo. Mi máquina de prueba es un procesador Sandy Bridge, que es capaz de soportar cargas de 2x128b, 1x128b store y 1x256b vector FP multiplique cada ciclo. Y potencialmente otro uno o dos vector o entero ops, si las cargas son operandos fuente de memoria para uops micro-fusionados. (2 cargas + 1 almacenar el rendimiento solo cuando se utiliza 256b AVX cargas / tiendas, de lo contrario solo dos ops de memoria total por ciclo (a lo sumo una tienda)).
Mirando a la asamblea (que omitiré por brevedad), parece que el compilador desenrolló el bucle, reduciendo así la sobrecarga de bucle. Pero no se las arregló para vectorizarlo.
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 @ 4.2 GHz
- Compilador: Visual Studio 2012
- Tiempo: 5.811 segundos
Así que toma mi máquina 5.811 segundos para escribir a 100 GB de memoria. Eso es alrededor de 17.2 GB/s.
Y mi procesador está en el extremo superior. Los procesadores de la generación Nehalem y Core 2 tienen menos ancho de banda de memoria.
Actualización de Marzo 2017:
A partir de 2017, las cosas se han vuelto más complicadas.
Gracias a la memoria DDR4 y 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. A pesar de que el ancho de banda ha aumentado, los núcleos del procesador también han mejorado, y hay más de ellos.
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 antiguos,
X > Y. - En los sistemas actuales de gama alta,
X < Y. PeroX * (# of cores) > Y.
De vuelta en 2013: Sandy Bridge a 4 GHz + DDR3 de doble canal a 1333 MHz
- No vectorización (carga/almacenes de 8 bytes):
X = 32 GB/syY = ~17 GB/s - SSE vectorizado* (carga/almacenes de 16 bytes):
X = 64 GB/syY = ~17 GB/s
Ahora en 2017: Haswell-E @ 4 GHz + DDR4 de cuatro canales @ 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 caché limitarán el ancho de banda a aproximadamente 16 bytes / ciclo independientemente del ancho SIMD.)
Así que hoy en día, un solo hilo no siempre será capaz de saturar el ancho de banda de la memoria. Y tendrá que vectorizar para lograr ese límite de X. Pero todavía 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á por mucho tiempo: No podrá ejecutar un bucle de acaparamiento de ancho de banda en todos los núcleos sin saturar el total ancho de banda de memoria.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-03-31 19:07:15
EDITAR: Se modificó mucho la respuesta . Además, por favor ignore la mayor parte de lo que escribí antes acerca de que la respuesta de Mystical no es del todo correcta. Sin embargo, todavía no estoy de acuerdo en que esté atascado por la memoria, ya que a pesar de hacer una gran variedad de pruebas, no pude ver ningún signo de que el código original estuviera limitado por la velocidad de la memoria. Mientras tanto, seguía mostrando signos claros de estar limitado a la CPU.
Puede haber muchas razones. Y dado que la razón [s] puede ser muy dependiente del hardware, I decidí que no debía especular sobre la base de conjeturas. Solo voy a esbozar estas cosas que encontré durante las pruebas posteriores, donde utilicé un método de medición de tiempo de CPU mucho más preciso y confiable y un bucle de bucle 1000 veces. Creo que esta información podría ser de ayuda. Pero por favor tómelo con un grano de sal, ya que depende del hardware.
- Al usar instrucciones de la familia SSE, el código vectorizado que obtuve fue un 10% más rápido que el código no vectorizado.
- Código vectorizado usando la familia SSE y el código vectorizado usando AVX se ejecutó más o menos con el mismo rendimiento.
- Al usar instrucciones AVX, el código no vectorizado corrió más rápido-25% o más rápido que cualquier otra cosa que probé.
- Los resultados se escalan linealmente con el reloj de la CPU en todos los casos.
- Los resultados apenas se vieron afectados por el reloj de memoria.
- Los resultados se vieron considerablemente afectados por la latencia de la memoria, mucho más que el reloj de memoria, pero no tanto como el reloj de la CPU afectó al resultado.
El ejemplo de WRT Mystical de ejecutar casi 1 iteración por reloj - No esperaba que el programador de CPU fuera tan eficiente y estaba asumiendo 1 iteración cada 1.5-2 ticks de reloj. Pero para mi sorpresa, ese no es el caso; estoy seguro de que estaba equivocado, lo siento por eso. Mi propia CPU lo ejecutó aún más eficientemente - 1.048 ciclos/iteración. Así que puedo dar fe de que esta parte de la respuesta de Mystical es definitivamente correcta.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-08-11 02:53:12
Como Mysticial ya ha descrito, las limitaciones de ancho de banda de la memoria principal son el cuello de botella para los búferes grandes aquí. La forma de evitar esto es rediseñar su procesamiento para que funcione en trozos que quepan en la caché. (En lugar de multiplicar un total de 200MiB de dobles, multiplicar sólo 128kiB, a continuación, hacer algo con eso. Así que el código que utiliza la salida de la multiplicación lo encontrará todavía en caché L2. L2 es típicamente 256kiB, y es privado para cada núcleo de CPU, en diseños recientes de Intel.)
Esto la técnica se llama bloqueo de caché, o mosaico de bucles. Puede ser complicado para algunos algoritmos, pero la recompensa es la diferencia entre el ancho de banda de la caché L2 vs.el ancho de banda de la memoria principal.
Si hace esto, asegúrese de que el compilador no siga generando tiendas de streaming (movnt...). Esas escrituras omiten las cachés para evitar contaminarlo con datos que no encajan. La siguiente lectura de esos datos tendrá que tocar la memoria principal.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2015-07-05 03:12:45
Por si acaso a [] b [] y c [] están luchando por la caché L2::
#include <string.h> /* for memcpy */
...
gettimeofday(&stTime, NULL);
for(k = 0; k < LEN; k += 4) {
double a4[4], b4[4], c4[4];
memcpy(a4,a+k, sizeof a4);
memcpy(b4,b+k, sizeof b4);
c4[0] = a4[0] * b4[0];
c4[1] = a4[1] * b4[1];
c4[2] = a4[2] * b4[2];
c4[3] = a4[3] * b4[3];
memcpy(c+k,c4, sizeof c4);
}
gettimeofday(&endTime, NULL);
Reduce el tiempo de ejecución de 98429.000000 a 67213.000000; desenrollar el bucle 8 veces lo reduce a 57157.000000 aquí.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-08-10 14:09:06