stringtranslate.com

Políticas de ubicación de caché

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]

Caché mapeado directamente

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]

Para colocar un bloque en la caché

Para buscar una palabra en la caché

Ventajas

Desventaja

Ejemplo

Caché de mapeo directo

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:

  1. 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 del caché.
  2. 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 del caché.
  3. 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 del caché.
  4. 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 del caché.

Caché completamente asociativa

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]

Para colocar un bloque en la caché

Para buscar una palabra en la caché

Caché completamente asociativa

Ventajas

Desventajas

Ejemplo

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.

Caché asociativo por conjuntos

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]

Para colocar un bloque en la caché

Para localizar una palabra en la caché

Ventajas

Desventajas

Ejemplo

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.

Caché asociativo por 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:

  1. La dirección 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é.
  2. La dirección 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é.
  3. La dirección 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é.
  4. La dirección 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é.

Caché asociativa sesgada bidireccional

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]

Caché pseudoasociativa

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]

Véase también

Referencias

  1. ^ abcde "Los conceptos básicos del caché" (PDF) .
  2. ^ "Políticas de ubicación de caché". Archivado desde el original el 21 de febrero de 2020.
  3. ^ "Políticas de colocación". Archivado desde el original el 14 de agosto de 2020.
  4. ^ Mattson, RL ; Gecsei, J.; Slutz, DR; Traiger, I (1970). "Técnicas de evaluación para jerarquías de almacenamiento". IBM Systems Journal . 9 (2): 78–117. doi :10.1147/sj.92.0078.
  5. ^ abc Solihin, Yan (2015). Fundamentos de la arquitectura paralela multinúcleo . Taylor y Francisco. págs. 136-141. ISBN 978-1482211184.
  6. ^ "Tipos de errores de caché" (PDF) .
  7. ^ "Caché totalmente asociativa". Archivado desde el original el 24 de diciembre de 2017.
  8. ^ 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 .
  9. ^ ab C. Kozyrakis . "Conferencia 3: técnicas avanzadas de almacenamiento en caché" (PDF) . Archivado desde el original (PDF) el 7 de septiembre de 2012.
  10. ^ Microarquitectura "Los cachés asociativos sesgados tienen... ventajas importantes sobre los cachés asociativos de conjuntos convencionales".