Las políticas de ubicación de la memoria caché son políticas que determinan dónde se puede colocar un bloque de memoria en particular cuando ingresa en la memoria caché de la CPU . Un bloque de memoria no necesariamente se puede colocar en una ubicación arbitraria en la memoria caché; puede estar restringido a una línea de memoria caché en particular o a un conjunto de líneas de memoria caché [1] por la política de ubicación de la memoria caché. [2] [3]
Existen tres políticas diferentes para la colocación de un bloque de memoria en la caché: mapeo directo, completamente asociativo y asociativo por conjuntos. Originalmente, este espacio de organizaciones de la caché se describía utilizando el término "mapeo de congruencia". [4]
En una estructura de caché de mapeo directo, la caché se organiza en múltiples conjuntos [1] con una sola línea de caché por conjunto. Según la dirección del bloque de memoria, solo puede ocupar una sola línea de caché. La caché se puede estructurar como una matriz de columnas n × 1. [5]
Considere una memoria principal de 16 kilobytes, que está organizada en bloques de 4 bytes, y una caché de mapeo directo de 256 bytes con un tamaño de bloque de 4 bytes. Debido a que la memoria principal es de 16 kB, necesitamos un mínimo de 14 bits para representar de forma única una dirección de memoria.
Dado que cada bloque de caché tiene un tamaño de 4 bytes, el número total de conjuntos en la caché es 256/4, lo que equivale a 64 conjuntos.
La dirección entrante a la caché se divide en bits para Desplazamiento , Índice y Etiqueta .
A continuación se muestran las direcciones de memoria y una explicación de a qué línea de caché se asignan:
0x0000(etiqueta - 0b00_0000, índice – 0b00_0000, desplazamiento – 0b00) corresponde al bloque 0 de la memoria y se asigna al conjunto 0 del caché.0x0004(etiqueta - 0b00_0000, índice – 0b00_0001, desplazamiento – 0b00) corresponde al bloque 1 de la memoria y se asigna al conjunto 1 del caché.0x00FF(etiqueta – 0b00_0000, índice – 0b11_1111, desplazamiento – 0b11) corresponde al bloque 63 de la memoria y se asigna al conjunto 63 del caché.0x0100(etiqueta – 0b00_0001, índice – 0b00_0000, desplazamiento – 0b00) corresponde al bloque 64 de la memoria y se asigna al conjunto 0 del caché.En una caché completamente asociativa, la caché se organiza en un único conjunto de caché con múltiples líneas de caché. Un bloque de memoria puede ocupar cualquiera de las líneas de caché. La organización de la caché se puede estructurar como una matriz de filas de 1 × m . [5]
Consideremos una memoria principal de 16 kilobytes, que está organizada en bloques de 4 bytes, y una caché totalmente asociativa de 256 bytes y un tamaño de bloque de 4 bytes. Como la memoria principal tiene 16 kB, necesitamos un mínimo de 14 bits para representar de forma única una dirección de memoria.
El número total de conjuntos en la memoria caché es 1, y el conjunto contiene 256/4=64 líneas de memoria caché, ya que el bloque de memoria caché tiene un tamaño de 4 bytes.
La dirección entrante a la caché se divide en bits para el desplazamiento y la etiqueta.
Dado que cualquier bloque de memoria se puede asignar a cualquier línea de caché, el bloque de memoria puede ocupar una de las líneas de caché según la política de reemplazo.
La caché asociativa de conjuntos es un equilibrio entre la caché asignada directamente y la caché totalmente asociativa.
Una caché asociativa de conjuntos se puede imaginar como una matriz n × m . La caché se divide en 'n' conjuntos y cada conjunto contiene 'm' líneas de caché. Primero se asigna un bloque de memoria a un conjunto y luego se coloca en cualquier línea de caché del conjunto.
La gama de cachés, desde los de mapeo directo hasta los completamente asociativos, es un continuo de niveles de asociatividad de conjuntos. (Un caché de mapeo directo es asociativo de conjuntos unidireccional y un caché completamente asociativo con m líneas de caché es asociativo de conjuntos m -direccional).
Muchos cachés de procesadores en los diseños actuales son de mapeo directo, asociativos de conjuntos de dos vías o asociativos de conjuntos de cuatro vías. [5]
Considere una memoria principal de 16 kilobytes, que está organizada en bloques de 4 bytes, y una caché asociativa de conjuntos de 2 vías de 256 bytes con un tamaño de bloque de 4 bytes. Debido a que la memoria principal tiene 16 kB, necesitamos un mínimo de 14 bits para representar de forma única una dirección de memoria.
Dado que cada bloque de caché tiene un tamaño de 4 bytes y es asociativo de conjuntos bidireccional, la cantidad total de conjuntos en la caché es 256/(4 * 2), lo que equivale a 32 conjuntos.
La dirección entrante a la caché se divide en bits para Desplazamiento, Índice y Etiqueta.
A continuación se muestran las direcciones de memoria y una explicación de a qué línea de caché en qué conjunto se asignan:
0x0000(etiqueta - 0b000_0000, índice – 0b0_0000, desplazamiento – 0b00) corresponde al bloque 0 de la memoria y se asigna al conjunto 0 de la caché. El bloque ocupa una línea de caché en el conjunto 0, determinada por la política de reemplazo de la caché.0x0004(etiqueta - 0b000_0000, índice – 0b0_0001, desplazamiento – 0b00) corresponde al bloque 1 de la memoria y se asigna al conjunto 1 de la caché. El bloque ocupa una línea de caché en el conjunto 1, determinada por la política de reemplazo de la caché.0x00FF(etiqueta – 0b000_0001, índice – 0b1_1111, desplazamiento – 0b11) corresponde al bloque 63 de la memoria y se asigna al conjunto 31 de la caché. El bloque ocupa una línea de caché en el conjunto 31, determinada por la política de reemplazo de la caché.0x0100(etiqueta – 0b000_0010, índice – 0b0_0000, desplazamiento – 0b00) corresponde al bloque 64 de la memoria y se asigna al conjunto 0 de la caché. El bloque ocupa una línea de caché en el conjunto 0, determinada por la política de reemplazo de la caché.Se han sugerido otros esquemas, como la caché sesgada [8] , donde el índice para la vía 0 es directo, como se mencionó anteriormente, pero el índice para la vía 1 se forma con una función hash . Una buena función hash tiene la propiedad de que las direcciones que entran en conflicto con la asignación directa tienden a no entrar en conflicto cuando se asignan con la función hash, y por lo tanto es menos probable que un programa sufra una cantidad inesperadamente grande de errores de conflicto debido a un patrón de acceso patológico. La desventaja es la latencia adicional al calcular la función hash. [9] Además, cuando llega el momento de cargar una nueva línea y desalojar una línea anterior, puede ser difícil determinar qué línea existente se usó menos recientemente, porque la nueva línea entra en conflicto con datos en diferentes índices en cada vía; el seguimiento de LRU para cachés no sesgados generalmente se realiza por conjunto. Sin embargo, los cachés asociativos sesgados tienen ventajas importantes sobre los asociativos por conjunto convencionales. [10]
Una verdadera caché asociativa de conjuntos prueba todas las formas posibles simultáneamente, utilizando algo así como una memoria direccionable por contenido . Una caché pseudoasociativa prueba cada forma posible de a una por vez. Una caché de hash-rehash y una caché asociativa de columnas son ejemplos de una caché pseudoasociativa.
En el caso común de encontrar un resultado de la primera manera probada, un caché pseudoasociativo es tan rápido como un caché mapeado directamente, pero tiene una tasa de errores de conflicto mucho menor que un caché mapeado directamente, más cercana a la tasa de errores de un caché completamente asociativo. [9]