caching - que - memoria cache mapeo

¿Cómo funciona el caché mapeado directo? (4)

Estoy tomando un curso de Arquitectura del sistema y tengo problemas para entender cómo funciona un caché mapeado directo.

He buscado en varios lugares y lo explican de manera diferente, lo que me confunde aún más.

Lo que no puedo entender es qué etiqueta e índice, y cómo se seleccionan?

La explicación de mi conferencia es: "Dirección dividida se divide en dos partes (por ejemplo, 15 bits) utilizada para direccionar (32k) RAM directamente. Resto de la dirección, la etiqueta se almacena y se compara con la etiqueta entrante".

¿De dónde viene esa etiqueta? No puede ser la dirección completa de la ubicación de la memoria en la memoria RAM ya que inutiliza la memoria caché asignada directa (en comparación con la memoria caché totalmente asociativa).

Muchas gracias.

Bueno. Entonces, primero comprendamos cómo la CPU interactúa con la memoria caché.

Hay tres capas de memoria (ampliamente hablando): cache (generalmente hecha de chips SRAM ), main memory (generalmente hecha de chips DRAM ) y storage (generalmente magnéticos, como discos duros). Cada vez que la CPU necesita datos de una ubicación en particular, primero busca en la memoria caché para ver si está allí. La memoria caché se encuentra más cerca de la CPU en términos de jerarquía de memoria, por lo que su tiempo de acceso es menor (y el costo es el más alto), por lo que si la CPU de datos está buscando allí, constituye un ''hit'', y los datos se obtiene desde allí para su uso por la CPU. Si no está allí, entonces los datos tienen que moverse de la memoria principal a la caché antes de que la CPU pueda acceder a ella (la CPU generalmente interactúa solo con la memoria caché), que incurre en una penalización de tiempo.

Entonces, para saber si los datos están ahí o no en la caché, se aplican varios algoritmos. Uno es este método de caché mapeado directo. Para simplificar, supongamos que hay un sistema de memoria en el que hay 10 ubicaciones de memoria caché (numeradas de 0 a 9) y 40 ubicaciones de memoria principal disponibles (numeradas del 0 al 39). Esta imagen lo resume:

Hay 40 ubicaciones de memoria principal disponibles, pero solo se pueden acomodar hasta 10 en la memoria caché. Entonces, de alguna manera, la solicitud entrante de la CPU necesita ser redirigida a una ubicación de caché. Eso tiene dos problemas:

¿Cómo redirigir? Específicamente, ¿cómo hacerlo de una manera predecible que no cambiará con el tiempo?
Si la ubicación de la memoria caché ya está llena de algunos datos, la solicitud entrante de la CPU debe identificar si la dirección de la que requiere los datos es la misma que la dirección cuyos datos se almacenan en esa ubicación.

En nuestro ejemplo simple, podemos redirigir mediante una lógica simple. Dado que tenemos que mapear 40 ubicaciones de memoria principal numeradas en serie de 0 a 39 a 10 ubicaciones de caché numeradas del 0 al 9, la ubicación del caché para una ubicación de memoria n puede ser n%10 . Entonces 21 corresponde a 1, 37 corresponde a 7, etc. Eso se convierte en el índice .

Pero 37, 17, 7 corresponden todos a 7. Entonces, para diferenciarlos, viene la etiqueta . Así que al igual que el índice es n%10 , la etiqueta es int(n/10) . Así que ahora 37, 17, 7 tendrán el mismo índice 7, pero diferentes etiquetas como 3, 1, 0, etc. Es decir, la asignación puede ser completamente especificada por los dos datos: etiqueta e índice.

Entonces, si llega una solicitud para la ubicación de la dirección 29, se traducirá en una etiqueta de 2 y un índice de 9. El índice corresponde al número de ubicación de la memoria caché, por lo que la ubicación del caché no. Se consultará 9 para ver si contiene datos, y si es así, si la etiqueta asociada es 2. Si es así, se trata de un golpe de CPU y los datos se obtendrán de esa ubicación de inmediato. Si está vacío, o la etiqueta no es 2, significa que contiene los datos correspondientes a otra dirección de memoria y no a 29 (aunque tendrá el mismo índice, lo que significa que contiene datos de una dirección como 9, 19, 39, etc.). Por lo tanto, es una falla de CPU, y los datos de la ubicación no. 29 en la memoria principal tendrá que cargarse en la memoria caché en la ubicación 29 (y la etiqueta se cambió a 2, y eliminar los datos que estaban allí antes), después de lo cual la CPU la extrajo.

Encontré un buen libro en la biblioteca que me ofreció la explicación clara que necesitaba y ahora la compartiré aquí en caso de que algún otro estudiante tropiece con este hilo mientras busca los cachés.

El libro es "Computer Architecture - A Quantitative Approach" 3ª edición de Hennesy y Patterson, página 390.

Primero, tenga en cuenta que la memoria principal está dividida en bloques para la memoria caché. Si tenemos un caché de 64 bytes y 1 GB de RAM, la RAM se dividirá en bloques de 128 KB (1 GB de RAM / 64B de caché = 128 KB de tamaño de bloque).

Del libro:

¿Dónde se puede colocar un bloque en un caché?

Si cada bloque tiene un solo lugar, puede aparecer en el caché, se dice que el caché está mapeado directamente . El bloque de destino se calcula con esta fórmula: <RAM Block Address> MOD <Number of Blocks in the Cache>

Entonces, supongamos que tenemos 32 bloques de RAM y 8 bloques de caché.

Si queremos almacenar el bloque 12 de la RAM en la memoria caché, el bloque RAM 12 se almacenará en el bloque Caché 4. ¿Por qué? Porque 12/8 = 1 resto 4. El resto es el bloque de destino.

Si se puede colocar un bloque en cualquier lugar de la memoria caché, se dice que la memoria caché es totalmente asociativa .
Si un bloque se puede colocar en cualquier lugar de un conjunto restringido de lugares en el caché, el caché se establece de forma asociativa .

Básicamente, un conjunto es un grupo de bloques en el caché. Primero se asigna un bloque a un conjunto y luego el bloque se puede colocar en cualquier lugar dentro del conjunto.

La fórmula es: <RAM Block Address> MOD <Number of Sets in the Cache>

Entonces, supongamos que tenemos 32 bloques de RAM y un caché dividido en 4 conjuntos (cada conjunto tiene dos bloques, lo que significa 8 bloques en total). De esta forma, el conjunto 0 tendría los bloques 0 y 1, el conjunto 1 tendría los bloques 2 y 3, y así sucesivamente ...

Si queremos almacenar el bloque 12 de RAM en la memoria caché, el bloque de RAM se almacenará en los bloques de memoria caché 0 o 1. ¿Por qué? Porque 12/4 = 3, resto 0. Por lo tanto, se selecciona el conjunto 0 y el bloque se puede colocar en cualquier lugar dentro del conjunto 0 (es decir, el bloque 0 y 1).

Ahora volveré a mi problema original con las direcciones.

¿Cómo se encuentra un bloque si está en la memoria caché?

Cada cuadro de bloque en el caché tiene una dirección. Para dejarlo en claro, un bloque tiene direcciones y datos.

La dirección del bloque se divide en varias partes: etiqueta, índice y desplazamiento.

La etiqueta se usa para encontrar el bloque dentro de la caché, el índice solo muestra el conjunto en el que se encuentra el bloque (lo que lo hace bastante redundante) y el desplazamiento se usa para seleccionar los datos.

Con "seleccionar los datos" me refiero a que en un bloque de caché obviamente habrá más de una ubicación de memoria, el desplazamiento se usa para seleccionar entre ellos.

Entonces, si quieres imaginar una tabla, estas serían las columnas:

Tag se usaría para encontrar el bloque, el índice mostraría en qué conjunto está el bloque, offset seleccionaría uno de los campos a su derecha.

Espero que mi comprensión de esto sea correcta, si no es así, háganmelo saber.

Un caché mapeado directo es como una tabla que tiene filas también llamadas líneas de caché y al menos 2 columnas, una para los datos y la otra para las etiquetas.

Así es como funciona: Un acceso de lectura al caché toma la parte central de la dirección que se llama índice y la usa como el número de fila. Los datos y la etiqueta se buscan al mismo tiempo. A continuación, la etiqueta debe compararse con la parte superior de la dirección para decidir si la línea pertenece al mismo rango de direcciones en la memoria y es válida. Al mismo tiempo, la parte inferior de la dirección se puede utilizar para seleccionar los datos solicitados de la línea de caché (supongo que una línea de caché puede contener datos para varias palabras).

Enfaticé un poco en el acceso a los datos y el acceso a las etiquetas + comparar ocurre al mismo tiempo, porque esa es la clave para reducir la latencia (propósito de un caché). El acceso de ram de ruta de datos no necesita ser de dos pasos.

La ventaja es que una lectura es básicamente una simple búsqueda de tabla y una comparación.

Pero está mapeado directamente, lo que significa que para cada dirección de lectura hay exactamente un lugar en el caché donde estos datos podrían almacenarse en caché. Entonces, la desventaja es que muchas otras direcciones se mapearían en el mismo lugar y podrían competir por esta línea de caché.

Vamos a usar un ejemplo. Un caché de 64 kilobytes, con caché de 16 bytes tiene 4096 líneas de caché diferentes.

Necesita dividir la dirección en tres partes diferentes.

Los bits más bajos se utilizan para indicarle el byte dentro de una línea de caché cuando la recupera, esta parte no se usa directamente en la búsqueda de caché. (bits 0-3 en este ejemplo)
Los siguientes bits se usan para INDEXAR el caché. Si considera el caché como una gran columna de líneas de caché, los bits del índice le indican en qué fila debe buscar sus datos. (bits 4-15 en este ejemplo)
Todos los demás bits son bits TAG. Estos bits se almacenan en el almacén de etiquetas para los datos que ha almacenado en el caché, y comparamos los bits correspondientes de la solicitud de caché con lo que hemos almacenado para determinar si los datos que estamos almacenando en caché son los datos que se solicitan.

El número de bits que utiliza para el índice es log_base_2 (number_of_cache_lines) [en realidad es el número de conjuntos, pero en un caché mapeado directo, hay el mismo número de líneas y conjuntos]