Story Transcript
Respuestas al Problemario Memoria Cache 1.
Para la traza de direcciones dada a continuación, calcule la tasa de aciertos suponiendo una memoria caché (mapeo directo) de cuatro líneas de ocho bytes de longitud cada una. El CPU direcciona por byte y por palabra de 4 bytes, siendo el tamaño del bus de direcciones de 32 bits.
Formato dirección Virtual: 2 bits para byte, 1 bit para palabra, 2 para línea 27 para etiqueta. RB RB RB RB RB RB RB RB RB RW RW RB RB RB RB RB RB
A16 A17 A18 A19 A1A A1B A1C A1D A1E B0B B10 A1F A47 A48 A49 A50 A3F
Línea 2 2 3 3 3 3 3 3 3 1 0 3 0 1 1 2 3
Etiqueta 50 50 50 50 50 50 50 50 50 162 162 50 52 52 52 52 51
A/F F A F A A A A A A F F A F F A F F
A/F x 9
A A A A A A F F A F F A F
ESTE TROZO SE REPITE 10 VECES
RB: Read Byte RW: Read Word
81 aciertos/134 Accesos totales = 60,4% aciertos 2.
Considere un procesador de 64 bits que cuenta con una memoria caché interna de 64K Bytes de capacidad, mapeo directo con 256 líneas. La memoria principal es de 4G Bytes. a) Indique el número de bytes por línea. 1 punto 256 b) Muestre el formato de dirección virtual de este sistema de memoria. Etiqueta: 16; Línea: 8; (Palabra: 5; Bytes: 3 = 8) c) Para la traza de direcciones dada a continuación calcule la tasa de aciertos. 7A*7=49A;+5A=54A/112 (48.2%) Considere ahora una cache asociativa de dos vías con 128 conjuntos y 16 bytes por línea: d) Muestre el formato de dirección virtual de este sistema de memoria. Etiqueta: 21; Línea: 7; (Palabra: 1; Bytes: 3 = 4) e) Calcule la tasa de aciertos y compare. Use el algoritmo de reemplazo LRU. 13A*7=91A;+4A=96A/112 (85.7%) Dirección RB 0x1201AB1 F F RB 0xD2019FC F F RB 0xD201A34 F F RB 0x12C19F1 F F RB 0x1201398 F F RB 0x12C1998 A F RB 0x12C1391 F A F 2da vez en adelante Todos aciertos (13) RB 0x12C199A A A A RB 0xD2C1A34 F F F RB 0x12C19F1 F A F RB 0xD2CB833 F A F RB 0x52CBB32 F F F Se repite 8 veces RB 0xD2CB856 A A F RB 0xD2CBB56 F F F RB 0xD2CBB55 A A A RB 0x12C1A51 F F F RB 0XD3CBB59 F F F RB 0xD2CBB55 F F A RB 0x51CA835 F A F RB 0x120139A F F RB 0x12C1990 A A 3.
Suponga una memoria caché de correspondencia directa (o correspondencia directa), de 128K bytes de datos con líneas de 256 bytes de longitud cada una. El CPU direcciona por byte y por palabra de 4 bytes, siendo el tamaño del bus de direcciones de 32 bits. a)
Calcule el número de líneas de caché.
b) c) d)
Muestre el formato de dirección virtual. Muestre la secuencia de aciertos y fallos y calcule la tasa de aciertos para la traza mostrada a continuación. Considerando que ahora cuenta con una cache asociativa de dos vías, de igual número de conjuntos que de líneas del caso anterior y con el mismo número de bytes por línea que en el caso anterior. Repita la parte c). El algoritmo de sustitución es FIFO.
128 kbytes 217 = 8 = 2 9 = 512 lineas a) # de lineas = 256 lineas /byte 2 b)
Etiqueta: 15 bits
c) RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB
013728 0058A0 01372C 125824 01372C 125830 3 VECES 125838 013768 0BA600 2858FC 4 VECES 0BA608 0BA700 3537B0 3537B4 0BA708 393784 28580C 285900 285904
Linea: 9 bits Ciclo 1
Ciclo 2
F F A F A A A A F F A F F A A F A F A
F F A A A A F A A F A A F
A A A A
A A A A
# total de accesos = 81; # de aciertos = 62;
h=
d) RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB RB
013728 0058A0 01372C 125824 01372C 125830 3 VECES 125838 013768 0BA600 2858FC 4 VECES 0BA608 0BA700 3537B0 3537B4 0BA708 393784 28580C 285900 285904
W: 6 bits
A A A A
Ciclo 1 F F A F A A A A F A F A A A F A F A A F A F A
A A A A
Ciclo 3
A A A A
A A A A
A A A A
# total de accesos = 81; # de aciertos = 66;
F F A A A A F A A F A A F
A A A A
A A A A
A A A A
A A A A
A A A A
62 = 76,54% 81 Ciclo 2
A A A A
B: 2 bits
A F A A A A A A A F A A F
A A A A
Ciclo 3
A A A A
A A A A
A F A A A A A A A F A A F
A A A A
4. Indique el formato de dirección virtual si se tiene una caché de 32K Bytes y una memoria principal de 16 M Bytes en los siguientes casos: El tamaño de las palabas es 64 bits. a)
Caché correspondencia directa con líneas de 16 bytes. 9
11
ETIQUETA b)
11
10
3
CONJUNTO
BYTE
Caché completamente asociativa con líneas de 32 bytes. (1 PUNTO) 19
2
ETIQUETA
5.
3 BYTE
Caché asociativa por conjuntos con conjuntos de 4 líneas y líneas de 8 bytes. (1 PUNTO)
ETIQUETA c)
1 PALABRA
LINEA
3
PALABRA
BYTE
Considere un procesador que direcciona por byte y palabra de 32 bits un espacio de memoria de 16 Mbytes. Para la traza de accesos que se muestra a continuación, responda: a) Calcule la tasa de aciertos para una memoria caché de correspondencia directa que utiliza el siguiente formato de dirección virtual: Etiqueta 8 bits
Linea 12 bits
Palabra 2bits
Byte 2 bits
b) Calcule la tasa de aciertos para una memoria caché, asociativa por conjuntos de 2 vias que utiliza el siguiente formato de dirección virtual: Etiqueta 12 bits
Conjunto 8 bits
Palabra 2bits
Byte 2 bits
Caso a
Caso b
1era
X20
1era
X20
RB
0x020074
F
A
F
A
RB
0x146A22
F
A
F
A
RB
0x46007A
F
F
F
A
RB
0x146A28
A
A
A
A
RB
0x460076
A
A
A
A
RB
0x041450
F
A
F
A
RB
0X020072
F
F
A
A
Se repite 20 veces
6.- Una cierta computadora tiene un sistema de memoria caché de correspondencia directa, y las direcciones que genera el CPU se interpretan según el formato: Etiqueta 8 bits
Línea 8 bits
Palabra 5 bits
Byte 3 bits
a) Calcule la capacidad de la memoria caché en bytes, y diga cuál es su organización. La memoria se organiza en palabras de 23 = 8 bytes, y cada linea contiene 25 = 32 palabras, por lo cual el número de bytes por línea es 256. Dado que hay 8 bits dedicados a la identificación de línea, la caché contiene 28 = 256 líneas, y su capacidad será entonces de 256 x 256 = 64 kbytes. b) Muestre la secuencia de aciertos y fallos y calcule la tasa de aciertos para la traza mostrada a continuación.
Dirección 003A50 003A58 013A60 013A80 3A2238 025B00 025B10 025B18 3A2230 003A58 003A70 013A58 3B23A8 3A2238 AA5BB0 AA5BB8 AA5BC0 3A5BF0 285800 285918 285970
Línea 3A 3A 3A 3A 22 5B 5B 5B 22 3A 3A 3A 23 22 5B 5B 5B 5B 58 59 59
Etiqueta 00 00 01 01 3A 02 02 02 3A 00 00 01 3B 3A AA AA AA 3A 28 28 28
Lazo externo 1ª paso Lazo interno 1ª paso Pasos 2 a 11 F A F A F F A
F A A A F A F F
A A F A F A
A F A A F F F A
Número total de accesos a memoria = 7 + 4 x (8 + 11 x 6) = 303 Número de aciertos = 3 + 4 + 3 x 5 + 3 + 10 x 4 + 3 x (11 x 4) = 197
h=
Aciertos Accesos
=
197 303
= 0,6502
Pasos 2 a 4 Lazo interno Pasos 1 a 11
A A F A F A A F A A F A
7.- El diseñador de la computadora del problema 6 decide cambiar el sistema de memoria caché por una memoria asociativa por conjuntos de 2 vías, y el formato de dirección es ahora: Etiqueta 12 bits
Conjunto 4 bits
Palabra 5 bits
Byte 3 bits
a) Calcule la capacidad de la memoria caché en bytes, y diga cuál es su organización. El número de bytes por línea es 256, igual que en el caso anterior, pero ahora tenemos dos vías o líneas por conjunto, así que hay 512 bytes por conjunto. Dado que se usan 4 bits para la identificación de conjunto, la caché contiene 24 = 16 conjuntos, y su capacidad será entonces de 512 x 16 = 8 kbytes. b) Muestre la secuencia de aciertos y fallos y calcule la tasa de aciertos para la traza del problema (1.b), suponiendo el uso del algoritmo de sustitución LRU.
Dirección 003A50 003A58 013A60 013A80 3A2238 025B00 025B10 025B18 3A2230 003A58 003A70 013A58 3B23A8 3A2238 AA5BB0 AA5BB8 AA5BC0 3A5BF0 285800 285918 285970
Conj. A A A A 2 B B B 2 A A A 3 2 B B B B 8 9 9
Etiqueta 003 003 013 013 3A2 025 025 025 3A2 003 003 013 3B2 3A2 AA5 AA5 AA5 3A5 285 285 285
Lazo externo 1ª paso Lazo interno 1ª paso Pasos 2 a 11
Pasos 2 a 4 Lazo interno Pasos 1 a 11
F A F A F F A
F A A A A A A F
A A A A A A
A F A A F F
A A A A A A A F A A F A
F A
El número total de accesos a memoria sigue siendo 303. Número de aciertos = 3 + 4 + 3 x 5 + 5 + 6 x 10 + 3 x (11 x 6) = 285
h=
Aciertos Accesos
=
285 303
= 0,9406
Pese a ser una memoria caché más pequeña, el uso del esquema asociativo por conjuntos aumenta la tasa de aciertos de 65% a 94%. Si embargo, la mejora procede casi exclusivamente del lazo interno, pues en el lazo externo el algoritmo LRU en este caso hace la peor decisión posible cada vez. Usar más de dos vías o un algoritmo de reemplazo con algo de aleatoriedad mejoraría aún más el valor de h.