Hoy, cuando estaba en la clase de organización informática, la maestra habló sobre algo interesante para mí. Cuando se trata de hablar de por qué funciona la memoria caché, dijo que:¿Cómo funciona la memoria caché?
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 el segundo. ¿Cuál es tu opinión sobre esto? ¿Y por qué es así?
Localidad de referencia. Como los datos se almacenan por filas, para cada fila, las j columnas están en direcciones de memoria adyacentes. El SO generalmente 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 aumenta por el índice de fila en el bucle interno, es posible que estas filas estén en páginas diferentes (ya que están separadas por j dobles cada una) y la memoria caché puede tener que traer y eliminar constantemente las páginas de memoria a medida que hace referencia. los datos. Esto se llama golpeteo y es malo para el rendimiento.
En la práctica y con caches más grandes y modernos, los tamaños de las filas/columnas tendrían que ser razonablemente grandes antes de que esto entrara 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 cosas en orden mayor de columna (la 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 lenguaje implementa el almacenamiento de datos.
¿Es realmente el sistema operativo el que maneja esto? Tenía la impresión de que el propio procesador manejaba su propio Caché, y que el sistema operativo simplemente lo deshabilitaba para ciertas páginas, etc. –
"OS cargará típicamente una página entera de la memoria" - hoho, es un error para l1/l2/l3 caché de datos. En parte es cierto para las memorias caché tlb con la antigua TLU (MMU) que no puede cargar la entrada de la tabla de páginas en hardware – osgx
Es así porque causa caches como localidad. La misma cantidad de memoria a la que se accede, pero espaciada aún más, afectará a diferentes "líneas" de caché, o incluso podría perder la memoria caché por completo. Por lo tanto, es bueno, siempre que tenga la opción, organizar los datos para que los accesos que probablemente se suceden a tiempo, también lo hagan en el espacio. Esto aumenta las posibilidades de que se produzca un golpe de caché y le proporciona más rendimiento.
Por supuesto, hay una gran cantidad de información sobre este tema disponible, ver por ejemplo this wikipedia entry on locality of reference. O, supongo, tu propio libro de texto del curso. :)
Gracias por la información. buen recurso;) – israkir
En C, las matrices de dimensión n son fila mayor, lo que significa que el último índice en la matriz representa espacios adyacentes en la memoria. Esto es diferente de algunos otros lenguajes, FORTRAN por ejemplo, que son columnas principales. En FORTRAN, que es más eficiente para iterar a través de una matriz 2D como esto:
do jj = 1,N
do ii = 1,M
x(ii,jj) = x(ii,jj) + K;
enddo
enddo
Esto es incorrecto. Ver http://en.wikipedia.org/wiki/Row-major_order. Las matrices C son fila principal y las matrices Fortran son columnas principales. – tvanfosson
Creo que, ScottieT812 lo escribió mal por accidente: P Esperando su edición;) – israkir
memoria caché es muy rápido y la memoria que se encuentra cerca de la CPU muy caro. En lugar de buscar una pequeña porción de datos de la RAM cada vez, la CPU obtiene un fragmento de datos y los almacena en la caché. La apuesta es que si solo lee un byte, entonces es probable que el siguiente byte que lea sea el correcto. Si este es el caso, entonces puede provenir del caché.
Al diseñar su bucle tal como lo tiene, lee los bytes en el orden en que están almacenados en la memoria. Esto significa que están en la memoria caché y la CPU puede leerlos muy rápidamente. Si cambia las líneas 1 y 2, entonces leería cada "N" bytes cada vez en el ciclo. 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 buscarlos desde la RAM (más lenta) y, por lo tanto, su rendimiento disminuye.
Hay un documento muy bueno de Ulrich Drepper de Red Hat y glibc fame, What Every Programmer Should Know About Memory. Una sección discutió los caches en gran detalle. Por ejemplo, hay efectos de caché en los sistemas SMP donde las CPU pueden terminar arrasando la propiedad de una línea de memoria caché modificada, perjudicando enormemente el rendimiento.
+1 por papel interesante – psihodelia
Esta es la tercera pregunta básica sobre tareas que he visto en los últimos días. Si estás luchando, es posible que quieras contratar un tutor. – tvanfosson
hey, hombre! esto no es tarea ... ¡Me encontré con esto en la clase! Debido a que el maestro estaba hablando en chino, realmente no entendí de qué estaba hablando. Es por eso que quiero preguntarles a todos ... – israkir
Sin embargo, si se trata de tarea, puedo poner la etiqueta 'tarea' por mi cuenta; al igual que lo puse para algunas de mis preguntas recientes antes ... – israkir