Un caché de CPU es una memoria que contiene los datos utilizados recientemente por el procesador. Un bloque de memoria no se puede colocar necesariamente al azar en la caché y puede estar restringido a una sola línea de caché o un conjunto de líneas de caché [1] por la política de ubicación de la caché . [2] [3] En otras palabras, la política de ubicación de la caché determina dónde se puede colocar un bloque de memoria en particular cuando entra en la caché.
Hay tres políticas diferentes disponibles para la ubicación de un bloque de memoria en la caché: mapeado directo, completamente asociativo y asociativo por conjuntos. Originalmente, este espacio de organizaciones de caché se describió utilizando el término "mapeo de congruencia". [4]
Caché de asignación directa
En una estructura de caché mapeada directamente, la caché se organiza en varios 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é. La caché se puede enmarcar como una matriz de columnas (n * 1). [5]
Para colocar un bloque en el caché
- El conjunto está determinado por los bits de índice [1] derivados de la dirección del bloque de memoria.
- El bloque de memoria se coloca en el conjunto identificado y la etiqueta [1] se almacena en el campo de etiqueta asociado con el conjunto.
- Si la línea de la caché estaba ocupada anteriormente, los nuevos datos reemplazan el bloque de memoria en la caché.
Para buscar una palabra en la caché
- El conjunto se identifica mediante los bits de índice de la dirección.
- Los bits de etiqueta derivados de la dirección del bloque de memoria se comparan con los bits de etiqueta asociados con el conjunto. Si la etiqueta coincide, hay un acierto de caché y el bloque de caché se devuelve al procesador. De lo contrario, hay una falta de caché y el bloque de memoria se recupera de la memoria inferior ( memoria principal , disco ).
Ventajas
- Esta política de ubicación es energéticamente eficiente ya que evita la búsqueda a través de todas las líneas de caché.
- La política de colocación y la política de reemplazo es simple.
- Requiere hardware barato, ya que solo se debe verificar una etiqueta a la vez.
Desventaja
- Tiene una tasa de aciertos de caché más baja, ya que solo hay una línea de caché disponible en un conjunto. Cada vez que se hace referencia a una nueva memoria al mismo conjunto, se reemplaza la línea de caché, lo que provoca que se pierda el conflicto. [6]
Ejemplo
Considere una memoria principal de 16 kilobytes, que está organizada como bloques de 4 bytes, y una caché de asignación directa 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 de entrada a la caché se divide en bits para Offset , Index y Tag .
- El desplazamiento corresponde a los bits utilizados para determinar el byte al que se accede desde la línea de caché. Debido a que las líneas de caché tienen 4 bytes de longitud, hay 2 bits de desplazamiento .
- El índice corresponde a los bits utilizados para determinar el conjunto de la caché. Hay 64 conjuntos en la caché y, como 2 ^ 6 = 64, hay 6 bits de índice.
- La etiqueta corresponde a los bits restantes. Esto significa que hay 14 - (6 + 2) = 6 bits de etiqueta , que se almacenan en el campo de etiqueta para que coincida con la dirección en la solicitud de caché.
A continuación se muestran las direcciones de memoria y una explicación de a qué línea de caché se asignan:
- La dirección
0x0000
(etiqueta -0b00_0000
, índice -0b00_0000
, desplazamiento -0b00
) corresponde al bloque 0 de la memoria y se asigna al conjunto 0 de la caché. - La dirección
0x0004
(etiqueta -0b00_0000
, índice -0b00_0001
, desplazamiento -0b00
) corresponde al bloque 1 de la memoria y se asigna al conjunto 1 de la caché. - La dirección
0x00FF
(etiqueta -0b00_0000
, índice -0b11_1111
, desplazamiento -0b11
) corresponde al bloque 63 de la memoria y se asigna al conjunto 63 de la caché. - La dirección
0x0100
(etiqueta -0b00_0001
, índice -0b00_0000
, desplazamiento -0b00
) corresponde al bloque 64 de la memoria y se asigna al conjunto 0 de la caché.
Caché completamente asociativo
En un caché completamente asociativo, el 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 (1 * m). [5]
Para colocar un bloque en el caché
- La línea de caché se selecciona basándose en el bit válido [1] asociado a ella. Si el bit válido es 0, el nuevo bloque de memoria se puede colocar en la línea de caché, de lo contrario, debe colocarse en otra línea de caché con el bit 0 válido.
- Si la caché está completamente ocupada, se desaloja un bloque y el bloque de memoria se coloca en esa línea de caché.
- La política de sustitución decide el desalojo del bloque de memoria del caché. [7]
Para buscar una palabra en la caché
- El campo Etiqueta de la dirección de memoria se compara con los bits de etiqueta asociados con todas las líneas de caché. Si coincide, el bloque está presente en la caché y es un acierto de caché. Si no coincide, entonces es un error de caché y debe buscarse desde la memoria inferior.
- Según el desplazamiento, se selecciona un byte y se devuelve al procesador.
Ventajas
- La estructura de caché completamente asociativa nos proporciona la flexibilidad de colocar el bloque de memoria en cualquiera de las líneas de caché y, por lo tanto, la utilización completa de la caché.
- La política de ubicación proporciona una mejor tasa de aciertos de caché.
- Ofrece la flexibilidad de utilizar una amplia variedad de algoritmos de reemplazo si se produce un error de caché
Desventaja
- La política de ubicación es lenta ya que lleva tiempo recorrer todas las líneas.
- La política de ubicación consume mucha energía, ya que tiene que iterar sobre todo el conjunto de caché para ubicar un bloque.
- El más caro de todos los métodos, debido al alto costo del hardware de comparación asociativa.
Ejemplo
Considere una memoria principal de 16 kilobytes, que está organizada como 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.
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 o líneas de caché.
La dirección de entrada a la caché se divide en bits para desplazamiento y etiqueta.
- El desplazamiento corresponde a los bits utilizados para determinar el byte al que se accede desde la línea de caché. En el ejemplo, hay 2 bits de compensación, que se utilizan para direccionar los 4 bytes de la línea de caché.
- La etiqueta corresponde a los bits restantes. Esto significa que hay 14 - (2) = 12 bits de etiqueta , que se almacenan en el campo de etiqueta para que coincida con la dirección en la solicitud de caché.
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.
Caché asociativo de conjuntos
La caché asociativa de conjuntos es una compensación entre la caché mapeada directamente y la caché completamente asociativa.
Una caché asociativa 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é. Un bloque de memoria se asigna primero a un conjunto y luego se coloca en cualquier línea de caché del conjunto.
El rango de cachés desde el mapeado directo hasta el totalmente asociativo es un continuo de niveles de asociatividad de conjuntos. (Una caché de mapeo directo es asociativa por conjuntos unidireccional y una caché completamente asociativa con m líneas de caché es asociativa por conjuntos de m vías).
Muchas memorias caché de procesador en los diseños actuales están mapeadas directamente, asociativas de conjuntos bidireccionales o asociativas de conjuntos de cuatro vías. [5]
Para colocar un bloque en el caché
- El conjunto está determinado por los bits de índice derivados de la dirección del bloque de memoria.
- El bloque de memoria se coloca en una línea de caché disponible en el conjunto identificado, y la etiqueta se almacena en el campo de etiqueta asociado con la línea. Si todas las líneas de caché del conjunto están ocupadas, los nuevos datos reemplazan el bloque identificado a través de la política de reemplazo .
Para ubicar una palabra en el caché
- El conjunto está determinado por los bits de índice derivados de la dirección del bloque de memoria.
- Los bits de etiqueta se comparan con las etiquetas de todas las líneas de caché presentes en el conjunto seleccionado. Si la etiqueta coincide con alguna de las líneas de caché, es un acierto de caché y se devuelve la línea correspondiente. Si la etiqueta no coincide con ninguna de las líneas, entonces es una falta de caché y los datos se solicitan desde el siguiente nivel en la jerarquía de memoria.
Ventajas
- La política de ubicación es una compensación entre la caché mapeada directamente y la completamente asociativa.
- Ofrece la flexibilidad de utilizar algoritmos de reemplazo si se produce un error de caché.
Desventajas
- La política de ubicación no utilizará de manera efectiva todas las líneas de caché disponibles en la caché y sufre de errores de conflicto .
Ejemplo
Considere una memoria principal de 16 kilobytes, que está organizada como 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 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 la caché es 256 / (4 * 2), lo que equivale a 32 conjuntos.
La dirección de entrada a la caché se divide en bits para Offset, Index y Tag.
- El desplazamiento corresponde a los bits utilizados para determinar el byte al que se accede desde la línea de caché. Debido a que las líneas de caché tienen 4 bytes de longitud, hay 2 bits de desplazamiento .
- El índice corresponde a los bits utilizados para determinar el conjunto de la caché. Hay 32 conjuntos en la caché y, como 2 ^ 5 = 32, hay 5 bits de índice.
- La etiqueta corresponde a los bits restantes. Esto significa que hay 14 - (5 + 2) = 7 bits , que se almacenan en el campo de etiqueta para que coincida con la dirección en la solicitud de caché.
A continuación se muestran las direcciones de memoria y una explicación de qué línea de caché en qué conjunto se asignan:
- La dirección
0x0000
(etiqueta -0b00_0000
, índice -0b00_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é. - La dirección
0x0004
(etiqueta -0b00_0000
, índice -0b00_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 0, determinada por la política de reemplazo de la caché. - La dirección
0x00FF
(etiqueta -0b00_0000
, índice -0b11_1111
, desplazamiento -0b11
) corresponde al bloque 63 de la memoria y se asigna al conjunto 63 de la caché. El bloque ocupa una línea de caché en el conjunto 31, determinada por la política de sustitución de la caché. - La dirección
0x0100
(etiqueta -0b00_0001
, índice -0b00_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é.
Caché asociativo sesgado bidireccional
Se han sugerido otros esquemas, como la caché sesgada , [8] donde el índice de la vía 0 es directo, como se indicó anteriormente, pero el índice de 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 un número inesperadamente grande de errores de conflicto 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 antigua, puede ser difícil determinar qué línea existente se utilizó menos recientemente, porque la nueva línea entra en conflicto con los datos de 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 ventajas importantes sobre los asociativos de conjuntos convencionales. [10]
Caché pseudoasociativo
Una verdadera caché asociativa de conjuntos prueba todas las formas posibles simultáneamente, utilizando algo como una memoria direccionable por contenido . Una caché pseudoasociativa prueba todas las formas posibles una a la vez. Una caché de repetición de hash y una caché asociativa de columnas son ejemplos de una caché pseudoasociativa.
En el caso común de encontrar un acierto de la primera forma 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 cerca de la tasa de errores. de un caché totalmente asociativo. [9]
Ver también
Referencias
- ^ a b c d e "Los conceptos básicos de la caché" (PDF) .
- ^ "Políticas de colocación de caché" .
- ^ "Políticas de colocación" .
- ^ Mattson, RL ; Gecsei, J .; Slutz, DR; Traiger, yo (1970). "Técnicas de evaluación para jerarquías de almacenamiento". Revista de sistemas de IBM . 9 (2): 78-117. doi : 10.1147 / sj.92.0078 .
- ^ a b c Solihin, Yan (2015). Fundamentos de la arquitectura multinúcleo en paralelo . Taylor y Francis. págs. 136-141. ISBN 978-1482211184.
- ^ "Tipos de errores de caché" (PDF) .
- ^ "Caché totalmente asociativo" .
- ^ André Seznec (1993). "Un caso para cachés asociativos sesgados bidireccionales". ACM SIGARCH Computer Architecture News . 21 (2): 169-178. doi : 10.1145 / 173682.165152 .
- ^ a b C. Kozyrakis. "Lección 3: Técnicas avanzadas de almacenamiento en caché" (PDF) . Archivado desde el original (PDF) el 7 de septiembre de 2012.
- ^ Microarquitectura "cachés sesgada asociativos tienen ... grandes ventajas con respecto a las memorias caché de asociación de conjuntos convencionales."