performance - Acceso a la memoria Haswell

x86 cpu-architecture

Question

Estaba experimentando con conjuntos de instrucciones AVX -AVX2 para ver el rendimiento de la transmisión en matrices consecutivas. Así que tengo el siguiente ejemplo, donde hago memoria básica de lectura y almacenamiento.

#include <iostream>
#include <string.h>
#include <immintrin.h>
#include <chrono>
const uint64_t BENCHMARK_SIZE = 5000;

typedef struct alignas(32) data_t {
  double a[BENCHMARK_SIZE];
  double c[BENCHMARK_SIZE];
  alignas(32) double b[BENCHMARK_SIZE];
}
data;

int main() {
  data myData;
  memset(&myData, 0, sizeof(data_t));

  auto start = std::chrono::high_resolution_clock::now();

  for (auto i = 0; i < std::micro::den; i++) {
    for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) {
      myData.b[i] = myData.a[i] + 1;
    }
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << (end - start).count() / std::micro::den << " " << myData.b[1]
            << std::endl;
}

Y después de compilar con g ++ - 4.9 -ggdb -march = core-avx2 -std = c ++ 11 struct_of_arrays.cpp -O3 -o struct_of_arrays

Veo una buena instrucción por tiempo de ciclo y tiempos, para el tamaño de referencia 4000. Sin embargo, una vez que aumente el tamaño de referencia a 5000, veo que la instrucción por ciclo disminuye significativamente y también los saltos de latencia. Ahora mi pregunta es, aunque puedo ver que la degradación del rendimiento parece estar relacionada con el caché L1, no puedo explicar por qué esto sucede tan repentinamente.

Para dar más información, si ejecuto perf con Benchmark tamaño 4000 y 5000

| Event                               | Size=4000 | Size=5000 |
|-------------------------------------+-----------+-----------|
| Time                                |    245 ns |    950 ns |
| L1 load hit                         |    525881 |    527210 |
| L1 Load miss                        |     16689 |     21331 |
| L1D writebacks that access L2 cache |   1172328 | 623710387 |
| L1D Data line replacements          |   1423213 | 624753092 |

Entonces, mi pregunta es: ¿por qué ocurre este impacto, considerando que haswell debería ser capaz de entregar 2 * 32 bytes para leer, y 32 bytes almacenados en cada ciclo?

EDITAR 1

Me di cuenta de que con este código, gcc elimina de forma inteligente los accesos a myData.a, ya que se establece en 0. Para evitar esto, realicé otro punto de referencia que es ligeramente diferente, donde a se establece explícitamente.

#include <iostream>
#include <string.h>
#include <immintrin.h>
#include <chrono>
const uint64_t BENCHMARK_SIZE = 4000;

typedef struct alignas(64) data_t {
  double a[BENCHMARK_SIZE];
  alignas(32) double c[BENCHMARK_SIZE];

  alignas(32) double b[BENCHMARK_SIZE];

}
data;

int main() {
  data myData;
  memset(&myData, 0, sizeof(data_t));
  std::cout << sizeof(data) << std::endl;
  std::cout << sizeof(myData.a) << " cache lines " << sizeof(myData.a) / 64
            << std::endl;
  for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) {
    myData.b[i] = 0;
    myData.a[i] = 1;
    myData.c[i] = 2;
  }

  auto start = std::chrono::high_resolution_clock::now();
  for (auto i = 0; i < std::micro::den; i++) {
    for (uint64_t i = 0; i < BENCHMARK_SIZE; i += 1) {
      myData.b[i] = myData.a[i] + 1;  
    }
  }
  auto end = std::chrono::high_resolution_clock::now();
  std::cout << (end - start).count() / std::micro::den << " " << myData.b[1]
            << std::endl;
}

El segundo ejemplo tendrá una matriz que se está leyendo y otra matriz que se está escribiendo. Y este produce la siguiente salida de perf para diferentes tamaños:

| Event          | Size=1000   | Size=2000   | Size=3000   | Size=4000     |
|----------------+-------------+-------------+-------------+---------------|
| Time           | 86  ns      | 166 ns      | 734 ns      | 931    ns     |
| L1 load hit    | 252,807,410 | 494,765,803 | 9,335,692   | 9,878,121     |
| L1 load miss   | 24,931      | 585,891     | 370,834,983 | 495,678,895   |
| L2 load hit    | 16,274      | 361,196     | 371,128,643 | 495,554,002   |
| L2 load miss   | 9,589       | 11,586      | 18,240      | 40,147        |
| L1D wb acc. L2 | 9,121       | 771,073     | 374,957,848 | 500,066,160   |
| L1D repl.      | 19,335      | 1,834,100   | 751,189,826 | 1,000,053,544 |

Nuevamente, el mismo patrón se ve como se señala en la respuesta, al aumentar el tamaño del conjunto de datos, los datos ya no caben en L1 y L2 se convierte en un cuello de botella. Lo que también es interesante es que la captación previa no parece estar ayudando y L1 aumenta considerablemente. Sin embargo, esperaría ver al menos un 50 por ciento de tasa de aciertos, considerando que cada línea de caché traída a L1 para lectura será un acierto para el segundo acceso (la línea de 64 bytes de 32 bytes se lee con cada iteración). Sin embargo, una vez que el conjunto de datos se derrama a L2, parece que la tasa de aciertos de L1 se reduce al 2%. Teniendo en cuenta que las matrices no se superponen realmente con el tamaño de caché L1, esto no debería ser debido a conflictos de caché. Así que esta parte todavía no tiene sentido para mí.

Answer 1

También estoy en Haswell, pero no puedo reproducir los mismos resultados. ¿Estás seguro de que utilizaste los eventos de rendimiento adecuados? Tenía la curiosidad de seguir investigando y perfilar el código yo mismo. Pero primero, determinemos el número esperado de cargas y almacenes simplemente analizando el código de forma estática y luego comparemos con los números que tenemos para ver si tienen sentido. Estás utilizando gcc 4.9. Este es el código de ensamblaje que se emite para el nido de bucle usando -march=core-avx2 -O3 :

  4007a8:   48 8d 85 d0 2a fe ff    lea    -0x1d530(%rbp),%rax
  4007af:   90                      nop
  4007b0:   c5 f5 58 00             vaddpd (%rax),%ymm1,%ymm0
  4007b4:   48 83 c0 20             add    $0x20,%rax
  4007b8:   c5 fd 29 80 60 38 01    vmovapd %ymm0,0x13860(%rax)
  4007bf:   00 
  4007c0:   48 39 c2                cmp    %rax,%rdx
  4007c3:   75 eb                   jne    4007b0 <main+0x50>
  4007c5:   83 e9 01                sub    $0x1,%ecx
  4007c8:   75 de                   jne    4007a8 <main+0x48>

Hay exactamente un uop de carga de 32 bytes alineado y un uop de almacenamiento de 32 bytes alineado por iteración de bucle interno. El recuento del viaje del bucle externo es de 1 millón. El recuento de disparo del bucle interno es BENCHMARK_SIZE / 4 (debido a la vectorización). Por lo tanto, el número total de solicitudes de carga al L1 debería ser de aproximadamente 1 millón * BENCHMARK_SIZE / 4 y el número total de tiendas también debería ser aproximadamente el mismo. Por ejemplo, si BENCHMARK_SIZE es 4000, entonces el número de solicitudes de carga y almacenamiento debe ser de 1 billón cada uno. Las ramas del bucle son muy predecibles, por lo que no tenemos que preocuparnos por las cargas especulativas no retiradas y las recuperaciones de código.

Recuerde que la L1D en Haswell tiene dos puertos de carga de 32 bytes y un puerto de almacenamiento de 32 bytes. La siguiente gráfica muestra lo que obtuve usando perf . Tenga en cuenta que tanto L1D como L2 prefetchers estaban habilitados cuando tomé estas medidas. Hyperthreading se deshabilitó para eliminar posibles perturbaciones y hacer uso de los otros 4 contadores de rendimiento programables.

Lo primero que se puede observar es que el número de cargas ( MEM_UOPS_RETIRED.ALL_LOADS ) y tiendas ( MEM_UOPS_RETIRED.ALL_STORES ) coincide con nuestro análisis estático. Eso es genial. Pero la primera observación crítica es que el número de aciertos de carga MEM_LOAD_UOPS_RETIRED.L1_HIT ( MEM_LOAD_UOPS_RETIRED.L1_HIT ) está muy cerca del número de cargas L1D. Esto significa que el prefetcher de transmisión de L1D fue capaz de obtener la mayoría de los myData.a[i] manera oportuna. Obviamente, el número de fallas de carga MEM_LOAD_UOPS_RETIRED.L1_MISS ( MEM_LOAD_UOPS_RETIRED.L1_MISS ) debe ser muy pequeño. Esto es válido para todos los valores de BENCHMARK_SIZE .

L1D_PEND_MISS.REQUEST_FB_FULL nos informa el número de ciclos en los que una carga de demanda o un pedido o una solicitud de captación previa de software faltó a la L1D pero no se pudieron emitir desde el búfer de carga / almacenamiento porque no había disponible un búfer de relleno. Esto parece ser un problema significativo. Sin embargo, este evento no nos permite determinar si las cargas, las tiendas o ambas se están bloqueando. Hay otro evento para eso como lo discutiré en breve. Este recuento de eventos es insignificante cuando BENCHMARK_SIZE es 2000 o menos porque después de la primera iteración del bucle interno, todas las cargas y almacenes posteriores se almacenarán en el caché, eliminando la necesidad de buffers de relleno.

L2_TRANS.RFO cuenta el número de solicitudes de RFO que acceden al L2. Si observa detenidamente el gráfico, verá que esto parece ser un poco menos de la mitad del número total de tiendas uops. Esto tiene sentido porque cada dos uops de tienda consecutivos están en la misma línea de caché. Por lo tanto, si uno omite el L1D, el otro fallará y se combinará en escritura en la misma entrada LFB y también se aplastará dentro de la misma solicitud de RFO al L2. No sé por qué L2_TRANS.RFO no es exactamente la mitad de MEM_UOPS_RETIRED.ALL_STORES (como esperaba para los casos en los que BENCHMARK_SIZE > 2000).

L2_RQSTS.ALL_DEMAND_DATA_RD , de acuerdo con el manual, se supone que cuenta el número de cargas de datos de demanda de L1 y el número de solicitudes de L2_RQSTS.ALL_DEMAND_DATA_RD de L1 a L2. Pero es muy pequeño. Creo que solo cuenta el número de cargas de datos de demanda o quizás el prefetcher de transmisión de L1 puede comunicarse directamente con el L3. De todos modos, esto no es importante para este análisis.

De ese gráfico podemos concluir que las solicitudes de carga no están en la ruta crítica, pero sí las solicitudes de almacenamiento. El siguiente paso es, obviamente, medir RESOURCE_STALLS.SB para determinar qué tanto están sufriendo realmente las tiendas. Este evento cuenta el número de ciclos de bloqueo de asignación total debido a un almacenamiento intermedio de almacenamiento completo.

(los cycles en la gráfica se refieren a ciclos de núcleo no inhalados, que es básicamente el tiempo de ejecución).

El gráfico muestra que más del 60% del tiempo de ejecución se desperdicia en el asignador en espera de que una entrada de búfer de tienda se libere. ¿Por qué está pasando esto? Tanto los prefetchers L1D solo rastrean las solicitudes de carga y las líneas de captación en el estado de coherencia S o E. Si las cargas y los almacenes están en las mismas líneas de caché y ningún otro núcleo tiene una copia compartida de las líneas, entonces el transmisor L1 buscará previamente las líneas en el estado E, beneficiando efectivamente tanto a las cargas como a los almacenes. Pero en nuestro ejemplo, las tiendas están en diferentes líneas de caché, y estas no son rastreadas por ninguno de los solicitadores de L1D. Los LFB combinados de escritura ayudan mucho, pero el bucle estrecho abruma al controlador L1D y hace que se arrodille, suplicando a la unidad de almacenamiento / almacenamiento de la unidad de búfer que deje de emitir más solicitudes de almacenamiento. Sin embargo, aún se pueden emitir solicitudes de carga porque en su mayoría se encuentran en la memoria caché y no necesitan un LFB en ese caso. Por lo tanto, las tiendas se acumularán en el búfer de la tienda hasta que se llene, por lo que se estancará el asignador. Los LFB estarían ocupados en su mayoría de manera competitiva por las fallas de la tienda combinada y las solicitudes del transmisor L1. Por lo tanto, el número de LFB y las entradas del búfer de almacenamiento están en la ruta crítica. El número de puertos de escritura L1D no lo son. Esa ruta crítica surge cuando el tamaño de la matriz que se está almacenando excede la capacidad de la L1D.

Para completar, aquí hay un gráfico que muestra el número de instrucciones retiradas y el tiempo de ejecución en segundos.

@PeterCordes sugirió normalizar las mediciones por el tamaño del problema. El siguiente gráfico representa los recuentos de ciclos de instrucción normalizados para los diferentes valores de BENCHMARK_SIZE ciclos y las instrucciones son unidades diferentes, así que pensé que debería dar a cada uno su propio eje. Pero luego el gráfico parecía dar la ilusión de que el recuento de instrucciones normalizadas varía significativamente, lo que no es, y eso no tendría ningún sentido. Así que he decidido trazar ambos en el mismo eje como se muestra en la gráfica. El IPC y el CPI se pueden observar fácilmente desde este gráfico, lo cual es bueno.

Answer 2

Resumen ejecutivo:
Los diferentes niveles de caché pueden mantener diferentes anchos de banda para la misma carga de trabajo básica, por lo que tener conjuntos de datos de diferentes tamaños puede afectar en gran medida el rendimiento.

Explicación más larga:
No es muy sorprendente teniendo en cuenta que Haswell, según este artículo, por ejemplo, puede

Sostener 2 cargas y 1 tienda por ciclo.

Pero solo se dice que se aplique a la L1. Si sigues leyendo ves que el L2

puede proporcionar una línea 64B completa a la caché de datos o instrucciones en cada ciclo

Ya que necesita una carga y un almacenamiento por iteración, el hecho de que el conjunto de datos resida en el L1 le permitirá disfrutar del ancho de banda de L1 y posiblemente alcanzar un rendimiento de ciclo por iteración, mientras que el conjunto de datos se derrame al L2. obligarte a esperar más tiempo. Esto depende de cuán grande sea el doble en su sistema, pero dado que es más comúnmente de 8 bytes, 4000 * 2 arreglos * 8 bytes = 64k, que excede el tamaño L1 en la mayoría de los sistemas actuales. Sin embargo, Peter Cords sugiere en los comentarios que el código original puede haber optimizado la matriz de datos cero (no estoy convencido, pero es una posibilidad)

Ahora hay dos cosas que suceden una vez que comienzas a pasar al siguiente nivel de caché:

1. L1-writebacks : tenga en cuenta que el artículo no menciona las escrituras que son una penalización adicional que debe pagar en términos de ancho de banda (como se puede ver en su salida de rendimiento, aunque parece un poco pronunciado). Mantener los datos en el L1 significa que no tiene que hacer ningún desalojo en absoluto, mientras que tener algunos datos en el L2 significa que cada línea leída desde L2 tendría que lanzar una línea existente desde el L1, la mitad de los cuales son modificados por Su código y requieren escrituras explícitas. Estas transacciones tendrían que ir más allá de la lectura de los valores de los dos elementos de datos que utiliza por iteración. Recuerde que la tienda también tiene que leer primero los datos antiguos, ya que parte de la línea no se utiliza y requiere fusión.

2. Política de reemplazo de caché : tenga en cuenta que, dado que el caché está configurado como asociativo y es muy probable que use un esquema LRU, y dado que revisa sus matrices en serie, su patrón de uso de caché probablemente estaría llenando la primera forma asociativa, y luego continuando con la segunda. y así sucesivamente: para cuando complete la última forma, si todavía hay datos necesarios en la L2 (en el caso del conjunto de datos más grande), probablemente desalojará todas las líneas de la primera forma ya que son las menos recientes -usado, aunque eso también significa que son los que usarás a continuación. Esa es la desventaja de LRU con conjuntos de datos más grandes que el caché.

Esto explica por qué la caída en el rendimiento es tan repentina, debido a este patrón de acceso, una vez que se excede el tamaño de la memoria caché al menos en el tamaño de una sola manera (1/8 de la memoria caché L1).

Un último comentario acerca de los resultados del rendimiento: se habría esperado que la tasa de aciertos de L1 se redujera a una buena ronda cero para el caso de los 5000 elementos, lo que creo que sí. Sin embargo, la captación previa de HW puede hacer que parezca que aún lo golpeas en la L1 a medida que avanza la lectura de los datos reales. Aún tiene que esperar a que estos prefetches traigan los datos y, lo que es más importante, ya que está midiendo el ancho de banda, siguen teniendo el mismo ancho de banda que las cargas / tiendas reales, pero no son considerados por perf, lo que lo hace creer. Tuviste L1 hits todo el tiempo. Esa es mi mejor suposición, al menos, podría comprobarlo si desactiva los parches previos y vuelve a realizar la medición (parece que estoy dando ese consejo demasiado a menudo, lo siento por ser tan arrastrado).

EDITAR 1 (siguiendo el tuyo)

Gran captura sobre la matriz eliminada, que resuelve el misterio sobre el tamaño doble: de hecho, es de 64 bits, por lo que una matriz de 4000 elementos o 2 matrices de 2000 elementos cada una (después de su corrección) son todo lo que puede caber en la L1 . Ahora el derrame se produce en 3000 elementos. La tasa de aciertos de L1 es baja ahora, ya que L1 no pudo emitir suficientes gestiones previas para correr por delante de tus 2 transmisiones distintas.

En cuanto a la expectativa de que cada carga traería una línea de 64 bytes para 2 iteraciones (veo algo muy interesante), si suma la cantidad de cargas emitidas desde la unidad de memoria (L1 acierta + L1 falla), verá que el caso de 2000 elementos es casi exactamente 2x de los 1000 elementos, pero los casos de 3000 y 4000 no son 3x y 4x respectivamente, sino la mitad. Específicamente, con 3000 elementos por conjunto, tiene menos accesos que con 2000 elementos.
Esto me hace sospechar que la unidad de memoria es capaz de combinar cada 2 cargas en un solo acceso de memoria, pero solo cuando va a la L2 y más allá. Eso tiene sentido cuando lo piensas, no hay razón para emitir otro acceso para buscar el L2 si ya tienes uno pendiente para esa línea, y es una forma factible de mitigar el ancho de banda inferior en ese nivel. Supongo que, por alguna razón, la segunda carga ni siquiera se contabiliza como una búsqueda L1, y no ayuda a la tasa de aciertos que desea ver (puede verificar los contadores que indican cuántas cargas están pasando la ejecución, eso probablemente debería ser cierto). Sin embargo, esto es solo una corazonada, no estoy seguro de cómo se define el contador, pero se ajusta al número de accesos que vemos.