Memoria jerárquicaEditar

La memoria jerárquica es una optimización de hardware que toma los beneficios de la localidad espacial y temporal y puede ser utilizada en varios niveles de la jerarquía de memoria. La paginación se beneficia obviamente de la localidad temporal y espacial. Una caché es un ejemplo sencillo de aprovechamiento de la localidad temporal, ya que se trata de una zona de memoria especialmente diseñada, más rápida pero más pequeña, que se utiliza generalmente para mantener los datos referenciados recientemente y los datos cercanos a los datos referenciados recientemente, lo que puede suponer un aumento potencial del rendimiento.

Los elementos de datos de una caché no se corresponden necesariamente con los elementos de datos que están espacialmente cerca en la memoria principal; sin embargo, los elementos de datos se introducen en la caché una línea de caché cada vez. Esto significa que la localización espacial es de nuevo importante: si se hace referencia a un elemento, algunos elementos vecinos también se llevarán a la caché. Por último, la localidad temporal juega un papel en el nivel más bajo, ya que los resultados que se referencian muy juntos pueden mantenerse en los registros de la máquina. Algunos lenguajes de programación (como C) permiten al programador sugerir que ciertas variables se mantengan en los registros.

La localidad de los datos es una característica de referencia de memoria típica de los programas regulares (aunque existen muchos patrones de acceso a la memoria irregulares). Hace que la disposición jerárquica de la memoria sea rentable. En los ordenadores, la memoria se divide en una jerarquía para acelerar los accesos a los datos. Los niveles inferiores de la jerarquía de memoria suelen ser más lentos, pero más grandes. Así, un programa conseguirá un mayor rendimiento si utiliza la memoria mientras está en caché en los niveles superiores de la jerarquía de memoria y evita llevar otros datos a los niveles superiores de la jerarquía que desplazarán a los datos que se utilizarán en breve en el futuro. Esto es un ideal, y a veces no se puede lograr.

Jerarquía de memoria típica (los tiempos de acceso y los tamaños de la caché son aproximaciones de los valores típicos utilizados a partir de 2013 a efectos de discusión; los valores reales y el número real de niveles en la jerarquía varían):

• Registros de la CPU (8-256 registros) – acceso inmediato, con la velocidad del núcleo más interno del procesador
• L1 Cachés de la CPU (32 KiB a 512 KiB) – acceso rápido, con la velocidad del bus de memoria más interno propiedad exclusiva de cada núcleo
• L2 Cachés de la CPU (128 KiB a 24 MiB) – acceso ligeramente más lento, con la velocidad del bus de memoria compartida entre gemelos de núcleos
• L3 cachés de CPU (2 MiB a 32 MiB) – acceso aún más lento, con la velocidad del bus de memoria compartida entre aún más núcleos del mismo procesador
• Memoria física principal (RAM) (256 MiB a 64 GiB) – acceso lento, cuya velocidad está limitada por las distancias espaciales y las interfaces generales de hardware entre el procesador y los módulos de memoria de la placa base
• Disco (memoria virtual, sistema de archivos) (1 GiB a 256 TiB) – muy lento, debido al canal de datos más estrecho (en ancho de bits), físicamente mucho más largo, entre la placa principal del ordenador y los dispositivos de disco, y debido al protocolo de software extraño necesario en la parte superior de la interfaz de hardware lento
• Memoria remota (otros ordenadores o la nube) (prácticamente ilimitado) – la velocidad varía de muy lento a extremadamente lento

Las máquinas modernas tienden a leer bloques de memoria inferior en el siguiente nivel de la jerarquía de memoria. Si esto desplaza la memoria utilizada, el sistema operativo intenta predecir a qué datos se va a acceder menos (o más tarde) y los mueve hacia abajo en la jerarquía de memoria. Los algoritmos de predicción tienden a ser simples para reducir la complejidad del hardware, aunque se están volviendo algo más complicados.

Multiplicación de matricesEditar

Un ejemplo común es la multiplicación de matrices:

for i in 0..n for j in 0..m for k in 0..p C = C + A * B;

Cambiando el orden de los bucles para j y k, la aceleración en las multiplicaciones de matrices grandes se vuelve dramática, al menos para los lenguajes que ponen elementos de matrices contiguas en la última dimensión. Esto no cambia el resultado matemático, pero mejora la eficiencia. En este caso, «grande» significa, aproximadamente, más de 100.000 elementos en cada matriz, o suficiente memoria direccionable como para que las matrices no quepan en las cachés L1 y L2.

for i in 0..n for k in 0..p for j in 0..m C = C + A * B;

La razón de este aumento de velocidad es que en el primer caso, las lecturas de A están en la caché (ya que el índice k es la última dimensión contigua), pero B no lo está, por lo que hay una penalización por pérdida de caché en B. C es irrelevante, porque puede ser sacado del bucle interno – la variable del bucle es k.

for i in 0..n for j in 0..m temp = C for k in 0..p temp = temp + A * B; C = temp

En el segundo caso, las lecturas y escrituras de C están ambas en la caché, las lecturas de B están en la caché, y la lectura de A puede ser sacada del bucle interno.

for i in 0..n for k in 0..p temp = A for j in 0..m C = C + temp * B;

Por lo tanto, el segundo ejemplo no tiene penalización de pérdida de caché en el bucle interno mientras que el primer ejemplo tiene una penalización de caché.

En un procesador del año 2014, el segundo caso es aproximadamente cinco veces más rápido que el primer caso, cuando se escribe en C y se compila con gcc -O3. (Un examen cuidadoso del código desensamblado muestra que en el primer caso, GCC utiliza instrucciones SIMD y en el segundo no, pero la penalización de la caché es mucho peor que la ganancia SIMD.)

La localidad temporal también puede mejorarse en el ejemplo anterior utilizando una técnica llamada bloqueo. La matriz más grande puede dividirse en submatrices de tamaño uniforme, de modo que los bloques más pequeños pueden ser referenciados (multiplicados) varias veces mientras están en memoria.

for (ii = 0; ii < SIZE; ii += BLOCK_SIZE) for (kk = 0; kk < SIZE; kk += BLOCK_SIZE) for (jj = 0; jj < SIZE; jj += BLOCK_SIZE) maxi = min(ii + BLOCK_SIZE, SIZE); for (i = ii; i < maxi; i++) maxk = min(kk + BLOCK_SIZE, SIZE); for (k = kk; k < maxk; k++) maxj = min(jj + BLOCK_SIZE, SIZE); for (j = jj; j < maxj; j++) C = C + A * B;

La localidad temporal de la solución anterior se proporciona porque un bloque puede ser utilizado varias veces antes de seguir adelante, de modo que se mueve dentro y fuera de la memoria con menos frecuencia. La localidad espacial se mejora porque los elementos con direcciones de memoria consecutivas tienden a subir juntos por la jerarquía de memoria.