resueltos - que es cache en informatica

Ancho de banda de memoria L1: 50% de disminución en la eficiencia con direcciones que difieren en 4096+64 bytes

Question

Quiero lograr el ancho de banda máximo de las siguientes operaciones con los procesadores Intel.

for(int i=0; i<n; i++) z[i] = x[i] + y[i]; //n=2048

donde x, y, y z son matrices flotantes. Estoy haciendo esto en los sistemas Haswell, Ivy Bridge y Westmere.

Originalmente asigné la memoria de esta manera

char *a = (char*)_mm_malloc(sizeof(float)*n, 64);
char *b = (char*)_mm_malloc(sizeof(float)*n, 64);
char *c = (char*)_mm_malloc(sizeof(float)*n, 64);
float *x = (float*)a; float *y = (float*)b; float *z = (float*)c;

Cuando hice esto obtuve aproximadamente el 50% del ancho de banda máximo que esperaba para cada sistema.

Los valores máximos se calculan como frequency * average bytes/clock_cycle . El ciclo promedio de bytes / reloj para cada sistema es:

Core2: two 16 byte reads one 16 byte write per 2 clock cycles -> 24 bytes/clock cycle
SB/IB: two 32 byte reads and one 32 byte write per 2 clock cycles -> 48 bytes/clock cycle
Haswell: two 32 byte reads and one 32 byte write per clock cycle -> 96 bytes/clock cycle

Esto significa que, por ejemplo, en Haswell II solo se observan 48 bytes / ciclo de reloj (podrían ser dos lecturas en un ciclo de reloj y una escritura en el siguiente ciclo de reloj).

Imprimí la diferencia en la dirección de ba y cb y cada uno tiene 8256 bytes. El valor 8256 es 8192 + 64. Entonces cada uno es más grande que el tamaño de la matriz (8192 bytes) por una línea de caché.

Por un capricho, traté de asignar la memoria de esta manera.

const int k = 0;
char *mem = (char*)_mm_malloc(1<<18,4096);
char *a = mem;
char *b = a+n*sizeof(float)+k*64;
char *c = b+n*sizeof(float)+k*64;
float *x = (float*)a; float *y = (float*)b; float *z = (float*)c;

Esto casi duplicó mi ancho de banda máximo, de modo que ahora obtengo alrededor del 90% del ancho de banda máximo. Sin embargo, cuando probé k=1 , volvió a caer al 50%. He intentado con otros valores de k encontré que, por ejemplo, k=2 , k=33 , k=65 solo obtiene el 50% del pico pero, por ejemplo, k=10 , k=32 , k=63 dio la velocidad máxima. No entiendo esto.

En el manual de microrrefiguración de Agner Fog dice que hay una dependencia falsa con dirección de memoria con el mismo conjunto y desplazamiento

No es posible leer y escribir simultáneamente desde direcciones que están espaciadas por un múltiplo de 4 Kbytes.

¡Pero allí es donde veo el mayor beneficio! Cuando k=0 la dirección de memoria difiere exactamente en 2*4096 bytes. Agner también habla sobre conflictos en los bancos de caché. Pero se supone que Haswell y Westmere no tienen estos conflictos bancarios, por lo que no deberían explicar lo que estoy observando. ¿¡Que esta pasando!?

Entiendo que la ejecución de OoO decide qué dirección leer y escribir, incluso si las direcciones de las matrices difieren exactamente 4096 bytes, lo que no significa necesariamente que el procesador lea por ejemplo &x[0] y escriba &z[0] al mismo tiempo, pero entonces, ¿por qué estar desconectado por una sola línea de caché causa que se ahogue?

Editar: Basado en la respuesta de Evgeny Kluev, ahora creo que esto es lo que Agner Fog llama un "puesto de reenvío de tienda falso". En su manual de Pentium Pro, II y II, escribe:

Curiosamente, puede obtener un puesto de reenvío de tienda falso cuando escribe y lee direcciones completamente diferentes si tienen el mismo valor fijo en diferentes bancos de caché:

; Example 5.28. Bogus store-to-load forwarding stall
mov byte ptr [esi], al
mov ebx, dword ptr [esi+4092]
; No stall
mov ecx, dword ptr [esi+4096]
; Bogus stall

Editar: Aquí está la tabla de las eficiencias en cada sistema para k=0 y k=1 .

 k=0 k=1
Westmere: 99% 66%
Ivy Bridge: 98% 44%
Haswell: 90% 49%

Creo que puedo explicar estos números si supongo que para k=1 que escribe y lee no puede suceder en el mismo ciclo de reloj.

 cycle Westmere Ivy Bridge Haswell
1 read 16 read 16 read 16 read 32 read 32
2 write 16 read 16 read 16 write 32
3 write 16
4 write 16
k=1/k=0 peak 16/24=66% 24/48=50% 48/96=50%

Esta teoría funciona bastante bien. Ivy bridge es un poco más bajo de lo que esperaba, pero Ivy Bridge sufre conflictos de caché bancaria donde los demás no lo hacen, por lo que puede ser otro efecto a tener en cuenta.

A continuación está el código de trabajo para probarlo usted mismo. En un sistema sin AVX compile con g++ -O3 sum.cpp contrario compila con g++ -O3 -mavx sum.cpp . Intenta variar el valor k .

//sum.cpp
#include <x86intrin.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#define TIMER_TYPE CLOCK_REALTIME
double time_diff(timespec start, timespec end)
{
timespec temp;
if ((end.tv_nsec-start.tv_nsec)<0) {
temp.tv_sec = end.tv_sec-start.tv_sec-1;
temp.tv_nsec = 1000000000+end.tv_nsec-start.tv_nsec;
} else {
temp.tv_sec = end.tv_sec-start.tv_sec;
temp.tv_nsec = end.tv_nsec-start.tv_nsec;
}
return (double)temp.tv_sec + (double)temp.tv_nsec*1E-9;
}
void sum(float * __restrict x, float * __restrict y, float * __restrict z, const int n) {
#if defined(__GNUC__)
x = (float*)__builtin_assume_aligned (x, 64);
y = (float*)__builtin_assume_aligned (y, 64);
z = (float*)__builtin_assume_aligned (z, 64);
#endif
for(int i=0; i<n; i++) {
z[i] = x[i] + y[i];
}
}
#if (defined(__AVX__))
void sum_avx(float *x, float *y, float *z, const int n) {
float *x1 = x;
float *y1 = y;
float *z1 = z;
for(int i=0; i<n/64; i++) { //unroll eight times
_mm256_store_ps(z1+64*i+ 0,_mm256_add_ps(_mm256_load_ps(x1+64*i+ 0), _mm256_load_ps(y1+64*i+ 0)));
_mm256_store_ps(z1+64*i+ 8,_mm256_add_ps(_mm256_load_ps(x1+64*i+ 8), _mm256_load_ps(y1+64*i+ 8)));
_mm256_store_ps(z1+64*i+ 16,_mm256_add_ps(_mm256_load_ps(x1+64*i+16), _mm256_load_ps(y1+64*i+ 16)));
_mm256_store_ps(z1+64*i+ 24,_mm256_add_ps(_mm256_load_ps(x1+64*i+24), _mm256_load_ps(y1+64*i+ 24)));
_mm256_store_ps(z1+64*i+ 32,_mm256_add_ps(_mm256_load_ps(x1+64*i+32), _mm256_load_ps(y1+64*i+ 32)));
_mm256_store_ps(z1+64*i+ 40,_mm256_add_ps(_mm256_load_ps(x1+64*i+40), _mm256_load_ps(y1+64*i+ 40)));
_mm256_store_ps(z1+64*i+ 48,_mm256_add_ps(_mm256_load_ps(x1+64*i+48), _mm256_load_ps(y1+64*i+ 48)));
_mm256_store_ps(z1+64*i+ 56,_mm256_add_ps(_mm256_load_ps(x1+64*i+56), _mm256_load_ps(y1+64*i+ 56)));
}
}
#else
void sum_sse(float *x, float *y, float *z, const int n) {
float *x1 = x;
float *y1 = y;
float *z1 = z;
for(int i=0; i<n/32; i++) { //unroll eight times
_mm_store_ps(z1+32*i+ 0,_mm_add_ps(_mm_load_ps(x1+32*i+ 0), _mm_load_ps(y1+32*i+ 0)));
_mm_store_ps(z1+32*i+ 4,_mm_add_ps(_mm_load_ps(x1+32*i+ 4), _mm_load_ps(y1+32*i+ 4)));
_mm_store_ps(z1+32*i+ 8,_mm_add_ps(_mm_load_ps(x1+32*i+ 8), _mm_load_ps(y1+32*i+ 8)));
_mm_store_ps(z1+32*i+ 12,_mm_add_ps(_mm_load_ps(x1+32*i+12), _mm_load_ps(y1+32*i+ 12)));
_mm_store_ps(z1+32*i+ 16,_mm_add_ps(_mm_load_ps(x1+32*i+16), _mm_load_ps(y1+32*i+ 16)));
_mm_store_ps(z1+32*i+ 20,_mm_add_ps(_mm_load_ps(x1+32*i+20), _mm_load_ps(y1+32*i+ 20)));
_mm_store_ps(z1+32*i+ 24,_mm_add_ps(_mm_load_ps(x1+32*i+24), _mm_load_ps(y1+32*i+ 24)));
_mm_store_ps(z1+32*i+ 28,_mm_add_ps(_mm_load_ps(x1+32*i+28), _mm_load_ps(y1+32*i+ 28)));
}
}
#endif
int main () {
const int n = 2048;
const int k = 0;
float *z2 = (float*)_mm_malloc(sizeof(float)*n, 64);
char *mem = (char*)_mm_malloc(1<<18,4096);
char *a = mem;
char *b = a+n*sizeof(float)+k*64;
char *c = b+n*sizeof(float)+k*64;
float *x = (float*)a;
float *y = (float*)b;
float *z = (float*)c;
printf("x %p, y %p, z %p, y-x %d, z-y %d/n", a, b, c, b-a, c-b);
for(int i=0; i<n; i++) {
x[i] = (1.0f*i+1.0f);
y[i] = (1.0f*i+1.0f);
z[i] = 0;
}
int repeat = 1000000;
timespec time1, time2;
sum(x,y,z,n);
#if (defined(__AVX__))
sum_avx(x,y,z2,n);
#else
sum_sse(x,y,z2,n);
#endif
printf("error: %d/n", memcmp(z,z2,sizeof(float)*n));
while(1) {
clock_gettime(TIMER_TYPE, &time1);
#if (defined(__AVX__))
for(int r=0; r<repeat; r++) sum_avx(x,y,z,n);
#else
for(int r=0; r<repeat; r++) sum_sse(x,y,z,n);
#endif
clock_gettime(TIMER_TYPE, &time2);
double dtime = time_diff(time1,time2);
double peak = 1.3*96; //haswell @1.3GHz
//double peak = 3.6*48; //Ivy Bridge @ 3.6Ghz
//double peak = 2.4*24; // Westmere @ 2.4GHz
double rate = 3.0*1E-9*sizeof(float)*n*repeat/dtime;
printf("dtime %f, %f GB/s, peak, %f, efficiency %f%%/n", dtime, rate, peak, 100*rate/peak);
}
}

Answer 1

Creo que la brecha entre a y b realmente no importa. Después de dejar solo un espacio entre b tengo los siguientes resultados en Haswell:

k %
-----
1 48
2 48
3 48
4 48
5 46
6 53
7 59
8 67
9 73
10 81
11 85
12 87
13 87
...
0 86

Como se sabe que Haswell no tiene conflictos bancarios, la única explicación que queda es la falsa dependencia entre direcciones de memoria (y ha encontrado el lugar adecuado en el manual de microarquitectura de Agner Fog que explica exactamente este problema). La diferencia entre el conflicto bancario y el intercambio falso es que el conflicto bancario impide acceder al mismo banco dos veces durante el mismo ciclo de reloj, mientras que el uso compartido falso impide la lectura de un desplazamiento en memoria 4K justo después de haber escrito algo con el mismo desplazamiento (y no solo durante el mismo ciclo de reloj pero también durante varios ciclos de reloj después de la escritura).

Dado que su código (para k=0 ) escribe en cualquier desplazamiento justo después de hacer dos lecturas del mismo desplazamiento y no leería durante un tiempo muy prolongado, este caso debe considerarse como "mejor", por lo que puse k=0 al final de la mesa Para k=1 , siempre lee desde el desplazamiento que ha sido sobreescrito recientemente, lo que significa compartir falsamente y por lo tanto degradación del rendimiento. Con mayor tiempo k entre incrementos de escritura y lectura y CPU core tiene más posibilidades de pasar datos escritos a través de toda la jerarquía de memoria (lo que significa dos conversiones de direcciones para lectura y escritura, actualización de datos y etiquetas y obtención de datos del caché, sincronización de datos entre núcleos, y probablemente muchas más cosas). k=12 o 24 relojes (en mi CPU) es suficiente para que cada pieza escrita de datos esté lista para las operaciones de lectura subsiguientes, por lo que al comenzar con este valor, el rendimiento vuelve a ser el habitual. No parece muy diferente de más de 20 relojes en AMD (como dice @Mysticial).