CACHÉS
Considerando los datos de la tabla adjunta correspondientes a cachés de correspondencia directa con un tamaño de bloque de 32 bytes, tomados sobre un conjunto de programas de prueba en los que el porcentaje de referencias a instrucciones es del 75%, responde:
A) ¿Qué sistema presenta una menor razón de fallos, el constituido por una caché de instrucciones de 16KB y una caché de datos de 16KB, o el constituido por una caché de 32KB unificada?
SOLUCIÓN: Dado que el 75% de accesos son referentes a instrucciones, el otro 25% serán accesos a datos, con lo que la razón de fallos conjunta para la caché separada de 16KB será:
75% x 0,64% (esto sacado de la tabla) + 25% x 6,47% (sacado de la tabla) = 2,10% tomando los datos de tasas de fallos para caché de instrucciones y datos de 16KB cada una separadas.
La tabla indica que la tasa de fallos para la unificada de 32KB es el 1,99%, ligeramente inferior.
B) Supóngase que un acierto caché requiere un ciclo de reloj, un fallo tiene un costo de 50 ciclos, y que un acierto en una instrucción load o store requiere un ciclo extra en el caso de la caché unificada. ¿Cuál es el tiempo medio de acceso a memoria en cada caso?
SOLUCIÓN: El tiempo medio de acceso a memoria puede dividirse en términos, el correspondiente a instrucciones y a datos:
TiempoMedioAccesoMemoria = PorcentajeAccesosInstrucc. x (Tiempo de acierto + TasaFallos x PenalizaciónFallos) + PorcentajeAccesosDatos x (TiempoAcierto + TasaFallos x PenalizaciónFallos)
- El tiempo de acceso medio a memoria para la caché dividida es: 75% x (1 + 0.64% x 50) + 25% x (1 + 6,47% x 50) = 2,05
- El tiempo de acceso medio a memoria para la caché unificada es: 75% x (1 + 1,99% x 50) + 25% x (1 + 1 + 1,99% x 50) = 2,24
Así pues, aunque la tasa de fallos del sistema con caché separadas sea superior al de la unificada, su tiempo de acceso medio a memoria es menor.
| Tamaño | Cache de instrucciones | Cache de datos | Cache unificada |
|---|---|---|---|
| 8KB | 1.10% | 10.19% | 4.57% |
| 16KB | 0.64% | 6.47% | 2.87% |
| 32KB | 0.39% | 4.82% | 1.99% |
MEMORIA VIRTUAL
Sea un sistema de memoria virtual paginado en 2 niveles con tamaño de página 512 bytes. El sistema dispone de espacio virtual de 1MB y de espacio físico de 512KB, ambos organizados en bytes y reservados para un único proceso. El sistema dispone de una caché asociativa por conjuntos, que consta de 4 conjuntos de 2 vías cada uno. Cada línea de la caché consta de 4 bytes. Se adjunta el contenido de la tabla del primer nivel y de la caché en un momento determinado en hexadecimal. Cada entrada de la tabla de traducción tiene 16 bits, de forma que los más significativos son de control y los menos significativos contienen un número de página física. El bit más significativo de cada entrada es el de residencia, que vale 1 si la página está residente. El resto de bits de control no influyen. Las entradas de las tablas de páginas de 2º nivel tienen el mismo formato. Con estos datos y sabiendo que las tablas del 2º nivel se tratan exactamente igual que el resto de páginas virtuales, indicar de forma detallada todos los pasos implicados en el proceso de traducción, así como los distintos valores que se van obteniendo en el proceso si el procesador emite la dirección virtual B8ED1 para leer un byte. ¿Qué dato es enviado finalmente al procesador?
Planteamiento:
- |V| = 1MB = 220 bytes –> 20 bits de dirección virtual
- |M| = 512KB = 219 bytes –> 19 bits de dirección física
- Tamaño de página = 512 bytes = 29 bytes –> 9 bits de desplazamiento
Descomposición de la Dirección Virtual:
Al ser la página de 512 bytes, el desplazamiento en la página requiere 9 bits. Como la tabla de páginas del primer nivel tiene 8 entradas, se requieren log28 = 3 bits para indexarla. Puesto que las direcciones virtuales son de 20 bits, los restantes 20 – 9 – 3 = 8 bits indexarán la tabla de páginas de 2º nivel.
Descomposición de la Dirección Física:
Al ser la página de 512 bytes, el desplazamiento en la página es también de 9 bits. Puesto que las direcciones físicas son de 19 bits, los restantes 19 – 9 = 10 bits serán el número de página física.
Descomposición de la Dirección Física desde el punto de vista de la caché:
Líneas de la caché de 4 bytes = 22 –> 2 bits de desplazamiento. La caché tiene 4 conjuntos = 22 –> 2 bits de campo de índice. 19 – 2 – 2 = 15 bits de etiqueta.
Resolución:
Descomponemos la dirección virtual B8ED1 generada por el procesador (1011 1000 1110 1101 0001), que descompuesto queda:
TP1 = 101 – TP2 = 11000111 – DESP = 011010001. Así pues, se lee la entrada 5 (101) de la TP1, que contiene AF71 (1010 1111 0111 0001).
El 1 en el bit más significativo indica que la tabla de páginas de 2º nivel está residente en la memoria física. Como el tamaño de la página física es de 10 bits, cogemos los 10 bits menos significativos, que son el número de la página física que contiene la tabla de páginas del 2º nivel asociada: 1101110001 (nºPF). En dicha tabla se necesita leer la entrada 11000111, que indica el campo TP2 de la dirección virtual B8ED1. Dado que cada entrada de la tabla de páginas, tanto en el 1º como en el 2º nivel, consta de 16 bits (2 bytes), la dirección física donde se inicia la entrada de la TP2 a leer se obtiene concatenando al mencionado número de página física el número de entrada multiplicado por dos, obteniendo así la dirección física final de la TP2 a la que hay que acudir = 1101110001 110001110. Esta dirección es una posición de memoria física que será buscada en la caché antes que en memoria principal cuando se la intenta acceder. Descomponemos la dirección física desde el punto de vista de la caché –>
ETIQUETA = 110111000111000 – ÍNDICE = 11 – DESP = 10. Buscamos la etiqueta, que en hexadecimal es 6E38, en el conjunto 3, como indica el índice. Acertamos, está y contiene ¡IF3EB0D9! Nos quedamos con los 2 bytes (cada par de letras es 1 byte) empezando en el par 2 (empieza en 0), como indica el campo desplazamiento –> B0D9. Estos 16 bits (1011 0000 1101 1001) son la entrada de la TP2 que estamos buscando. Está residente en memoria porque el más significativo es un 1. Los 10 bits menos significativos contienen precisamente la página física = 0011011001. Como es paginado, concatenamos este número de página física con el desplazamiento dentro de la página del principio del todo = 0011011001 011010001 (1B2D1), obteniendo la dirección física final. Queremos saber el dato, como es una dirección física, primero miramos en caché, por lo que descomponemos: ETIQUETA = 1B2D – I = 00 – DESP = 01. Hay que buscar la etiqueta 1B2D en el conjunto 0. Está, por lo que cogemos el desplazamiento 1 (2º par) = 6A, que es lo que devuelve el procesador.
MEMORIAS
Espacio virtual de 64 bytes, memoria principal de 32 bytes y tamaño de página 8 bytes. Paginado en 1 nivel con el auxilio de una TLB de tres entradas. Algoritmo de reemplazo de páginas físicas y de entradas de TLB es FIFO. También caché de 6 bytes de 2 conjuntos con 2 líneas/conjunto. En cada conjunto se usa el algoritmo de reemplazo LRU. Si el procesador emite la siguiente lista de direcciones virtuales (1D, 21, 1C, 0C), indicar cómo evoluciona todo en cada acceso partiendo de:
Planteamiento:
- |V| = 64 bytes –> 26 –> 6 bits de dirección virtual
- |M| = 32 bytes = 25 –> 5 bits de dirección física
- Tamaño de página = 8 bytes –> 3 bits de desplazamiento
- Caché de 8 bytes en dos conjuntos de 2 líneas cada uno –> cada línea puede almacenar 8 / 2 x 2 = 2 bytes
Descomposición de la Dirección Virtual:
Página de 8 bits –> desplazamiento = 3 bits. Puesto que las direcciones virtuales son de 6 bits y solo hay 1 nivel de paginación, los restantes 6 – 3 = 3 bits indexarán la tabla de páginas.
Descomposición de la Dirección Física:
Al ser la página de 8 bytes –> desplazamiento de 3 bits, como en la dirección virtual. Las direcciones físicas son de 5 bits, así que 5 – 3 = 2 bits son el número de página física.
Descomposición desde el punto de vista de la caché:
Líneas de la caché de 2 bytes –> 1 bit de desplazamiento. La caché tiene dos conjuntos –> 1 bit de índice. 5 – 1 – 1 = 3 bits de etiqueta.
Resolución:
a) Acceso 1D:
En binario, usando 6 bits (tamaño de la dirección virtual) = 011101, con 011 etiqueta (página virtual), 101 desplazamiento. La traducción la iniciamos mirando la TLB, donde vemos que la página virtual 011 está mapeada a la página física 01. Así pues, es la dirección física 01 101 la que buscamos. Miramos si esa dirección física está en caché, descomponiéndola: desde el punto de vista de la caché, 011 etiqueta, 0 índice, 1 desplazamiento. Buscamos 011 en el conjunto 0. No se encuentra en el conjunto –> fallo de caché. Ya que el bit LRU señala la línea 1, esta será expulsada de la caché para poder introducir en el conjunto 0 la línea con etiqueta 011, siendo la línea 0 ahora la menos recientemente accedida del conjunto 0, con lo que el bit LRU la apunta a ella ahora.
b) Acceso 21:
Lo mismo que arriba, pero no está ahora 100 en la TLB (el 100 viene de 100001 en este caso), fallo de TLB. Miramos pues la tabla de páginas y nos encontramos también con un fallo de página (no hay nada en la posición 100 o 4). La memoria física consta de 32 bytes y cada página ocupa 8 bytes, así pues hay 4 páginas físicas. Dado que hay 3 ocupadas de los accesos anteriores, hay una disponible, la página física 11. Así pues, en la entrada 100 (4) escribimos que la página virtual correspondiente se ubica en la página física 11 y reflejamos eso mismo en la TLB, echando usando FIFO. Una vez que hemos ubicado la página física 11, podemos calcular la dirección física asociada al acceso como en el apartado anterior, dando también un fallo de caché y teniendo que reemplazar.
c) Acceso 1C:
Como en el apartado a), tenemos un acierto de TLB, pero esta vez tenemos un acierto de caché, con lo que todo se mantiene igual, menos en el conjunto donde acertamos, que ahora el bit LRU cambia porque apuntaba al dato que acabamos de acceder y ahora apunta al otro como el menos recientemente accedido.
cientemente accedido.