while visual una tablas tabla studio operaciones multiplicar mostrar hacer form consola con como basicas c# arrays matrix-multiplication

c# - visual - ¿Por qué hay un gran rendimiento en 2048x2048 frente a la multiplicación de 2047x2047?



tabla de multiplicar en c# con while (10)

Alias ​​de caché

O agolpamiento de caché , si puedo acuñar un término.

Las cachés funcionan indexando con bits de orden baja 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, los elementos de cada columna en la memoria se asignarán al mismo elemento de caché.

Una potencia de dos más uno es realmente óptima para este problema. Cada nuevo elemento de columna se correlacionará con la siguiente ranura de caché exactamente como si accediera por fila.

En la vida real, una etiqueta cubre múltiples direcciones que se incrementan secuencialmente y que almacenan en caché varios elementos adyacentes en una fila. Al desplazar la cubeta a la que se asigna cada nueva fila, atravesar la columna no reemplaza la entrada anterior. Cuando se atraviesa la siguiente columna, toda la memoria caché se rellenará con filas diferentes y cada sección de fila que se ajuste a la memoria caché mostrará varias columnas.

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

Estoy haciendo un benchmarking 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 otros. Cuando intento multiplicar solo matrices 2047x2047, parece normal. Agregó algunos otros para la comparación también.

1024x1024 - 10 segundos.

1027x1027 - 10 segundos.

2047x2047 - 90 segundos.

2048x2048 - 300 segundos.

2049x2049 - 91 segundos. (actualizar)

2500x2500 - 166 segundos

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

usando matrices de 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; } }

A medida que accede a la matriz matice2 verticalmente, se intercambiará dentro y fuera de la memoria caché mucho más. Si duplica la matriz en diagonal, para que pueda acceder a ella utilizando [k,m] lugar de [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 matrices de 2048x2048 es aproximadamente diez veces más rápido.

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

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

Las fallas de caché en matice1 no son el problema porque se accede de forma secuencial. Sin embargo, para matice2 si una columna completa cabe en L2 (es decir, cuando accede a matice2 [0, 0], matice2 [1, 0], matice2 [2, 0] ... etc, no se desaloja a nadie) que no hay problema con el caché falla con matice2 tampoco.

Ahora, para profundizar en cómo funciona el caché, si la dirección de byte de su variable es X, entonces la línea de caché sería (X >> 6) & (L - 1). Donde L es el número total de líneas de caché en su caché. L es siempre 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, eso 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 tamaño:

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 flotación). 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 encajará de forma segura en su caché.

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

Asigna tu array array matice2 como este matice2 [razmor, 4096], y ejecuta con razmor = 1024, 1025 o cualquier tamaño, y deberías ver muy mal rendimiento en comparación con lo que tenías antes. Esto se debe a que alineas todas las columnas por la fuerza para que entren en conflicto entre ellas.

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

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

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 16KB, entonces las cosas comienzan a complicarse. Además, cada vez que "omite" el caché, intercambiar datos de otro caché o memoria principal retrasa las cosas.

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

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 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 W elementos en la memoria, donde W es el número de columnas . El mosaico puede generar tanto como una diferencia de rendimiento de factor de diez.

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

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

Probablemente un efecto de almacenamiento en caché. Con dimensiones matriciales que son grandes potencias de dos y un tamaño de caché que también es una potencia de dos, puede terminar utilizando solo una pequeña fracción de su caché L1, ralentizando mucho las cosas. La multiplicación de matrices ingenua generalmente está limitada por la necesidad de obtener datos en la memoria caché. Los algoritmos optimizados que usan mosaico (o algoritmos de caché ajena) se centran en hacer un mejor uso de la memoria caché L1.

Si mide 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] estén desplazados uno del otro en 2048 * sizeof (float) y así mapear al mismo índice en la caché L1. Con un caché asociativo de N vías, normalmente tendrá de 1 a 8 ubicaciones de caché para todo esto. Por lo tanto, casi todos estos accesos desencadenarán un desalojo de caché L1 y la obtención de datos de un caché o memoria principal más lentos.

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

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