Cheatsheet Ejercicios caché

Funciones de correspondencia

📌

Estrategia de correspondencia directa

🔎

Para hallar la línea a la que haremos corresponder un cierto bloque usaremos la expresión:

\boxed{nl = n\_blk\ \%\ l\_totates}

$nl$ → Número de línea

$n\_blk$ → Número de bloque

$l\_totales$ → Líneas totales de la caché

💡

Para saber como se distribuyen los bits de una dirección entre los diferentes parámetros, debemos consultar las especificaciones de la memoria, ya que la distribución del tamaño que abarcan estos parámetros depende de los siguientes valores:

Tamaño de las direcciones de memoria (en bits) → $n$

Número de líneas de la caché → $r = \log_2(x)$

Tamaño de los bloques (en words) → $q = \log_2(x)$

Tamaño de palabra (en bytes) → $p = \log_2(x)$

Etiqueta	Índice de línea	Desplazamiento de palabra	Desplazamiento de byte
$n-r-q-p$	$r$	$q$	$p$

📌

Estrategia de correspondencia totalmente asociativa

🔎

Un bloque puede asignarse a cualquier línea

💡

Debemos recordar que para extraer la información contenida en los bits de una dirección según esta estrategia, debemos conocer los siguientes parámetros

Tamaño de las direcciones de memoria (en bits) → $n$

Tamaño de los bloques (en words) → $q = \log_2(x)$

Tamaño de palabra (en bytes) → $p = \log_2(x)$

Etiqueta	Desplazamiento de palabra	Desplazamiento de byte
$n - q - p$	$q$	$p$

📌

Estrategia de correspondencia asociativa por conjuntos

📖

Cada uno de los conjuntos de la memoria principal se hace corresponder con un conjunto de la caché usando el método de correspondencia directa, una vez asignada la correspondencia del conjunto, ahora cada bloque del conjunto (memoria) se hace corresponder con cada línea del conjunto (caché) usando la estrategia de correspondencia totalmente asociativa

Asignación de un bloque (memoria) a un conjunto de la caché

\boxed{nc = nb\ \%\ nc\_total}

$nc$ → Número de conjunto (caché)

$nb$ → Número de bloque (memoria principal)

$nc\_total$ → Número total de conjuntos (caché)

💡

Para poder calcular la cantidad de bits que abarca cada parámetro debemos conocer las siguientes características del sistema

Tamaño de las direcciones de memoria (en bits) → $n$

Número de conjuntos de la caché → $s = \log_2(x)$

Tamaño de los bloques (en words) → $q = \log_2(x)$

Tamaño de palabra (en bytes) → $p = \log_2(x)$

Etiqueta	Índice de conjunto	Desplazamiento de palabra	Desplazamiento de palabra
$n - s - q -p$	$s$	$q$	$p$

Algoritmos de reemplazo

📖

El algoritmo de reemplazo establece el criterio que se utilizará para determinar en qué línea, de entre las accesibles a través de las vías de dicho bloque, debemos almacenar el dato

Diferentes algoritmos de reemplazo:

Aleatorio

La línea se elige al azar entre las posibles a través de las vías de dicho bloque. Esta técnica es casi tan buena como las otras

Least-Recently Used (LRU)

Esta técnica utiliza el criterio de localidad temporal, siendo así que los datos que llevan más tiempo sin ser referenciados, son reemplazados
Require añadir a la linea unos bits de uso, estos consisten en unos contadores que llevan la cuenta de qué líneas han sido las más recientemente accedidas

Least-Frequently Used (LFU)

A diferencia del LRU, este algoritmo reemplazará los datos que menos veces han sido referenciados, sin importar si han sido utilizados recientemente
Require añadir unos bits a modo de contador de aciertos

First-In-First-Out (FIFO)

Este algoritmo almacena los datos como si estos pertenecieran a una cola, por lo que los datos se almacenan en la línea del dato que lleva más tiempo en la caché

Óptimo (ideal)

Este algoritmo consiste en reemplazar el dato que no va a ser utilizado durante más tiempo.
Este algoritmo no siempre es posible de implementar ya que requiere que podamos hacer una previsión de qué datos vamos a referenciar y cuando

🟢

Acierto en la caché al leer

Este caso no supone ningún problema para el flujo normal del programa

🔴

Fallo en la caché al leer

Cuando ocurre un fallo, se consulta el dato deseado en un nivel inferior de la jerarquía. El ciclo de la instrucción actual es reiniciado debido a que el acceso al dato cuando este se encuentra en unidades inferiores en la jerarquía puede tardar varios ciclos

💡

Si lo que estamos consultando es una instrucción, se debe restar

4

al valor actual de PC ya que este se incrementa al principio del ciclo

🟢

Acierto en la caché al escribir

Cuando ocurre un acierto en el acceso a un dato el cual deseamos actualizar, debemos decidir cuando actualizaremos el dato en memoria principal

Write-through (inmediatamente)

El dato se actualiza tanto en la caché como en la memoria principal

Se utiliza un buffer de escritura

Write-back (retardado)

El dato solo se escribe en caché, y solo se vuelca en la memoria principal cuando haya que reemplazar el dato en la caché

Bit sucio (dirty bit, D) → Este es un bit en memoria principal que indica que el bloque tiene modificaciones pendientes

🔴

Fallo en la caché al escribir

En estos casos existen dos estrategias

Write Allocate (fetch on write)

Se trae el bloque a la caché y luego se gestiona como un acierto. Se suele combinar con write-back

No-Write Allocate (write around)

Se modifica el bloque en la memoria principal pero no en la caché. Se suele combinar con write-through

Medición de rendimiento

ℹ️

Este parámetro mide el tiempo medio de acceso a un dato en memoria: AMAT (Average memory access time)

Opción 1 (Fórmula de la media ponderada)
tasa_acierto → Proporción de aciertos (tanto por uno)
tiempo_acierto → Tiempo necesario para acceder a un dato en cache (acierto)
tasa_fallo → Proporción de fallos (tanto por uno)
tiempo_fallo → tiempo_acierto $+$ penalizacion_fallo
$AMAT =\\tasa\_acierto \times tiempo\_acierto + tasa\_fallo \times tiempo\_fallo$

Opción 2
tiempo_acierto → Tiempo necesario para acceder a un dato en cache (acierto)
tasa_fallo → Proporción de fallos (tanto por uno)
penalizacion_fallo → Tiempo extra necesario tras un fallo para acceder a memoria (penalización_fallo)
$AMAT = \\ tiempo\_acierto + tasa\_fallo \times penalizacion\_fallo$

⚠️

La penailzacion_fallo / tiempo_fallo hay que multiplicarla por el número de palabras por bloque. Ya que cada fallo require mover todos un bloque palabra por palabra