optimización del bucle anidado del compilador para acceso a la memoria secuencial.

Question

Me encontré con un problema de rendimiento extraño en un punto de referencia de multiplicación de matriz (matrix_mult en Metis desde el paquete MOSBENCH). El punto de referencia se optimizó para ajustar los datos de forma tal que el conjunto de trabajo activo fuera de 12kb (3 mosaicos de 32x32 ints) y encajaría en la caché L1. Para resumir, el intercambio de los dos bucles más internos tuvo una diferencia de rendimiento de casi 4x en ciertos tamaños de entrada de matriz (4096, 8192) y alrededor de un 30% de diferencia en otros. El problema básicamente se reducía a acceder a los elementos secuencialmente versus en un patrón de zancada. Determinados tamaños de matriz creo que crearon un mal acceso de zancada que generó muchas colisiones en la línea de caché. La diferencia de rendimiento es notablemente menor cuando se cambia de L1 asociativo de 2 vías a L1 asociativo de 8 vías.

Mi pregunta es por qué gcc no optimiza el orden de bucles para maximizar los accesos de memoria secuenciales?

A continuación se muestra una versión simplificada del problema (tenga en cuenta que los tiempos de rendimiento dependen en gran medida de la configuración de L1. Los números que se muestran a continuación son del sistema 2.3 GHZ AMD con 64K L1 de 2 vías compilado con -O3).

N = ARRAY_SIZE // 1024 
int* mat_A = (int*)malloc(N*N*sizeof(int)); 
int* mat_B = (int*)malloc(N*N*sizeof(int)); 
int* mat_C = (int*)malloc(N*N*sizeof(int)); 

// Elements of mat_B are accessed in a stride pattern of length N 
// This takes 800 msec 
for (int t = 0; t < 1000; t++) 
    for (int a = 0; a < 32; a++) 
     for (int b = 0; b < 32; b++) 
     for (int c = 0; c < 32; c++) 
      mat_C[N*a+b] += mat_A[N*a+c] * mat_B[N*c+b]; 

// Inner two loops are swapped 
// Elements are now accessed sequentially in inner loop 
// This takes 172 msec 
for (int t = 0; t < 1000; t++) 
    for (int a = 0; a < 32; a++) 
     for (int c = 0; c < 32; c++) 
     for (int b = 0; b < 32; b++) 
      mat_C[N*a+b] += mat_A[N*a+c] * mat_B[N*c+b]; 

Answer 1

1. gcc podría no ser capaz de demostrar que los punteros no se superponen. Si está bien usar extensiones no estándar, puede intentar usar __restrict.
2. gcc no aprovecha al máximo su arquitectura para evitar la necesidad de recompilar para cada procesador. Usar la opción -march con el valor apropiado para su sistema puede ayudar.

Answer 2

gcc tiene un montón de optimizaciones que hacen lo que usted quiere.

Busque las opciones del compilador -floop-strip-mine y -floop-block.

Cita del manual:

realizar transformaciones de bloqueo de bucle en los bucles. Bloqueo de las minas de tira cada bucle en el bucle anida de modo que los accesos de memoria de los elementos se ajusten dentro de cachés. La longitud de la tira se puede cambiar usando el parámetro loop-block-tile-size.