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 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]

• 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 caché estaba ocupada previamente, los nuevos datos reemplazan el bloque de memoria en el 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, se produce un acierto en la memoria caché y el bloque de memoria se devuelve al procesador. De lo contrario, se produce un error en la memoria caché y el bloque de memoria se recupera de la memoria inferior ( memoria principal , disco ).

• Esta política de ubicación es energéticamente eficiente ya que evita la búsqueda en todas las líneas de caché.
• La política de colocación y la política de reemplazo son sencillas.
• Requiere hardware barato ya que sólo es necesario verificar una etiqueta a la vez.

• 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 en el mismo conjunto, se reemplaza la línea de caché, lo que provoca errores de conflicto. ^[6]

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 .

• El desplazamiento corresponde a los bits utilizados para determinar el byte al que se accederá desde la línea de caché. Debido a que las líneas de caché tienen una longitud de 4 bytes, 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 coincidan 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:

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é.

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]

• La línea de caché se selecciona en función del 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, se debe colocar en otra línea de caché con el bit válido 0.
• Si la memoria caché está completamente ocupada, se expulsa un bloque y el bloque de memoria se coloca en esa línea de memoria caché.
• La expulsión de un bloque de memoria de la caché se decide mediante la política de reemplazo. ^[7]

• El campo de 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, es un error de caché y debe buscarse en la memoria inferior.
• En función del desplazamiento, se selecciona un byte y se devuelve al procesador.

• La estructura de caché totalmente asociativa nos proporciona la flexibilidad de colocar bloques de memoria en cualquiera de las líneas de caché y, por lo tanto, la utilización completa del 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 ocurre una falla de caché.

• La política de ubicación consume mucha energía, ya que el circuito de comparación debe recorrer todo el caché para localizar un bloque.
• El más caro de todos los métodos, debido al elevado coste del hardware de comparación asociativa.

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.

• El desplazamiento corresponde a los bits utilizados para determinar el byte al que se accederá desde la línea de caché. En el ejemplo, hay 2 bits de desplazamiento, 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 coincidan 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.

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 unidireccionalmente asociativo de conjuntos y un caché completamente asociativo con m líneas de caché es m -direccionalmente asociativo de conjuntos).

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]

• 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 .

• 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é, se trata de un acierto de caché y se devuelve la línea correspondiente. Si la etiqueta no coincide con ninguna de las líneas, se trata de un error de caché y los datos se solicitan desde el siguiente nivel en la jerarquía de memoria.

• La política de ubicación es un equilibrio entre el caché mapeado directamente y el caché totalmente asociativo.
• Ofrece la flexibilidad de utilizar algoritmos de reemplazo si ocurre una falla de caché.

• La política de ubicación no utilizará eficazmente todas las líneas de caché disponibles en la memoria caché y sufrirá conflictos .

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.

• El desplazamiento corresponde a los bits utilizados para determinar el byte al que se accederá desde la línea de caché. Debido a que las líneas de caché tienen una longitud de 4 bytes, 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 coincidan 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é 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é.

Se han sugerido otros esquemas, como la caché sesgada ^[8] , donde el índice para la vía 0 es directo, como se indicó 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]

• Asociatividad
• Política de reemplazo de caché
• Jerarquía de caché
• Políticas de redacción
• Coloración de caché