EC ES Ejercicios T5 - sdfsdf PDF

Preview

Summary

sdfsdf...

Description

ESTRUCTURA DE COMPUTADORES TEMAS 5: Memoria cach´ e 1. Una memoria cach´e asociativa por conjuntos consta de 16 conjuntos con 4 v´ıas por conjunto. La memoria principal tiene una capacidad de 4MB dividida en l´ıneas de 512 bytes. A la direcci´on de memoria principal, expresada en binario, 1010000110010011000000 ¿Qu´e conjunto le corresponde (expresado en decimal)?. Soluci´ on : DATOS Memoria cach´e (Mc) asociativa por conjuntos. 16 (24 ) conjuntos 4 (22 ) v´ıas/ conjunto Memoria principal CM p = 4 M (222) bytes 512 (29 ) bytes/l´ınea Puesto que la Mp tiene 222 bytes se requieren direcciones de longitud n = log2 CM p = log2 222 = 22 bits. En segundo lugar se va a calcular el n´ umero de l´ıneas L de la Mc: L=16 conjuntos × 4 l´ıneas/conjunto = 26 l´ıneas en Mc El formato de una direcci´on de la Mc que utiliza una funci´on de correspondencia asociativa por conjuntos es: 9 bits etiqueta

n = 22 bits 4 bits ´ındice

9 bits desplazamiento

Luego la direcci´on que se nos plantea es: etiqueta 101000011

´ındice 0010

desplazamiento 011000000

El conjunto de Mc al que hace referencia esta direcci´on es 0010 = (2)10 2. Un computador tiene una unidad de memoria de 8MB y una memoria cach´e de 4KB con un tama˜ no de l´ınea de 256 bytes. Suponer que se hace una referencia a la direcci´on de memoria principal, expresada en binario, 000 0000 0110 0100 1100 0000. a) Si la memoria cach´e utiliza correspondencia directa, ¿En qu´e l´ınea de la memoria cach´e ser´ıa posible encontrar esa direcci´on de memoria principal? ¿Qu´e etiqueta habr´ıa que buscar en esa l´ınea para saber si esa direcci´on se encuentra en la memoria cach´e? b) Si la memoria cach´e utiliza correspondencia totalmente asociativa, ¿qu´e etiqueta habr´ıa que buscar para saber si esa direcci´on se encuentra en la memoria cach´e?

Soluci´ on : DATOS Memoria principal CM p = 8 M (223) bytes Memoria cach´e CM c = 4 K (212 ) bytes 256 (28 ) bytes/l´ınea De los datos del enunciado se deduce que el n´ umero de l´ıneas L de Mc es: L= 212 bytes / (28 bytes/l´ınea) = 24 bloques en Mc a) La memoria cach´e utiliza funci´on de correspondencia directa. Por lo tanto el formato de una direcci´on desde el punto de vista de la memoria cach´e es : n = 23 bits 4 bits ´ındice

11 bits etiqueta

8 bits desplazamiento

Luego dada la direcci´on en binario del enunciado, etiqueta 00000000110

´ındice 0100

desplazamiento 11000000

La l´ınea de la Mc a la que hace referencia es la n´ umero (4)10 (0100). La etiqueta que habr´ıa que buscar es (6)10 (000 000 001 10). b) La memoria cach´e utiliza funci´on de correspondencia totalmente asociativa. Por lo tanto el formato de una direcci´on desde el punto de vista de la memoria cach´e es : n = 23 bits 15 bits etiqueta

8 bits desplazamiento

Luego dada la direcci´on en binario del enunciado, etiqueta 000000001100100

desplazamiento 11000000

La etiqueta que habr´ıa que buscar es (100)10 (000 000 001 100 100). 3. Un computador tiene una unidad de memoria de 2KB y una memoria cach´e de 128 bytes con un tama˜ no de l´ınea de 32 bytes. Suponiendo que inicialmente la memoria cach´e est´a vac´ıa, calcular cu´antos fallos se producir´ıan en la cach´e si se leyeran sucesivamente las direcciones de memoria principal 00000000000, 00000000100, 00000001100, 00010000100, 00010010100, 00001000000, 00001001000 y 00000000000, en cada una de las situaciones siguientes: a) La memoria cach´e emplea correspondencia directa. b) La memoria cach´e emplea correspondencia totalmente asociativa. El algoritmo de reemplazamiento utilizado es LRU (Least Recently Used).

Soluci´ on : DATOS CMp = 2K (211 ) bytes CMc = 128 (27 ) bytes El tama˜ no de l´ınea es 32 (25 ) bytes La cach´e est´a inicialmente vac´ıa. De los datos del enunciado se pueden calcular el n´ umero de l´ıneas L de la Mc. L=25 bytes / 23 bytes/l´ınea = 22 =4 l´ıneas en Mc a) La cach´e emplea correspondencia directa. La direcci´on desde el punto de vista de la Mc tendr´ıa los siguientes campos: n = 11 bits 2 bits ´ındice

4 bits etiqueta

5 bits desplazamiento

En la siguiente tabla se recoge la secuencia de direcciones le´ıdas y los resultados que se producen al ir a buscarlas a Mc:

Direcci´ on 0000 00 00000 0000 00 00100 0000 00 01100 0001 00 00100 0001 00 10100 0000 10 00000 0000 10 01000 0000 00 00000

N. de l´ınea de Mc 0 0 0 0 0 2 2 0

Fallo o acierto Fallo forzoso (se carga Acierto Acierto Fallo forzoso (se carga Acierto Fallo forzoso (se carga Acierto Fallo de conflicto (se l´ınea 0)

el bloque 0 en la l´ınea 0)

el bloque 4 en la l´ınea 0) el bloque 2 en la l´ınea 2) carga el bloque 0 en la

b) La cach´e emplea correspondencia totalmente asociativa. El algoritmo de reemplazamiento utilizado es LRU (Least Recently Used). Se sustituye el bloque utilizado menos recientemente. La direcci´on desde el punto de vista de la Mc tendr´ıa los siguientes campos : n = 11 bits 6 bits etiqueta

5 bits desplazamiento

En la siguiente tabla se recoge la secuencia de direcciones le´ıdas y los resultados que se producen al ir a buscarlas a Mc:

Direcci´ on 000000 00000 000000 00100 000000 01100 000100 00100 000100 10100 000010 00000 000010 01000 000000 00000

N. de l´ınea de Mc 0 0 0 1 1 2 2 0

Fallo o acierto Fallo forzoso (se carga el bloque 0 en la l´ınea 0) Acierto Acierto Fallo forzoso (se carga el bloque 4 en la l´ınea 1) Acierto Fallo forzoso (se carga el bloque 2 en la l´ınea 2) Acierto Acierto

4. Considerando los datos de la tabla adjunta correspondientes a cach´es de correspondencia directa con un tama˜ no 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 las siguientes cuestiones: a) ¿Qu´e sistema presenta una menor raz´ on de fallos, el constitu´ıdo por una cach´e de instrucciones de 16 KB y una cach´e de datos de 16 KB, o el constituido por una cach´e de 32 KB unificada? b) Sup´ ongase que un acierto cach´e requiere un ciclo de reloj, un fallo tiene un costo de 50 ciclos, y que un acierto en una instrucci´on load o store requiere un ciclo extra en el caso de la cach´e unificada, ya que s´ olo existe un puerto de acceso a esta cach´e para satisfacer dos peticiones simult´ aneas. ¿Cu´al es el tiempo medio de acceso a memoria en cada caso? Tama˜ no Cach´e de instrucciones 1 KB 3.06 % 2 KB 2.26 % 4 KB 1.78 % 8 KB 1.10 % 16 KB 0.64 % 32 KB 0.39 %

Cach´e de datos 24.61 % 20.57 % 15.94 % 10.19 % 6.47 % 4.82 %

Cach´e unificada 13.34 % 9.78 % 7.24 % 4.57 % 2.87 % 1.99 %

Soluci´ on : a) Dado que el 75 % de los accesos son referencias a instrucciones, el otro 25 % ser´an accesos a datos, con lo que la raz´on de fallos conjunta para una la cach´e separada ser´ a 75 % × 0,64 % + 25 % × 6,47 % = 2,10 % tomando los datos de tasas de fallos para una cach´e de instrucciones y de datos de 16 KB cada una separadas. La tabla indica que la tasa de fallos de la cach´e unificada de 32 KB es el 1.99 %, lo cual es ligeramente inferior.

b) El tiempo medio de acceso a memoria puede dividirse en t´erminos, el correspondiente a instrucciones y a datos: Tiempo medio de acceso a memoria = Porcentaje de accesos a instrucciones× (Tiempo de acierto + Tasa de Fallos × Penalizaci´ on de fallos)+ Porcentaje de accesos a datos× (Tiempo de acierto + Tasa de Fallos × Penalizaci´ on de fallos) El tiempo de acceso medio a memoria para la cach´e dividida es: 75 % × (1 + 0,64 % × 50) + 25 % × (1 + 6,47 % × 50) = 2,05 El tiempo de acceso medio a memoria para la cach´e unificada es: 75 % × (1 + 1,99 % × 50) + 25 % × (1 + 1 + 1,99 % × 50) = 2,24 As´ı pues, aunque la tasa de fallos del sistema con cach´e separadas sea superior al de la cach´e unificada, su tiempo medio de acceso a memoria es menor que el de la cach´e unificada. 5. La tabla adjunta muestra diferentes porcentajes de la raz´ on de fallos de una cach´e en funci´on de su tama˜ no y el tama˜ no de l´ınea elegidos (expresados en KBytes y bytes, respectivamente). Considera que el sistema de memoria requiere 40 ciclos de reloj de iniciaci´on y a continuaci´ on es capaz de proporcionar 16 bytes cada dos ciclos de reloj. Es decir, proporciona 16 bytes en 42 ciclos de reloj, 32 bytes en 44 ciclos de reloj, y as´ı sucesivamente. Determina qu´e tama˜ no de bloque posee el m´ınimo tiempo medio de acceso a memoria para las cach´es de tama˜ nos 4K, 16K y 64K, respectivamente. Tama˜ no Tama˜ no de la de l´ınea 4K 16K 16 8.57 % 3.94 % 32 7.24 % 2.87 % 64 7.00 % 2.64 %

cach´e 64K 2.04 % 1.35 % 1.06 %

Soluci´ on : Sabemos que Tiempo medio de acceso a memoria = Tiempo de acierto+Tasa de Fallos×Penalizaci´ on de fallos Supongamos que el tiempo de acierto es de un ciclo de reloj independientemente del tama˜ no de la l´ınea y calculemos as´ı los tiempos medios de acceso a memoria para cada combinaci´ on de la tabla. Por ejemplo, si consideramos la cach´e de 4 KBytes, seg´ un la tabla su tasa de fallos es del 8.57 %, y de acuerdo al enunciado el tiempo requerido para traer 16 bytes de la memoria son 42 ciclos. As´ı pues, su tiempo medio de acceso a memoria ser´ a 1 + 8,57 % × 42 = 4,599 ciclos. Si consider´ asemos la misma cach´e pero con un tama˜ no

de l´ınea de 32 bytes, la tasa de fallos ser´ıa del 7.24 % y la penalizaci´ on de fallo de 44 ciclos, puesto que la memoria requiere 44 ciclos para enviar 32 bytes a la cach´e. As´ı pues el tiempo medio de acceso a memoria en este caso ser´ıa 1 + 7,24 % × 44 = 4,186 ciclos. Siguiendo esta mec´anica podemos calcular el tiempo medio de acceso para todas las combinaciones, obteniendo la siguiente tabla: Tama˜ no Penalizaci´ on Tama˜ no de la cach´e de l´ınea de fallo 4K 16K 64K 16 42 4.599 2.655 1.857 32 44 4.186 2.263 1.594 64 48 4.360 2.267 1.509 As´ı pues, para las cach´es de 4 KBytes y de 16 KBytes el mejor tama˜ no de bloque es el de 32 bytes, mientras que la cach´e de 64 KBytes consigue su menor tiempo de acceso medio con un tama˜ no de l´ınea de 64 bytes. 6. Un computador tiene un sistema de dos niveles de cach´e en donde la tasa de fallos local del primer nivel es el 10 % y la del segundo nivel es del 3 %. Los tiempos de acierto de estas cach´es son uno y veinte ciclos, respectivamente; y la penalizaci´ on de fallo para el segundo nivel de cach´e son 100 ciclos. a) ¿Cu´ al es la tasa global de fallos del sistema? b) Calcula el tiempo medio de acceso a un dato. Soluci´ on : a) La f´ ormula para la tasa de fallos global es T Fglobal = T FN1 × T FN2 por tanto T Fglobal = 0,1 ∗ 0,03 = 0,003 o 0,3 % b) El tiempo medio de acceso a un dato, es el tiempo medio de acceso a un dato en la cach´e de nivel 1. La f´ ormula para el tiempo medio de acceso ya la conocemos Tiempo medio de acceso a memoria = Tiempo de acierto+Tasa de Fallos×Penalizaci´ on de fallos y la penalizaci´on de fallos de la cach´e de nivel 1 es igual al tiempo medio de acceso de la cach´e de nivel 2, por tanto Tiempo medio de acceso a memoria = 1 + 0,1 ∗ (20 + 0,03 ∗ 100) = 1 + 0,1 ∗ 23 = 3,3 ciclos 7. Un sistema tiene una memoria f´ısica de 1MB direccionables a nivel de byte. Est´ a dotado de una u ´nica cach´e de datos de correspondencia directa de 32 bytes con l´ıneas de 4 Bytes. Cada acierto en esa cache se resuelve en 1 ciclo mientras que la penalizaci´ on de un fallo es de 10 ciclos. Dado el siguiente c´ odigo: int x,a[128],b[128]; for(i=0;i...