Arquitectura de Computadores.

2º curso, Grado Ingeniería Informática

Gestión de Memoria

1.- (5.3 Patterson 2011) La siguiente tabla muestra una lista de referencias a dirección de memoria de 32 bits:
a.- 1, 134, 212, 1, 135, 213, 162, 161, 2, 44, 41, 221
b.- 6, 214, 175, 214, 6, 84, 65, 174, 64, 105, 85, 215

1.1. Dada una cache de correspondencia directa con 16 bloques de una sola palabra, indique para cada
una de las referencias, la dirección binaria, la etiqueta y el índice. Indique también si es un fallo o un
acierto, suponiendo que inicialmente la cache está vacía.

Solución:

Etiqueta bloque Palabra

1 0000 0000 0000 0000 0000 0000 0000 0001 --
134 0000 0000 0000 0000 0000 0000 1000 0110 --
212 0000 0000 0000 0000 0000 0000 1101 0100 --
1 0000 0000 0000 0000 0000 0000 0000 0001 -- Hit
135 0000 0000 0000 0000 0000 0000 1000 0111 --
…….

1.2. Dada una cache de correspondencia directa con 8 bloques de 2 palabras, indique para cada una de las
referencias, la dirección binaria, la etiqueta y el índice. Indique también si es un fallo o un acierto,
suponiendo que inicialmente la cache está vacía.
 Etiqueta bloque Palabra

1 0000 0000 0000 0000 0000 0000 0000 000 1

134 0000 0000 0000 0000 0000 0000 1000 011 0 HIT
212 0000 0000 0000 0000 0000 0000 1101 010 0
1 0000 0000 0000 0000 0000 0000 0000 000 1
135 0000 0000 0000 0000 0000 0000 1000 011 1 HIT

1.3. Sea una cache de correspondencia directa y una capacidad de 8 palabras con una memoria principal
direccionada con 32 bits. Optimice su diseño para las referencias anteriores. Considerar tres posibles
diseños de la cache: C1 con bloques de una palabra, C2 con bloques de 2 palabras y C3 con bloques
de 4 palabras. ¿Cuál es el mejor en términos de frecuencia de fallos? Si la parada por fallo es de 25
ciclos y C1 tiene un tiempo de acceso de 2 ciclos, C2 de 3 ciclos y C3 de 5 ciclos ¿Cúal es el mejor
diseño?
___________________________________________________________________
C1: con bloques de una palabra
Etiqueta bloque Palabra

1 0000 0000 0000 0000 0000 0000 0000 0 001 --

134 0000 0000 0000 0000 0000 0000 1000 0 110 --
212 0000 0000 0000 0000 0000 0000 1101 0 100 --
1 0000 0000 0000 0000 0000 0000 0000 0 001 -- Hit
135 0000 0000 0000 0000 0000 0000 1000 0 111 --
…….
 ___________________________________________________________________
C2: con bloques de 2 palabras  cache con 4 bloques

Etiqueta bloque Palabra

1 0000 0000 0000 0000 0000 0000 0000 0 00 1

134 0000 0000 0000 0000 0000 0000 1000 0 11 0
212 0000 0000 0000 0000 0000 0000 1101 0 10 0
1 0000 0000 0000 0000 0000 0000 0000 0 00 1--Hit
135 0000 0000 0000 0000 0000 0000 1000 0 11 1--Hit
…….
___________________________________________________________________
C3: con bloques de 4 palabras  cache con 2 bloques
Etiqueta bloque Palabra

1 0000 0000 0000 0000 0000 0000 0000 0 0 01

134 0000 0000 0000 0000 0000 0000 1000 0 1 10
212 0000 0000 0000 0000 0000 0000 1101 0 1 00
1 0000 0000 0000 0000 0000 0000 0000 0 0 01--Hit
135 0000 0000 0000 0000 0000 0000 1000 0 1 11
…….

a)
Miss hit
penalization
C1 25 ciclos 2 ciclos
C2 25 ciclos 3 ciclos
C4 25 ciclos 5 ciclos

C1: 1 hit tiempo memoria=25*11+2*12=299

C2: 3 hits tiempo memoria=25* 9 +3*12=261
C4: 2 hits tiempo memoria=25*10+4*12=298

1.4. Dados los siguientes parámetros para diferentes caches de correspondencia directa:
Tamaño Cache Tamaño bloque (diseño inicial) Tiempo de acceso a cache
a. 64KB 1 palabra 1 ciclo
b. 64KB 2 palabras 2 ciclos
Calcule el número total de bits de la cache suponiendo direcciones de 32 bits.
Dado este tamaño total, determine el tamaño más próximo al tamaño dado de la cache de
correspondencia directa con bloques de 16 palabras, siendo este tamaño igual o mayor al dado.
Explique por qué la segunda cache puede proporcionar peores prestaciones.

a) Tamaño de cache= bloques*(tamaño bloque + tamaño etiqueta + tamaño validez)

En este caso 64KB= 214 * 4 bytes/palabra=tamaño cache=219 bits=29 Kbits=512 Kbits
 Si se definen 214 bloques de una palabra (diseño inicial) en cache entonces no se dispone de
espacio para guardar la información, las etiquetas y bits de validez

 Si se definen bloques de 16 palabras  nºBloques=1K  10 bits direccionan bloques

Etiquetas de 32-10-4-2=16 bits  tamaño cache (bits)= 210 * (24 * 32+16+1)=529Kbits

2. (5.4 Patterson 2011) En una cache de correspondencia directa con direcciones de 32 bits, los bits de la
dirección se usan como se indica en la tabla:
Etiqueta Indice Desplazamiento
a. 31-10 9-4 3-0
b. 31-12 11-5 4-0
2.1 ¿Qué tamaño, en palabras, tiene la línea de cache?
a. 4 palabras de 32 bits donde se pueden direccionar bytes
b. 8 palabras de 32 bits donde se pueden direccionar bytes
2.2 ¿Cuantas entradas tiene la cache?
a. 64 líneas de cache, o bloques
b. 128 líneas de cache, o bloques

2.3 ¿Cúal es la relación entre el número total de bits de la cache y el número de bits de almacenamiento?

1. Tamaño cache= 26 * (22 * 32+12+1)=8.8Kbits

Datos 4*32=128 bits

Etiquetas+control=13 bits

Ratio datos/cache=128/141=0.907
90.7% de la cache almacena datos el otro 9.3% almacena etiquetas y control

2.4 Dada la siguiente secuencia de accesos expresadas como direcciones de byte

0, 4, 16, 132, 232, 160,1024, 30, 140, 3100, 180, 2180
Determinar los aciertos y fallos en los accesos a la cache.
Etiqueta Indice Desplazamiento
31-10 9-4 3-0
0 0000 0000 0000 0000 0000 00 00 0000 0000
4 0000 0000 0000 0000 0000 00 00 0000 0100 Hit
16 0000 0000 0000 0000 0000 00 00 0001 0000
132 0000 0000 0000 0000 0000 00 00 1000 0100
232 0000 0000 0000 0000 0000 00 00 1110 1000
160 0000 0000 0000 0000 0000 00 00 1010 0000
1024 0000 0000 0000 0000 0000 01 00 0000 0000 <= Reemplaza bloque
30 0000 0000 0000 0000 0000 00 00 0001 1110 Hit
140 0000 0000 0000 0000 0000 00 00 1000 1100 Hit
3100 0000 0000 0000 0000 0000 11 00 0001 1100 <= Reemplaza bloque
180 0000 0000 0000 0000 0000 00 00 1011 0100
2080 0000 0000 0000 0000 0000 10 00 0010 0000

2.5 Razón de aciertos = 0,25

3. Sea una memoria caché asociativa por conjuntos con 64 particiones (o bloques) en total; 4 particiones por
conjunto. Si la memoria principal contiene 4K bloques de 128 palabras cada uno, indicar cuántos bits, de una
dirección de memoria principal, se utilizarían para el campo etiqueta. (Esta arquitectura no es MIPS)
Solución:

Direccion de MP tamaño MP = 22 * 210 * 27 palabras  19 bits direccionan MP

Cache: conjuntos=64/4= 16 conjuntos direccionados con 4 bits

Palabras dentro del bloque=128  7 bits direccionan palabra en el bloque
Etiqueta conjunto palabra
00010001 1010 0001111
Entonces: Etiqueta=19-4-7=8 bits

4. Sea una memoria caché que almacena 2048 palabras organizadas en 2 conjuntos de bloques de 4 palabras. Si
la memoria principal tiene un tamaño de 128K x 32 bits. Indicar cómo se guarda la información de la caché, y
cuál es el tamaño total de la caché.

Solución:
En MC 2048 palabras/ 4 pal/bloque=29 bloques = 211 palabras en MC

17 bits direccionan MP, 14 campo etiqueta, 1 bits campo conjunto y 2 bits campo de palabras

Etiqueta Conjunto Palabra

14 bits 1 bit 2 bits
00010001101111 0 11

Tamaño MC=29 bloques *(22 * 32 bits+14 bits+1bit) =9152 bytes

MPrincipal 128K x 32 bits= 27 * 210 palabras = 215 bloques mapeados en dos conjuntos

M Cache M Principal
Conjunto 0 Bloque 0 Bloque 2 … Bloque 215 -2
De 256 bloques
Conjunto 1 Bloque 1 Bloque 3 … Bloque 215 -1
De 256 bloques

5. Sea una memoria principal de 64Kx16 bits, y una memoria caché con correspondencia directa de 1K palabra.
Si el tamaño de bloque es de 4 palabras, indicar el formato de las direcciones de memoria principal, y el
número de bits (y su función) que hay en cada entrada de la caché.

Solución:
MP => 64K = 216 palabras de 16 bits; direcciones de 16 bits; bloques en MP = 216 /4=214 bloques
MCache => Bloques en cache 210 /4=28

Etiqueta bloque Palabra

0000 00 00 0000 00 00

6. A continuación se da una cadena de referencias de direcciones de 19 bits dadas como direcciones de palabra:
1, 4, 8, 5, 20, 17, 19, 56, 9, 11, 4, 43, 5, 6, 9, 17.
Suponiendo una caché de correspondencia directa con 16 bloques de una palabra que está inicialmente vacía,
rotular cada referencia en la lista como un acierto o fallo y mostrar el contenido final de la caché. (Solución
similar al ejercicio 2.4)
 Ref Etiqueta bloque Palabra Hit/Miss
1 0000 0000 0000 000 0 001
4 0000 0000 0000 000 0 100
8 0000 0000 0000 000 1 000
5 0000 0000 0000 000 0 101
20 0000 0000 0000 001 0 100
17 0000 0000 0000 001 0 001
19 0000 0000 0000 001 0 011
56 0000 0000 0000 011 1 000
9 0000 0000 0000 000 1 001
11 0000 0000 0000 000 1 011
4 0000 0000 0000 000 0 100
43 0000 0000 0000 010 1 011
5 0000 0000 0000 000 0 101 Hit
6 0000 0000 0000 000 0 110
9 0000 0000 0000 000 1 001 Hit
17 0000 0000 0000 001 0 001 Hit

Tasa de aciertos =3/16

7. Utilizando la cadena de referencia del ejercicio 6, mostrar los aciertos y fallos y contenido final de la caché de
correspondencia directa con bloques de cuatro palabras y un tamaño total de 16 palabras.

M Cache
Ref Etiqueta Bl. Pal.
1 0000 0000 0000 000 0 0 01
4 0000 0000 0000 000 0 1 00 bloque Etiqueta Palabra
8 0000 0000 0000 000 1 0 00 seleccionada
5 0000 0000 0000 000 0 1 01Hit 00 0000 0000 0000 000 00 01 10 11
20 0000 0000 0000 001 0 1 00 0000 0000 0000 001 00 01 10 11
17 0000 0000 0000 001 0 0 01 01 0000 0000 0000 000 00 01 10 11
19 0000 0000 0000 001 0 0 11Hit 0000 0000 0000 001 00 01 10 11
56 0000 0000 0000 011 1 0 00 0000 0000 0000 000 00 01 10 11
9 0000 0000 0000 000 1 0 01 10 0000 0000 0000 000 00 01 10 11
11 0000 0000 0000 000 1 0 11Hit 0000 0000 0000 011 00 01 10 11
4 0000 0000 0000 000 0 1 00 0000 0000 0000 000 00 01 10 11
43 0000 0000 0000 010 1 0 11 0000 0000 0000 010 00 01 10 11
5 0000 0000 0000 000 0 1 01Hit 0000 0000 0000 000 00 01 10 11
6 0000 0000 0000 000 0 1 10Hit 11
9 0000 0000 0000 000 1 0 01
17 0000 0000 0000 001 0 0 01Hit

Tasa aciertos=6/16

8. Utilizando la cadena de referencia del ejercicio 6, mostrar los aciertos y fallos y contenido final de la caché
para una caché asociativa por conjuntos de dos bloques de una palabra y un tamaño total de 16 palabras.
Suponer política de reemplazo LRU.

Conjuntos de dos bloques,

Nº total de conjuntos =16 bloques de una palabra/2 bloques.conj=8 conjuntos tres bits para indexar el conjunto
 Ref Etiqueta Conjunto M Cache
1 0000 0000 0000 0000 001
4 0000 0000 0000 0000 100 Conj. Etiqueta bloque1 Etiqueta bloque2
8 0000 0000 0000 0001 000 000 0000 0000 0000 0001 0000 0000 0000 0111
5 0000 0000 0000 0000 101 001 0000 0000 0000 0000 0000 0000 0000 0010
20 0000 0000 0000 0010 100 0000 0000 0000 0001
17 0000 0000 0000 0010 001 010
19 0000 0000 0000 0010 011 011 0000 0000 0000 0010 0000 0000 0000 0001
56 0000 0000 0000 0111 000 0000 0000 0000 0101
9 0000 0000 0000 0001 001 100 0000 0000 0000 0000 0000 0000 0000 0010
11 0000 0000 0000 0001 011 101 0000 0000 0000 0000
4 0000 0000 0000 0000 100 hit 110 0000 0000 0000 0000
43 0000 0000 0000 0101 011 111
5 0000 0000 0000 0000 101hit
6 0000 0000 0000 0000 110
9 0000 0000 0000 0001 001hit
17 0000 0000 0000 0010 001

9. Utilizando la cadena de referencia del ejercicio 6, mostrar los aciertos y fallos y contenido final de la caché
para una caché totalmente asociativa con bloques de una palabra y un tamaño total de 16 palabras. Suponer
reemplazo LRU.

10. Utilizando la cadena de referencia del ejercicio 6, mostrar los aciertos y fallos y contenido final de la caché
para una caché totalmente asociativa con bloques de cuatro palabras y un tamaño total de 16 palabras.
Suponer reemplazo LRU.

11. Un computador monoprocesador con una memoria principal de 1Mpalabra, dispone de una memoria caché de
correspondencia directa de 4Kpalabras con bloques de 16 palabras. Suponiendo que la memoria caché se
encuentra inicialmente vacía, indique el número de fallos de caché que se producen si el procesador genera la
secuencia de accesos a memoria:
ABC13h, CDC14h, ABC1Fh, AB305h, ABC14h, CDC1Fh, AB306h, CAC13h, CDC1Ah, CA00h, CAC1Fh.
Para esa misma secuencia indique los marcos de bloque de caché en los que se carga cada posición de
memoria principal a la que se pretende acceder.

12. Considerar un sistema de memoria virtual con una dirección virtual de 40 bits, páginas de 16KB y dirección
física de 36 bits. ¿Cuál es el tamaño total de la tabla de páginas para cada proceso de esta máquina,
suponiendo que los bits de validez, protección, ocupación y uso necesitan un total de 4 bits y que se utilizan
todas las páginas virtuales? Suponer que las direcciones de disco no se almacenan en la tabla de páginas.
13. La caché C1 es de correspondencia directa con 16 bloques de una palabra. La caché C2 es de correspondencia
directa con 4 bloques de cuatro palabras. Suponer que la penalización de fallos para C1 es de 8 ciclos de reloj
y para C2 es de 11 ciclos de reloj. Suponiendo que las cachés están inicialmente vacías, encontrar una cadena
de referencia para que C2 tenga una tasa de fallos más baja pero emplee más ciclos en los fallos de caché que
C1. Utilizar direcciones de palabra.

14. Considerar tres máquinas con diferentes configuraciones de caché y diferentes medidas de tasa de fallos:
a. Caché 1: Correspondencia directa con bloques de una palabra. La tasa de fallos de instrucción es del 4
por 100 y la tasa de fallos de datos del 8 por 100. El periodo del reloj es de 10 ns.
b. Caché 2: Correspondencia directa con bloques de cuatro palabras. La tasa de fallos de instrucciones es
del 2 por 100 y la tasa de fallos de datos del 4 por 100. La frecuencia de reloj es de 10 ns.
c. Caché 3: Asociativa por conjuntos de dos vías con bloques de cuatro palabras. La tasa de fallos de
instrucciones es del 2 por 100 y la tasa de fallos de datos del 4 por 100. La frecuencia de reloj es de 12 ns.

Para estas máquinas, la mitad de las instrucciones contienen una referencia de datos. Suponer que la penalización
de fallos de la caché es 6+Tamaño de bloque. El CPI para esta carga de trabajo se midió sobre una máquina con
caché 1 y se encontró que era 2.0. Determinar que máquina emplea más ciclos en los fallos de caché. Determinar
que máquina es más rápida y cual más lenta.

Solución:

Cache 1 Cache 2 Cache 3

Correspondencia directa Correspondencia directa Asociativa por conjuntos
Bloque=1 palabra Bloque=4 palabra Conjuntos de dos bloques
Tasa fallos I=4% Tasa fallos I=2% Bloque=4 palabra
Tasa fallos D=8% Tasa fallos D=4% Tasa fallos I=2%
Periodo=10 ns Periodo=10 ns Tasa fallos D=4%
CPI=2 Periodo=12 ns
Se supone: 50% de las instrucciones referencias a datos. Penalizacion fallo =6+tamañobloque.

 Cache 1
Penalizacion fallo=6+1 ciclos=7 ciclos
Por cada N instrucciones con sus N/2 referencias a datos se tiene las siguientes penalizaciones
Ciclos penalización mem= N * (0.04*7+ 0.08*7*0.5)=0.56 *N El 56% del tiempo de ejecución se invierte en
accesos a memoria

Un programa con N instrucciones invierte 0.56 N ciclos en gestionar la memoria. Entonces

CPI=2 ciclos por instrucción= ciclos cpu+0.56 ciclos mem

ciclos cpu = 1.44=CPI cpu (esto será común para las otras maquinas)

Tiempo ejecución1= 2 * N*10ns= 20 N ns

 Cache2
Ciclos penalización= 7+4=11
Ciclos penalización= N*(0.02+0.04*0.5)*11=0.44N

CPI=1.44+0.44=1.88
Tiempo ejecución2= 1.88 * N*10ns= 18.8 N ns  la mas rápida

 Cache3
Ciclos penalización= 7+4=11
Ciclos penalización= N*(0.02+0.04*0.5)*11=0.44N

CPI=1.44+0.44=1.88
Tiempo ejecución2= 1.88 * N*12ns= 22.56 N ns