Políticas de ubicación de 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 caché está ocupada previamente, los nuevos datos reemplazan el bloque de memoria 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 al conjunto. Si la etiqueta coincide, se produce un acierto de caché y el bloque de caché se devuelve al procesador. De lo contrario, se produce un fallo de caché y el bloque de memoria se obtiene 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.
• Se puede utilizar hardware sencillo y de bajo coste, ya que solo es necesario comprobar una etiqueta a la vez.

• Tiene una tasa de aciertos de caché menor, ya que solo hay una línea de caché disponible en un conjunto. Cada vez que se hace referencia a una nueva memoria del mismo conjunto, la línea de caché se reemplaza, lo que provoca fallos por conflicto. ^{[ 6 ]}

Consideremos una memoria principal de 16 kilobytes, organizada en bloques de 4 bytes, y una caché de mapeo directo de 256 bytes con un tamaño de bloque de 4 bytes. Dado 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 Offset , Index y Tag .

• El desplazamiento corresponde a los bits utilizados para determinar el byte al que se accederá desde la línea de caché. Como 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, dado que 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 coincidir 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é corresponden:

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 de la 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 de la 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 de la 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 de la caché.

• 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, debe colocarse en otra línea de caché con el bit válido 0.
• Si la caché está completamente ocupada, se desaloja un bloque y el bloque de memoria se coloca en esa línea de 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 a todas las líneas de caché. Si coincide, el bloque está presente en la caché y se produce un acierto. Si no coincide, se produce un fallo de caché y debe recuperarse de la memoria inferior.
• En función del desplazamiento, se selecciona un byte y se devuelve al procesador.

• La estructura de caché totalmente asociativa nos brinda la flexibilidad de colocar bloques de memoria en cualquiera de las líneas de caché y, por lo tanto, una 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 fallo de caché.

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

Consideremos una memoria principal de 16 kilobytes, organizada en bloques de 4 bytes, y una caché totalmente asociativa de 256 bytes con un tamaño de bloque de 4 bytes. Dado 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 la 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 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 coincidir con la dirección en la solicitud de caché.

Dado que cualquier bloque de memoria puede asignarse 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.

• El conjunto se determina mediante los bits de índice derivados de la dirección del bloque de memoria.
• The memory block is placed in an available cache line in the set identified, and the tag is stored in the tag field associated with the line. If all the cache lines in the set are occupied, then the new data replaces the block identified through the replacement policy.

• The set is determined by the index bits derived from the address of the memory block.
• The tag bits are compared with the tags of all cache lines present in selected set. If the tag matches any of the cache lines, it is a cache hit and the appropriate line is returned. If the tag does not match any of the lines, then it is a cache miss and the data is requested from next level in the memory hierarchy.

• The placement policy is a trade-off between direct-mapped and fully associative cache.
• It offers the flexibility of using replacement algorithms if a cache miss occurs.

• The placement policy will not effectively use all the available cache lines in the cache and suffers from conflict miss.

Consider a main memory of 16 kilobytes, which is organized as 4-byte blocks, and a 2-way set-associative cache of 256 bytes with a block size of 4 bytes. Because the main memory is 16kB, we need a minimum of 14 bits to uniquely represent a memory address.

Since each cache block is of size 4 bytes and is 2-way set-associative, the total number of sets in the cache is 256/(4 * 2), which equals 32 sets.

The incoming address to the cache is divided into bits for Offset, Index and Tag.

• Offset corresponds to the bits used to determine the byte to be accessed from the cache line. Because the cache lines are 4 bytes long, there are 2 offset bits.
• Index corresponds to bits used to determine the set of the Cache. There are 32 sets in the cache, and because 2^5 = 32, there are 5 index bits.
• Tag corresponds to the remaining bits. This means there are 14 – (5+2) = 7 bits, which are stored in tag field to match the address on cache request.

Below are memory addresses and an explanation of which cache line on which set they map to:

1. Address 0x0000 (tag - 0b000_0000, index – 0b0_0000, offset – 0b00) corresponds to block 0 of the memory and maps to the set 0 of the cache. The block occupies a cache line in set 0, determined by the replacement policy for the cache.
2. Address 0x0004 (tag - 0b000_0000, index – 0b0_0001, offset – 0b00) corresponds to block 1 of the memory and maps to the set 1 of the cache. The block occupies a cache line in set 1, determined by the replacement policy for the cache.
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é.