sumar - suma de vectores en c++
¿Por qué mi caché 8M L3 no proporciona ningún beneficio para arreglos de más de 1M? (3)
Respuesta corta:
Su versión de memset comienza a usar almacenes no temporales al inicializar una región de memoria superior a 1 MB. Como resultado, la CPU no almacena estas líneas en su caché, a pesar de que su caché L3 es más grande que 1 MB. En consecuencia, el rendimiento está limitado por el ancho de banda de memoria disponible en el sistema para valores de búfer superiores a 1 MB.
Detalles:
Fondo:
Probé el código que proporcionaste en varios sistemas diferentes y al principio me centré en investigar el TLB porque pensé que podría haber problemas en el TLB de 2º nivel. Sin embargo, ninguno de los datos que recogí confirmó esa hipótesis.
Algunos de los sistemas que probé utilizaban Arch Linux, que tiene la última versión de glibc, mientras que otros usaban Ubuntu 10.04, que usa una versión anterior de eglibc. Pude reproducir el comportamiento descrito en la pregunta al usar un binario estáticamente vinculado al probar con múltiples arquitecturas de CPU diferentes. El comportamiento en el que me concentré era una diferencia significativa en el tiempo de ejecución entre cuando SIZE_KB era 1024 y cuando era 1025 . La diferencia de rendimiento se explica por un cambio en el código ejecutado para las versiones lentas y rápidas.
Código de la Asamblea
perf record y la perf annotate para recopilar una traza del código de ensamblaje en ejecución para ver cuál era la ruta del código activo. El código se muestra a continuación utilizando el siguiente formato:
percentage time executing instruction | address | instruction percentage time executing instruction | address | instruction
He copiado el bucle activo de la versión más corta que omite la mayor parte de la dirección y tiene una línea que conecta el borde posterior del bucle y el encabezado del bucle.
Para la versión compilada en Arch Linux, el hot loop fue (para los tamaños 1024 y 1025):
2.35 │a0:┌─+movdqa %xmm8,(%rcx)
54.90 │ │ movdqa %xmm8,0x10(%rcx)
32.85 │ │ movdqa %xmm8,0x20(%rcx)
1.73 │ │ movdqa %xmm8,0x30(%rcx)
8.11 │ │ add $0x40,%rcx
0.03 │ │ cmp %rcx,%rdx
│ └──jne a0
Para el binario de Ubuntu 10.04, el bucle activo cuando se ejecuta con un tamaño de 1024 fue:
│a00:┌─+lea -0x80(%r8),%r8
0.01 │ │ cmp $0x80,%r8
5.33 │ │ movdqa %xmm0,(%rdi)
4.67 │ │ movdqa %xmm0,0x10(%rdi)
6.69 │ │ movdqa %xmm0,0x20(%rdi)
31.23 │ │ movdqa %xmm0,0x30(%rdi)
18.35 │ │ movdqa %xmm0,0x40(%rdi)
0.27 │ │ movdqa %xmm0,0x50(%rdi)
3.24 │ │ movdqa %xmm0,0x60(%rdi)
16.36 │ │ movdqa %xmm0,0x70(%rdi)
13.76 │ │ lea 0x80(%rdi),%rdi
│ └──jge a00
Para la versión de Ubuntu 10.04 que se ejecuta con un tamaño de búfer de 1025, el bucle activo fue:
│a60:┌─+lea -0x80(%r8),%r8
0.15 │ │ cmp $0x80,%r8
1.36 │ │ movntd %xmm0,(%rdi)
0.24 │ │ movntd %xmm0,0x10(%rdi)
1.49 │ │ movntd %xmm0,0x20(%rdi)
44.89 │ │ movntd %xmm0,0x30(%rdi)
5.46 │ │ movntd %xmm0,0x40(%rdi)
0.02 │ │ movntd %xmm0,0x50(%rdi)
0.74 │ │ movntd %xmm0,0x60(%rdi)
40.14 │ │ movntd %xmm0,0x70(%rdi)
5.50 │ │ lea 0x80(%rdi),%rdi
│ └──jge a60
La diferencia clave aquí es que la versión más lenta movntd instrucciones de movntd mientras que las versiones más rápidas usaban instrucciones de movdqa . El manual de Intel Software Developers dice lo siguiente sobre las tiendas no temporales:
En particular, para el tipo de memoria WC, el procesador nunca parece leer los datos en la jerarquía de caché. En su lugar, la sugerencia no temporal puede implementarse cargando un búfer interno temporal con el equivalente de una línea de caché alineada sin llenar estos datos en el caché.
Entonces, esto parece explicar el comportamiento donde el memset con valores mayores a 1 MB no cabe en el caché. La siguiente pregunta es por qué hay una diferencia entre el sistema Ubuntu 10.04 y el sistema Arch Linux, y por qué se selecciona 1 MB como punto de corte. Para investigar esa pregunta miré el código fuente de glibc:
Código fuente de memset
Mirando el repositorio de glibc git en sysdeps/x86_64/memset.S el primer compromiso que encontré interesante fue b2b671b677d92429a3d41bf451668f476aa267ed
La descripción de confirmación es:
Memset más rápido en x64
Esta implementación acelera memset de varias maneras. Lo primero es evitar el salto computacional caro. El segundo es el hecho de que los argumentos de memset se alinean la mayor parte del tiempo con 8 bytes.
Resultados de referencia en: kam.mff.cuni.cz/~ondra/benchmark_string/memset_profile_result27_04_13.tar.bz2
Y el sitio web al que se hace referencia tiene algunos datos de perfil interesantes.
La diferencia de la confirmación muestra que el código para memset se simplifica mucho y se eliminan los almacenes no temporales. Esto coincide con lo que muestra el código perfilado de Arch Linux.
Mirando el código anterior , vi que la opción de usar almacenes no temporales parecía hacer uso de un valor descrito como The largest cache size
L(byte32sse2_pre):
mov __x86_shared_cache_size(%rip),%r9d # The largest cache size
cmp %r9,%r8
ja L(sse2_nt_move_pre)
El código para calcular esto está en: sysdeps/x86_64/cacheinfo.c
Aunque parece que hay un código para calcular el tamaño real de la memoria caché compartida, el valor predeterminado también es 1 MB :
long int __x86_64_shared_cache_size attribute_hidden = 1024 * 1024;
Entonces sospecho que se está utilizando el valor predeterminado, pero puede haber alguna otra razón por la que el código esté seleccionando 1MB como punto de corte.
En cualquier caso, la respuesta general a su pregunta parece ser que la versión de memset en su sistema está utilizando almacenes no temporales al configurar una región de memoria mayor a 1 MB.
Esta pregunta me inspiró a escribir un programa simple para probar el ancho de banda de memoria de mi máquina en cada nivel de caché:
¿Por qué vectorizar el bucle no tiene mejora de rendimiento?
Mi código usa memset para escribir en un búfer (o búferes) una y otra vez y mide la velocidad. También guarda la dirección de cada búfer para imprimir al final. Aquí está el listado:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>
#define SIZE_KB {8, 16, 24, 28, 32, 36, 40, 48, 64, 128, 256, 384, 512, 768, 1024, 1025, 2048, 4096, 8192, 16384, 200000}
#define TESTMEM 10000000000 // Approximate, in bytes
#define BUFFERS 1
double timer(void)
{
struct timeval ts;
double ans;
gettimeofday(&ts, NULL);
ans = ts.tv_sec + ts.tv_usec*1.0e-6;
return ans;
}
int main(int argc, char **argv)
{
double *x[BUFFERS];
double t1, t2;
int kbsizes[] = SIZE_KB;
double bandwidth[sizeof(kbsizes)/sizeof(int)];
int iterations[sizeof(kbsizes)/sizeof(int)];
double *address[sizeof(kbsizes)/sizeof(int)][BUFFERS];
int i, j, k;
for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
iterations[k] = TESTMEM/(kbsizes[k]*1024);
for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
{
// Allocate
for (j = 0; j < BUFFERS; j++)
{
x[j] = (double *) malloc(kbsizes[k]*1024);
address[k][j] = x[j];
memset(x[j], 0, kbsizes[k]*1024);
}
// Measure
t1 = timer();
for (i = 0; i < iterations[k]; i++)
{
for (j = 0; j < BUFFERS; j++)
memset(x[j], 0xff, kbsizes[k]*1024);
}
t2 = timer();
bandwidth[k] = (BUFFERS*kbsizes[k]*iterations[k])/1024.0/1024.0/(t2-t1);
// Free
for (j = 0; j < BUFFERS; j++)
free(x[j]);
}
printf("TESTMEM = %ld/n", TESTMEM);
printf("BUFFERS = %d/n", BUFFERS);
printf("Size (kB)/tBandwidth (GB/s)/tIterations/tAddresses/n");
for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
{
printf("%7d/t/t%.2f/t/t/t%d/t/t%x", kbsizes[k], bandwidth[k], iterations[k], address[k][0]);
for (j = 1; j < BUFFERS; j++)
printf(", %x", address[k][j]);
printf("/n");
}
return 0;
}
Y los resultados (con BUFFERS = 1):
TESTMEM = 10000000000
BUFFERS = 1
Size (kB) Bandwidth (GB/s) Iterations Addresses
8 52.79 1220703 90b010
16 56.48 610351 90b010
24 57.01 406901 90b010
28 57.13 348772 90b010
32 45.40 305175 90b010
36 38.11 271267 90b010
40 38.02 244140 90b010
48 38.12 203450 90b010
64 37.51 152587 90b010
128 36.89 76293 90b010
256 35.58 38146 d760f010
384 31.01 25431 d75ef010
512 26.79 19073 d75cf010
768 26.20 12715 d758f010
1024 26.20 9536 d754f010
1025 18.30 9527 90b010
2048 18.29 4768 d744f010
4096 18.29 2384 d724f010
8192 18.31 1192 d6e4f010
16384 18.31 596 d664f010
200000 18.32 48 cb2ff010
Puedo ver fácilmente el efecto de la caché 32K L1 y la caché 256K L2. Lo que no entiendo es por qué el rendimiento cae repentinamente después de que el tamaño del búfer de memset supera el 1M. Mi caché L3 se supone que es 8M. Sucede tan repentinamente también, no se reduce en absoluto como cuando se superó el tamaño de caché L1 y L2.
Mi procesador es el Intel i7 3700. Los detalles de la caché L3 de / sys / devices / system / cpu / cpu0 / cache son:
level = 3
coherency_line_size = 64
number_of_sets = 8192
physical_line_partition = 1
shared_cpu_list = 0-7
shared_cpu_map = ff
size = 8192K
type = Unified
ways_of_associativity = 16
Pensé que intentaría usar varios búferes - llame a memset en 2 búferes de 1M cada uno y vea si el rendimiento bajaría. Con BUFFERS = 2, obtengo:
TESTMEM = 10000000000
BUFFERS = 2
Size (kB) Bandwidth (GB/s) Iterations Addresses
8 54.15 1220703 e59010, e5b020
16 51.52 610351 e59010, e5d020
24 38.94 406901 e59010, e5f020
28 38.53 348772 e59010, e60020
32 38.31 305175 e59010, e61020
36 38.29 271267 e59010, e62020
40 38.29 244140 e59010, e63020
48 37.46 203450 e59010, e65020
64 36.93 152587 e59010, e69020
128 35.67 76293 e59010, 63769010
256 27.21 38146 63724010, 636e3010
384 26.26 25431 63704010, 636a3010
512 26.19 19073 636e4010, 63663010
768 26.20 12715 636a4010, 635e3010
1024 26.16 9536 63664010, 63563010
1025 18.29 9527 e59010, f59420
2048 18.23 4768 63564010, 63363010
4096 18.27 2384 63364010, 62f63010
8192 18.29 1192 62f64010, 62763010
16384 18.31 596 62764010, 61763010
200000 18.31 48 57414010, 4b0c3010
Parece que ambos buffers 1M permanecen en el caché L3. Pero intente aumentar el tamaño de cada búfer ligeramente y el rendimiento se reducirá.
He estado compilando con -O3. No hace mucha diferencia (excepto posiblemente desenrollar los bucles sobre BUFFERS). Intenté con -O0 y es lo mismo, excepto para las velocidades de L1. La versión de gcc es 4.9.1.
Para resumir, tengo una pregunta de 2 partes:
- ¿Por qué mi caché de 8 MB L3 no proporciona ningún beneficio en bloques de memoria de más de 1M?
- ¿Por qué la caída en el rendimiento es tan repentina?
EDITAR:
Según lo sugerido por Gabriel Southern , ejecuté mi código con perf usando BUFFERS = 1 con solo un tamaño de búfer a la vez. Este fue el comando completo:
perf stat -e dTLB-loads,dTLB-load-misses,dTLB-stores,dTLB-store-misses -r 100 ./a.out 2> perfout.txt
La -r significa que perf se ejecutará 100 veces y devolverá las estadísticas promedio.
La salida de perf , con #define SIZE_KB {1024} :
Performance counter stats for ''./a.out'' (100 runs):
1,508,798 dTLB-loads ( +- 0.02% )
0 dTLB-load-misses # 0.00% of all dTLB cache hits
625,967,550 dTLB-stores ( +- 0.00% )
1,503 dTLB-store-misses ( +- 0.79% )
0.360471583 seconds time elapsed ( +- 0.79% )
y con #define SIZE_KB {1025} :
Performance counter stats for ''./a.out'' (100 runs):
1,670,402 dTLB-loads ( +- 0.09% )
0 dTLB-load-misses # 0.00% of all dTLB cache hits
626,099,850 dTLB-stores ( +- 0.00% )
2,115 dTLB-store-misses ( +- 2.19% )
0.503913416 seconds time elapsed ( +- 0.06% )
Por lo tanto, parece que hay más errores de TLB con el búfer 1025K. Sin embargo, con este tamaño de búfer, el programa hace aproximadamente 9500 llamadas de memset , por lo que todavía es menos de 1 error por llamada memset .
Dado el desmontaje de Gabriel del código de ensamblaje generado, creo que este es el problema [ Editar: su respuesta fue editada, ahora aparece como la causa raíz, por lo que estamos de acuerdo ]:
Tenga en cuenta que movnt es una tienda de transmisión, que puede tener (dependiendo de la implementación exacta de micro-arquitectura) varios impactos:
- Tiene una semántica de ordenamiento débil (lo que le permite ser más rápido).
- Ha mejorado la latencia si sobrescribe una línea completa (no es necesario recuperar los datos anteriores y combinarlos).
- Tiene un indicio no temporal, lo que lo hace incomparable.
Los números 1 y 2 pueden mejorar la latencia y el ancho de banda de estas operaciones si están vinculados a la memoria, pero el número 3 básicamente los obliga a estar vinculados a la memoria, incluso si pueden entrar en algún nivel de caché. Esto probablemente supera los beneficios, ya que la latencia de la memoria / BW son significativamente peores para empezar.
Por lo tanto, la implementación de la biblioteca memset probablemente esté utilizando un umbral incorrecto para cambiar a la versión de tiendas de transmisión (supongo que no se molesta en verificar el tamaño de su LLC, pero suponiendo que 1M es residente de memoria es bastante extraño). Sugiero probar bibliotecas alternativas, o desactivar la capacidad del compilador para generarlas (si es compatible).
Su punto de referencia solo se escribe en la memoria, nunca se lee, se usa memset, que probablemente esté inteligentemente diseñado para no leer nada, desde la memoria caché a la memoria. Es muy posible que con este código, donde solo se utiliza la mitad de la capacidad de la memoria caché, no haya un aumento de rendimiento en comparación con la memoria en bruto. El hecho de que escribir en memoria bruta sea bastante cercano a la velocidad L2 puede ser una pista. Si L2 se ejecuta a 26 GB / seg, la memoria principal a 18 GB / seg, ¿qué puede esperar realmente del caché L3?
Usted está midiendo el rendimiento, no la latencia. Probaría un punto de referencia en el que realmente usas la fuerza de la memoria caché L3, proporcionando datos con menor latencia que la memoria principal.