¿Cómo funciona la memoria caché?

Question

Hoy, cuando estaba en la clase de organización de computadoras, la maestra habló sobre algo interesante para mí. Cuando se trata de hablar sobre por qué funciona la memoria caché, dijo que:

for (i=0; i<M; i++)
   for(j=0; j<N; j++)
      X[i][j] = X[i][j] + K; //X is double(8 bytes)

no es bueno cambiar la primera línea con la segunda. ¿Qué opinas sobre esto? ¿Y por qué es así?

Answer 1

Localidad de referencia. Debido a que los datos se almacenan por filas, para cada fila las j columnas están en direcciones de memoria adyacentes. El sistema operativo normalmente cargará una página completa de la memoria en el caché y las referencias de direcciones adyacentes probablemente se referirán a esa misma página. Si incrementa por el índice de la fila en el bucle interno, es posible que estas filas estén en diferentes páginas (ya que están separadas por j dobles cada una) y que la memoria caché tenga que traer y desechar constantemente las páginas de la memoria como referencia. los datos. Esto se llama golpear y es malo para el rendimiento.

En la práctica y con cachés más grandes y modernos, los tamaños de las filas / columnas deberían ser razonablemente grandes antes de que esto entre en juego, pero sigue siendo una buena práctica.

[EDITAR] La respuesta anterior es específica de C y puede diferir para otros idiomas. El único que sé que es diferente es FORTRAN. FORTRAN almacena las cosas en el orden mayor de la columna (lo anterior es la fila principal) y sería correcto cambiar el orden de las declaraciones en FORTRAN. Si desea / necesita eficiencia, es importante saber cómo su idioma implementa el almacenamiento de datos.

Answer 2

Hay un muy buen artículo de Ulrich Drepper de Red Hat y fama glibc, Lo que todo programador debería Saber acerca de la memoria . Una sección discutió los cachés con gran detalle. Por ejemplo, hay efectos de caché en los sistemas SMP en los que las CPU pueden acabar con la propiedad de una línea de caché modificada de un lado a otro, lo que perjudica en gran medida el rendimiento.

Answer 3

Es así porque los cachés como localidad. La misma cantidad de memoria accedida, pero espaciada aún más, alcanzará diferentes "líneas". de caché, o incluso podría perder el caché por completo. Por lo tanto, es bueno, siempre que tenga la opción, organizar los datos para que los accesos que puedan ocurrir cerca uno del otro en el tiempo, también lo hagan en el espacio. Esto aumenta la posibilidad de un acierto de caché y le proporciona más rendimiento.

Por supuesto, hay una gran cantidad de información disponible sobre este tema, consulte, por ejemplo, esta entrada de wikipedia en la localidad de referencia . O, supongo, su propio libro de texto del curso. :)

Answer 4

En C, las matrices n-dimensionales son filas mayores, lo que significa que el último índice en la matriz representa espacios adyacentes en la memoria. Esto es diferente a algunos otros idiomas, FORTRAN por ejemplo, que son columnas principales. En FORTRAN, es más eficiente iterar a través de una matriz 2D como esta:

do jj = 1,N
  do ii = 1,M
    x(ii,jj) = x(ii,jj) + K;
  enddo
enddo

Answer 5

La memoria caché es una memoria muy rápida y muy costosa que se encuentra cerca de la CPU. En lugar de obtener un pequeño fragmento de datos de la RAM cada vez, la CPU obtiene una parte de los datos y los almacena en la memoria caché. La apuesta es que si acaba de leer un byte, es probable que el siguiente byte que lea esté justo después. Si este es el caso, entonces puede provenir del caché.

Al diseñar su bucle como lo tiene, lee los bytes en el orden en que se almacenan en la memoria. Esto significa que están en la memoria caché y que la CPU puede leerlos muy rápidamente. Si intercambiaste las líneas 1 y 2, entonces leerías cada " N " bytes cada vez alrededor del bucle. Los bytes que está leyendo ya no son consecutivos en la memoria, por lo que es posible que no estén en la memoria caché. La CPU tiene que recuperarlos de la RAM (más lenta), por lo que su rendimiento disminuye.