sumar - suma de vectores en c++

¿Por qué mi caché 8M L3 no proporciona ningún beneficio para arreglos de más de 1M?

Question

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:

1. ¿Por qué mi caché de 8 MB L3 no proporciona ningún beneficio en bloques de memoria de más de 1M?
2. ¿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 .

Answer 1

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.

Answer 2

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:

1. Tiene una semántica de ordenamiento débil (lo que le permite ser más rápido).
2. Ha mejorado la latencia si sobrescribe una línea completa (no es necesario recuperar los datos anteriores y combinarlos).
3. 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).

Answer 3

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.