Comenzaré con el algoritmo básico y lo mejoraré para usar el caché.
Aquí A es una matriz (N, K), B es una matriz (K, M) y C = AB es una matriz (N, M).
para i en rango (0, N):
para j en el rango (0, M):
para k en el rango (0, K):
C [i] [j] + = A [i] [k] * B [k] [j]
(tenga en cuenta que este es el código de Python, por lo que el rango (0, N) contiene todos los enteros entre 0 y N-1. Si desea codificarlo en Python, le recomiendo que use matrices numpy para A, B y C)
Al hacer esto, su código pasará mucho tiempo mirando A [i] [k] y B [k] [j] en la memoria porque cambian en cada paso. Entonces hacemos 2 * N * K * M accesos de memoria.
La primera mejora que se debe hacer es invertir la suma en k, y la suma en j, para que podamos mantener el mismo r = A [i] [k] durante algún tiempo:
- ¿Cuál sería un ejemplo de un problema de programación que sería difícil si no fuera posible sin el uso de array?
- ¿Hay algún algoritmo que pueda implementarse en un lenguaje de programación pero no en otro lenguaje de programación?
- Cómo implementar el algoritmo
- ¿Los programadores diseñan algoritmos o simplemente los toman de Internet?
- ¿Cuál es el algoritmo utilizado por Diffbot para extraer datos web?
para i en rango (0, N):
para k en el rango (0, K):
r = A [i] [k]
para j en el rango (0, M):
C [i] [j] + = r * B [k] [j]
Este método realmente no usa caché, pero la apuesta solo hace acceso a la memoria N * K + N * K * M. Ahora suponga que B es una matriz pequeña que puede caber en su efectivo. Luego, su computadora leerá una primera vez B durante el primer ciclo i = 1 y la almacenará en su caché. Entonces el acceso a B [k] [j] será muy rápido porque ya estará en caché. Entonces solo hará N * K + K * M accesos a memoria (y (N-1) * K * M accesos a caché)
Entonces, lo que hacemos es dividir virtualmente B en una submatriz de tamaño más pequeña (S, S) que se ajusta a la memoria caché.
para kk en rango (0, K / S + 1):
para jj en rango (0, M / S + 1):
para i en rango (0, N):
para k en el rango (S * kk, min (S * (kk + 1), K)):
r = A [i] [k]
para j en el rango (S * jj, min (S * (jj + 1), M)):
C [i] [j] + = r * B [k] [j]
De esta manera, para cada kk y jj hacemos N * S + S * S accesos a memoria, donde S * S no puede ser mayor que el tamaño de la memoria caché. Con S = 1 volvemos al caso original pero sumamos k, j y luego i. Con S más grande que K y M volvemos al segundo caso con accesos de memoria N * K + K * M, y no podemos hacerlo mejor que eso. De hecho, ¡necesitamos leer ambas matrices para multiplicarlas!
