terror - ¿Por qué vectorizar el bucle no tiene mejora de rendimiento?

sin simpson (4)

Como Mysticial ya se describió, las limitaciones de ancho de banda de la memoria principal son el cuello de botella para los grandes buffers aquí. La forma de evitar esto es rediseñar su procesamiento para que funcione en trozos que encajan en el caché. (En lugar de multiplicar un total de 200MiB de dobles, multiplique solo 128kiB, luego haga algo con eso. Así que el código que usa la salida de la multiplicación lo encontrará aún en la memoria caché L2. L2 es típicamente 256kiB, y es privado para cada núcleo de CPU , en diseños recientes de Intel.)

Esta técnica se llama bloqueo de caché o mosaico de bucle . Puede ser complicado para algunos algoritmos, pero la recompensa es la diferencia entre el ancho de banda del caché L2 y el ancho de banda de la memoria principal.

Si haces esto, asegúrate de que el compilador no genere tiendas de transmisión ( movnt... ). Esas escrituras omiten los cachés para evitar contaminarlos con datos que no encajan. La siguiente lectura de esos datos deberá tocar la memoria principal.

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 más me interesa 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 mejora en el rendimiento cuando el ciclo se vectoriza.

Puede que me haya perdido algo aquí porque no estoy muy familiarizado con el tema. Por favor, avíseme si hay algún problema con mi código.

Gracias de antemano por tu ayuda.

PD: estoy usando Mac OSX, por lo que no es necesario alinear los datos, ya que todas las memorias asignadas están alineadas con 16 bytes.

Edit: Primero quisiera 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 sea más pequeño que LEN , hay otras cosas que se deben hacer para realizar la operación. Mirando el 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 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). Lo que es más importante, dado que la memoria requerida para a , b y c es contigua, el captador previo definitivamente ayudaría mucho y cargaría los siguientes bloques por adelantado. Habiendo dicho eso, 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 la Guía de Vectorización Intel . Por lo tanto, parece que deberíamos poder obtener alguna mejora en el rendimiento para este bucle muy simple.

Edit2: Gracias de nuevo por sus comentarios. Además, gracias al código de ejemplo de @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. Al elegir un tamaño pequeño para a , b y c que se ajuste a la caché L1, se puede ver que SIMD puede ayudar a mejorar el rendimiento de manera significativa. 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 lazo mejora el rendimiento aún más:

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

Además, debo mencionar que solo hace falta un ciclo para que mi procesador complete una iteración cuando se compila con -O2 .

PD: Mi computadora es un Macbook Pro Core i5 @ 2.5GHz (doble núcleo)

EDITAR: Modificó la respuesta mucho . Además, ignore la mayor parte de lo que escribí antes sobre la respuesta de Mystical que no es del todo correcta. Sin embargo, aún no estoy de acuerdo con que la memoria lo obstaculice, ya que, a pesar de realizar una gran variedad de pruebas, no pude ver ninguna señal de que el código original esté vinculado por la velocidad de la memoria. Mientras tanto, seguía mostrando signos claros de estar vinculado a la CPU.

Puede haber muchas razones. Y dado que la razón [s] puede ser muy dependiente del hardware, decidí que no debería especular sobre la base de conjeturas. Solo voy a resumir estas cosas que encontré durante las pruebas posteriores, donde utilicé un método de medición del tiempo de la CPU mucho más preciso y confiable y el looping the loop 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 más de 10% más rápido que el código no vectorizado.
El código vectorizado que utiliza la familia SSE y el código vectorizado que usa AVX se ejecutaron más o menos con el mismo rendimiento.
Cuando usé las 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 escalaron linealmente con el reloj de la CPU en todos los casos.
Los resultados fueron apenas 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ó los resultados.

El ejemplo de WRT Mystical de ejecutar casi 1 iteración por reloj: no esperaba que el programador de la CPU fuera tan eficiente y asumía 1 iteración cada 1.5-2 tics de reloj. Pero para mi sorpresa, ese no es el caso; Seguro 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 tiene toda la razón.

En caso de que a [] b [] yc [] luchen 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 funcionamiento de 98429.000000 a 67213.000000; Desenrollar el bucle 8 veces lo reduce a 57157.000000 aquí.

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.

Vea el final de esta respuesta para la actualización de 2017.

Respuesta original (2013):

Porque estás estancado por el ancho de banda de la memoria.

Si bien la vectorización y otras micro optimizaciones pueden mejorar la velocidad de computación, 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 una sola pasada sobre toda la memoria haciendo muy poco trabajo. Esto es maximizar el ancho de banda de su memoria.

Así que, 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 un orden de 10 GB / s de ancho de banda de memoria *.
Su ciclo toca 24 bytes / iteración .

Sin vectorización, un procesador x64 moderno probablemente puede hacer alrededor de 1 iteración por 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 de sorprender que algunas personas dudaran de los números que di anteriormente ya que no mencioné nada. 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 el LEN para que encaje en el 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 ciclos
27,510,000,000 / 25,600,000,000 = 1.074 ciclos / iteración

Ahora si te estás preguntando cómo es posible hacer:

2 cargas
1 tienda
1 multiplica
contador de incremento
comparar + rama

todo en un ciclo ...

Es porque los procesadores y compiladores modernos son impresionantes.

Si bien cada una de estas operaciones tiene una latencia (especialmente la multiplicación), el procesador puede ejecutar varias iteraciones al mismo tiempo. Mi máquina de prueba es un procesador Sandy Bridge, que es capaz de soportar cargas de 2x128b, una tienda de 1x128b y un multiplicador FP de 1x256b 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 la tienda solo cuando se utilizan 256b cargas / almacenes AVX; de lo contrario, solo dos operaciones de memoria totales por ciclo (como máximo, una tienda)).

Al mirar el conjunto (que omitiré por brevedad), parece que el compilador desenrolló el ciclo, lo que reduce la sobrecarga de bucle. Pero no logró llegar a 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

Entonces mi máquina tarda 5.811 segundos en 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. 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 ponerlo 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 . Pero X * (# of cores) > Y

En 2013: Sandy Bridge a 4 GHz + doble canal DDR3 a 1333 MHz

Sin vectorización (carga / almacenamiento de 8 bytes): X = 32 GB/s Y = ~17 GB/s
SSE vectorizado * (carga / almacenamiento de 16 bytes): X = 64 GB/s e Y = ~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/s Y = ~70 GB/s
AVX * vectorizado (carga / almacenamiento de 32 bytes): X = 64 GB/s e Y = ~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 aproximadamente 16 bytes / ciclo independientemente del ancho SIMD).}

Así que hoy en día, un solo hilo no siempre podrá saturar el ancho de banda de la memoria. Y necesitarás vectorizar para alcanzar 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 lo hará por mucho tiempo: no podrá ejecutar un bucle de ancho de banda en todos los núcleos sin saturar el ancho de banda total de la memoria.