Por qué vectorizar el bucle no mejora el rendimiento

Estoy investigando el efecto de la vectorización en el rendimiento del progtwig. En este sentido, he escrito el siguiente código:

#include  #include  #include  #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 ciclo:

 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í ya que no estoy muy familiarizado con el tema. Por lo tanto, 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 a 16 bytes.

Editar: me gustaría primero agradecerles a todos 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 se menciona @Vinska, c[k]=a[k]*b[k] no toma solo un ciclo. Además del incremento del índice del ciclo y la comparación realizada para asegurar que k sea ​​menor que LEN , hay otras cosas que se deben hacer para realizar la operación. Al observar el código de ensamblado generado por el comstackdor, 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 progtwig para una adición muy simple se menciona en la Guía de Vectorización de Intel . Por lo tanto, parece que deberíamos ser capaces de 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 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. 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. 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 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 comstack con -O2 .

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

Esta respuesta original fue válida en 2013. A partir de hardware 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 2017.


Respuesta original (2013):

Porque estás embotellado 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 boost 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 está maximizando el ancho de banda de tu memoria.

Por lo tanto, 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 *.
Su ciclo toca 24 bytes / iteración .

Sin vectorización, un procesador x64 moderno probablemente pueda hacer alrededor de 1 iteración por ciclo *.

Supongamos que está ejecutando a 4 GHz:

  • (4 * 10^9) * 24 bytes/iteration = 96 GB/s

Eso es casi 10 veces más ancho de banda de 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, ésos estaban fuera de mi cabeza por experiencia. Así que aquí hay algunos puntos de referencia para probarlo.

La iteración del ciclo 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 diferencia).

 #include  #include  
  • Procesador: Intel Core i7 2600K a 4.2 GHz
  • Comstackdor: Visual Studio 2012
  • Tiempo: 6.55 segundos

En esta prueba, ejecuté 25,600,000,000 de 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 multiplicar
  • contador de incremento
  • comparar + twig

todo en un ciclo ...

Es porque los procesadores y comstackdores modernos son impresionantes.

Mientras que 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, una tienda de 1x128b y un multiplicador FP de 1x256b cada ciclo. Y potencialmente otra o más operaciones vector o entero, 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 comstackdor desenrolló el ciclo, lo que reduce la sobrecarga de bucle. Pero no logró 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  #include  
  • Procesador: Intel Core i7 2600K a 4.2 GHz
  • Comstackdor: 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 único 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 más antiguos, X > Y
  • En los sistemas actuales de alta gama, X < Y . Pero X * (# of cores) > Y

Ya en 2013: Sandy Bridge @ 4 GHz + DDR3 de doble canal 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 Y = ~17 GB/s

Ahora en 2017: Haswell-E @ 4 GHz + quad-channel DDR4 @ 2400 MHz

  • Sin vectorización (carga / almacenamiento de 8 bytes): X = 32 GB/s Y = ~70 GB/s
  • Vectorizado AVX * (carga / almacenamiento de 32 bytes): X = 64 GB/s 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).

Entonces, 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 cambiará durante mucho tiempo: no podrá ejecutar un bucle de ancho de banda en todos los núcleos sin saturar el ancho de banda de la memoria total.

EDITAR: Modificó la respuesta mucho . Además, ignore la mayoría de lo que escribí antes sobre que la respuesta de Mystical no es del todo correcta. Sin embargo, todavía no estoy de acuerdo con que esté embotellado por la memoria, ya que a pesar de hacer una gran variedad de pruebas, no pude ver ninguna señal de que el código original estuviera limitado 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 usando SSE-family y el código vectorizado usando AVX funcionó 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 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ó los resultados.

Ejemplo de WRT Mystical de ejecutar casi 1 iteración por reloj: no esperaba que el progtwigdor de la CPU fuera tan eficiente y suponía 1 iteración cada 1.5-2 tics 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 . Entonces puedo dar fe de que esta parte de la respuesta de Mystical es definitivamente correcta.

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 solución a esto es rediseñar su procesamiento para que funcione en fragmentos que se ajustan a la memoria caché. (En lugar de multiplicar un total de 200MiB de dobles, multiplique solo 128kiB, luego haga algo con eso. Por lo tanto, el código que usa la salida del multiplicador lo encontrará aún en 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 locking de caché o mosaico de bucles . Puede ser complicado para algunos algoritmos, pero la recompensa es la diferencia entre el ancho de banda de caché L2 y el ancho de banda de la memoria principal.

Si hace esto, asegúrese de que el comstackdor aún no esté generando almacenes de transmisión ( movnt... ). Esos escrito omiten las cachés para evitar contaminarlo con datos que no encajarán. La próxima lectura de esos datos deberá tocar la memoria principal.

En caso de que a [] b [] yc [] luchen por la caché L2 ::

 #include  /* 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 lazo 8 veces lo reduce a 57157.000000 aquí.