¿Por qué hay un gran impacto en el rendimiento en 2048x2048 frente a la multiplicación de matriz 2047x2047?

Estoy haciendo una evaluación comparativa de multiplicación de matrices, como se mencionó anteriormente en ¿Por qué MATLAB es tan rápido en la multiplicación de matrices?

Ahora tengo otro problema, al multiplicar dos matrices de 2048x2048, hay una gran diferencia entre C # y otras. Cuando intento multiplicar solo matrices 2047x2047, parece normal. También se agregaron algunos otros para la comparación.

1024x1024 - 10 segundos.

1027x1027 - 10 segundos.

2047x2047 - 90 segundos.

2048x2048 - 300 segundos.

2049x2049 - 91 segundos. (actualizar)

2500x2500 - 166 segundos

Esa es una diferencia de tres minutos y medio para el caso de 2k por 2k.

utilizando matrices 2dim

//Array init like this
int rozmer = 2048;
float[,] matice = new float[rozmer, rozmer];

//Main multiply code
for(int j = 0; j < rozmer; j++)
{
   for (int k = 0; k < rozmer; k++)
   {
     float temp = 0;
     for (int m = 0; m < rozmer; m++)
     {
       temp = temp + matice1[j,m] * matice2[m,k];
     }
     matice3[j, k] = temp;
   }
 }

Esto probablemente tenga que ver con conflictos en su caché L2.

Los errores de caché en matice1 no son el problema porque se accede secuencialmente. Sin embargo, para matice2 si una columna completa encaja en L2 (es decir, cuando accede a matice2 [0, 0], matice2 [1, 0], matice2 [2, 0] ... etc., nada se desaloja) que no hay ningún problema con el caché falla con matice2 tampoco.

Ahora, para profundizar en el funcionamiento de los cachés, si la dirección de byte de su variable es X, la línea de caché sería (X >> 6) y (L - 1). Donde L es el número total de líneas de caché en su caché. L es siempre una potencia de 2. El seis proviene del hecho de que 2 ^ 6 == 64 bytes es el tamaño estándar de la línea de caché.

Ahora, que significa esto? Bueno, significa que si tengo la dirección X y la dirección Y y (X >> 6) - (Y >> 6) es divisible por L (es decir, una gran potencia de 2), se almacenarán en la misma línea de caché.

Ahora, para volver a su problema, ¿cuál es la diferencia entre 2048 y 2049?

cuando 2048 es tu talla:

si toma & matice2 [x, k] y & matice2 [y, k] la diferencia (& matice2 [x, k] >> 6) - (& matice2 [y, k] >> 6) será divisible por 2048 * 4 (tamaño de flotador). Entonces una gran potencia de 2.

Por lo tanto, dependiendo del tamaño de su L2, tendrá muchos conflictos de línea de caché y solo utilizará una pequeña porción de su L2 para almacenar una columna, por lo que no podrá almacenar la columna completa en su caché, por lo que obtendrá un mal rendimiento .

Cuando el tamaño es 2049, la diferencia es 2049 * 4, que no es potencia de 2, por lo que tendrá menos conflictos y su columna se ajustará de forma segura a su caché.

Ahora, para probar esta teoría, hay un par de cosas que puedes hacer:

Asigne su matriz matriz matice2 como esta matice2 [razmor, 4096], y ejecute con razmor = 1024, 1025 o cualquier tamaño, y debería ver un rendimiento muy malo en comparación con lo que tenía antes. Esto se debe a que alinea con fuerza todas las columnas para que entren en conflicto entre sí.

Luego pruebe matice2 [razmor, 4097] y ejecútelo con cualquier tamaño y debería ver un rendimiento mucho mejor.

Probablemente un efecto de almacenamiento en caché. Con dimensiones de matriz que son grandes potencias de dos, y un tamaño de caché que también es una potencia de dos, puede terminar usando solo una pequeña fracción de su caché L1, lo que ralentiza mucho las cosas. La multiplicación ingenua de matrices generalmente está limitada por la necesidad de recuperar datos en el caché. Los algoritmos optimizados que utilizan mosaico (o algoritmos ajenos al caché) se centran en hacer un mejor uso del caché L1.

Si cronometra otros pares (2 ^ n-1,2 ^ n) espero que vea efectos similares.

Para explicarlo más completamente, en el bucle interno, donde accede a matice2 [m, k], es probable que matice2 [m, k] y matice2 [m + 1, k] se compensen entre sí por 2048 * sizeof (float) y así correlacionar con el mismo índice en el caché L1. Con un caché asociativo N-way, normalmente tendrá 1-8 ubicaciones de caché para todo esto. Por lo tanto, casi todos esos accesos desencadenarán un desalojo de caché L1 y la obtención de datos de un caché más lento o memoria principal.

Esto puede tener que ver con el tamaño de su caché de la CPU. Si 2 filas de la matriz de matriz no encajan, perderá tiempo intercambiando elementos de la RAM. Los 4095 elementos adicionales pueden ser suficientes para evitar que se ajusten las filas.

En su caso, 2 filas para 2047 matrices 2d caen dentro de 16 KB de memoria (suponiendo tipos de 32 bits). Por ejemplo, si tiene un caché L1 (el más cercano a la CPU en el bus) de 64 KB, puede colocar al menos 4 filas (de 2047 * 32) en el caché a la vez. Con las filas más largas si se requiere un relleno que empuje los pares de filas más allá de 16 KB, entonces las cosas comienzan a complicarse. Además, cada vez que 'pierde' el caché, el intercambio de datos de otro caché o memoria principal retrasa las cosas.

Supongo que la variación en los tiempos de ejecución que está viendo con las matrices de diferentes tamaños se ve afectada por la eficacia con la que el sistema operativo puede hacer uso de la memoria caché disponible (y algunas combinaciones son simplemente problemáticas). Por supuesto, esto es una gran simplificación de mi parte.

Louis Brandy escribió dos publicaciones de blog analizando exactamente este problema:

Más locura de caché y rendimiento computacional: un estudio de caso para principiantes con algunas estadísticas interesantes e intentos de explicar el comportamiento con más detalle, de hecho se reduce a las limitaciones de tamaño de caché.

Dado que el tiempo se está reduciendo en tamaños más grandes, ¿no sería más probable que haya conflictos de caché, especialmente con potencias de 2 para los tamaños de matriz problemáticos? No soy experto en problemas de almacenamiento en caché, pero aquí tengo excelente información sobre problemas de rendimiento relacionados con el almacenamiento en caché .

A medida que accede a la matice2matriz verticalmente, se intercambiará mucho más dentro y fuera de la memoria caché. Si duplica la matriz en diagonal, para que pueda acceder a ella en [k,m]lugar de hacerlo [m,k], el código se ejecutará mucho más rápido.

Probé esto para matrices de 1024x1024, y es aproximadamente el doble de rápido. Para las matrices 2048x2048 es aproximadamente diez veces más rápido.

Aliasing de caché

O la caché golpeando , si puedo acuñar un término.

Las memorias caché funcionan indexando con bits de orden inferior y etiquetando con bits de orden superior.

Imagine que su caché tiene 4 palabras y su matriz es 4 x 4. Cuando se accede a una columna y la fila tiene una potencia de dos de longitud, cada elemento de columna en la memoria se asignará al mismo elemento de caché.

Un poder de dos más uno es realmente óptimo para este problema. Cada nuevo elemento de columna se asignará a la siguiente ranura de caché exactamente como si se accediera por fila.

En la vida real, una etiqueta cubre múltiples direcciones que aumentan secuencialmente y que almacenarán en caché varios elementos adyacentes en una fila. Al compensar el depósito al que se asigna cada nueva fila, atravesar la columna no reemplaza la entrada anterior. Cuando se atraviesa la siguiente columna, todo el caché se llenará con diferentes filas y cada sección de fila que se ajuste al caché alcanzará varias columnas.

Dado que el caché es mucho más rápido que la DRAM (principalmente en virtud de estar en el chip), la tasa de aciertos es todo.

Parece que has alcanzado un límite de tamaño de caché, o tal vez tienes algunos problemas de repetibilidad en tus tiempos.

Cualquiera sea el problema, simplemente no debe escribir la multiplicación de matrices usted mismo en C # y en su lugar usar una versión optimizada de BLAS. Ese tamaño de matriz debe multiplicarse en menos de un segundo en cualquier máquina moderna.

La utilización efectiva de la jerarquía de caché es muy importante. Debe asegurarse de que las matrices multidimensionales tengan datos en una buena disposición, lo que se puede lograr mediante el mosaico . Para hacer esto, necesitará almacenar la matriz 2D como una matriz 1D junto con un mecanismo de indexación. El problema con el método tradicional es que, aunque dos elementos de matriz adyacentes que están en la misma fila están uno al lado del otro en la memoria, dos elementos adyacentes en la misma columna estarán separados por elementos W en la memoria, donde W es el número de columnas . El mosaico puede marcar una diferencia de rendimiento de un factor de diez.

Sospecho que es el resultado de algo llamado " Inundación secuencial ". Lo que es esto es que está intentando recorrer la lista de objetos que es un poco más grande que el tamaño del caché, por lo tanto, cada solicitud a la lista (matriz) debe hacerse desde el ram, y no obtendrá un solo caché golpear.

En su caso, está recorriendo sus matrices 2048 índices 2048 veces, pero solo tiene espacio para 2047 (posiblemente debido a cierta sobrecarga de la estructura de la matriz), por lo que cada vez que accede a una posición de la matriz, necesita obtener esta posición de la matriz. de carnero. Luego se almacena en la memoria caché, pero justo antes de volver a usarse, se descarga. Por lo tanto, el caché es esencialmente inútil, lo que lleva a un tiempo de ejecución mucho más largo.