Las políticas de ubicación de caché son políticas que determinan dónde se puede colocar un bloque de memoria en particular cuando ingresa a un caché de CPU . Un bloque de memoria no puede necesariamente colocarse en una ubicación arbitraria del caché; puede estar restringido a una línea de caché particular o a un conjunto de líneas de caché [1] según la política de ubicación del caché. [2] [3]
Hay tres políticas diferentes disponibles para la colocación de un bloque de memoria en la caché: de asignación directa, totalmente asociativa y de conjunto asociativo. Originalmente, este espacio de organizaciones caché se describió utilizando el término "mapeo de congruencia". [4]
En una estructura de caché de mapeo directo, el caché se organiza en múltiples conjuntos [1] con una única línea de caché por conjunto. Según la dirección del bloque de memoria, solo puede ocupar una única línea de caché. El caché se puede enmarcar como una matriz de columnas de 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 el caché es 256/4, lo que equivale a 64 conjuntos.
La dirección entrante al caché se divide en bits para Offset , Index y Tag .
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é totalmente asociativa, la caché se organiza en un único conjunto de caché con varias 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 enmarcar como una matriz de filas de 1 × m . [5]
Considere 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. 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.
El número total de conjuntos en el caché es 1 y el conjunto contiene 256/4 = 64 líneas de caché, ya que el bloque de caché tiene un tamaño de 4 bytes.
La dirección entrante al caché se divide en bits para desplazamiento y 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 por conjuntos es una compensación entre la caché asignada directamente y la caché totalmente asociativa.
Un caché asociativo de conjuntos se puede imaginar como una matriz n × m . El 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.
El rango de cachés desde mapeado directo hasta completamente asociativo es un continuo de niveles de asociatividad de conjuntos. (Una caché asignada directamente es asociativa por conjuntos unidireccional y una caché totalmente asociativa con m líneas de caché es asociativa por conjuntos de m vías).
Muchas cachés de procesador en los diseños actuales son de mapeo directo, asociativas de conjuntos de dos vías o asociativas 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 2 vías 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 y es asociativo de conjuntos de 2 vías, el número total de conjuntos en el caché es 256/(4 * 2), lo que equivale a 32 conjuntos.
La dirección entrante al 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é y 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 del 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 del 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 del 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 del 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 el caché sesgado , [8] donde el índice para la vía 0 es directo, como arriba, 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 el mapeo directo tienden a no entrar en conflicto cuando se mapean con la función hash, por lo que es menos probable que un programa sufra una cantidad inesperadamente grande de conflictos fallidos debido a un acceso patológico. patrón. 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 antigua, puede resultar difícil determinar qué línea existente se utilizó menos recientemente, porque la nueva línea entra en conflicto con datos en diferentes índices en cada sentido; El seguimiento de LRU para cachés no sesgados generalmente se realiza por conjunto. Sin embargo, los cachés asociativos sesgados tienen grandes ventajas sobre los cachés asociativos de conjuntos convencionales. [10]
Un verdadero caché asociativo por conjuntos prueba todas las formas posibles simultáneamente, utilizando algo así como una memoria direccionable por contenido . Un caché pseudoasociativo prueba cada forma posible, una a la vez. Una caché hash-rehash y una caché asociativa de columnas son ejemplos de una caché pseudoasociativa.
En el caso común de encontrar un acierto en la primera forma probada, un caché pseudoasociativo es tan rápido como un caché de mapeo directo, pero tiene una tasa de errores de conflicto mucho menor que un caché de mapeo directo, más cercano a la tasa de errores. de un caché totalmente asociativo. [9]