ARQUITECTURA DE COMPUTADORES. 2º INGENIERÍA INFORMÁTICA.

Problemas de Gestión de Memoria. 1. Se tiene un procesador de tamaño de palabra 16 bits con un espacio de direcciones de 216 posiciones de memoria con un cache de mapeado directo y 32 entradas, 1 palabra por bloque. El caché esta inicialmente vacío. Se produce la siguiente secuencia de accesos (las direcciones se dan en hexadecimal): NºAcceso Dirección

l l

2 4

3 8

4 5

5 14

6 l1

7 l3

8 24

9 38

10 9

11 41

12 B

13 4

14 2b

15 5

l6 6

17 9

18 l1

l9 8

Se pide: a) Rotular cada referencia como acierto o fallo e indicar cuál es el contenido final del cache. b) Repetir suponiendo cache asociativo con 2 vías. c) Repetir suponiendo cache asociativo con 2 vías y 4 palabras por bloque. d) Repetir suponiendo cache totalmente asociativo. 2. En un procesador con 10 ns. de periodo de reloj, se tiene una caché con una tasa de fallos de 0.05, y una penalización por fallo de 20 ciclos de reloj. Calcular el tiempo medio de los accesos a memoria en función del número N de ciclos que se invierte en un acierto. Suponiendo que se pueda mejorar la tasa de fallo a 0.03 pero aumentando 2 ciclos el tiempo de acceso al cache. ¿Se consigue mejorar el tiempo medio de acceso a memoria? 3. Se tiene un computador A, con un caché de 4 vías con 256 entradas en cada vía. El tamaño total de la memoria que almacena las etiquetas del cache es de 16 Kbits. La memoria que almacena los datos en el caché es de 64 Kbits. ¿Cuál es la organización de la memoria principal (profundidad y anchura) en el computador A? Se tiene un segundo computador B, con un cache con la misma estructura y tamaño que el A. El cache B, sin embargo, carga un bloque de 4 palabras cada vez que se produce un fallo de cache (intenta aprovechar el principio de localidad espacial) ¿Cuál es la organización de la memoria principal (profundidad y anchura) en el computador B? 4. Suponga un procesador de 32 bits, con cache on-chip de 16KB, asociativo 4 vías, con líneas de 4 palabras. Dibuje un diagrama con la organización del cache y los campos en que se divide una dirección de memoria. ¿En qué posición del cache se almacenaría la posición de memoria 0xABCDE8F8? 5. Dada la siguiente información sobre un cache externo: Asociativo 4 vías, bloque de 2 palabras de 16 bits, puede contener hasta 4K dobles palabras de memoria y es usado por un procesador de 16 bits con direcciones de 24 bits. Describa la estructura del cache y muestre cómo se interpretan las direcciones. 6. El 80486 tiene un cache interno unificado de 8Kbytes, asociativo 4 vías con bloques de 4 dobles palabras. Posee un total de 128 conjuntos. Hay un bit de línea válida y 3 bits para el algoritmo pseudo-LRU. En caso de fallo de cache, el 486 lee un bloque de 16 bytes de memoria, siguiendo el método Dato Deseado Primero. Dibuje con el máximo detalle la estructura interna del caché y señale cómo se interpretan las direcciones.

1

20 18

7. Se ejecuta el siguiente código C en una máquina con un procesador que dispone de una memoria caché de datos de 256 bytes con bloques de 4 palabras (de 32 bits): int i,j,zancada,vector[256]; ... for (i=0; i256 (mirar código del programa). Los bloques de memoria principal: j = 0 Æ Bloque 0 de memoria principal. Æ 0 MOD 16 = 0 j = 131 Æ Bloque 32 de memoria principal ya que: 131 / 4 = 32,75 ó 4*32 = 128 es decir, en el bloque Nº 31 de M.P. está contenido el elemento Nº 127 del array. Por lo tanto en el bloque Nº 32 estarán contenidos los elementos Nº-s 128, 129, 130 y 131. Æ 32 MOD 16 = 0 Ahora resulta que los dos accesos que se producen a M.P. debido a la lectura de dos números/palabras corresponden a dos bloques diferentes (el bloque 0 y el 32) de M.P. que han de ubicarse en la misma línea de la memoria caché. Esto supone que se haya que traer y expulsar sucesivamente bloques de la línea cero de la memoria caché produciéndose dos fallos de conflicto en cada iteración del bucle interior. Repetidos estos accesos 10000 veces (bucle exterior) se puede concluir por tanto que el Miss Rate es exactamente uno (MR = 1).

c) Si la memoria caché se convierte en una caché asociativa por conjuntos de dos vías se soluciona el problema anterior y el MR ~ 0. Esto es así porque sólo se han de traer dos bloques distintos de memoria principal en todo el programa y ahora al disponerse de dos líneas por conjunto hay espacio suficiente para ubicar esos dos bloques en el mismo conjunto en caso de necesidad.

d) En primer lugar se va a calcular el tiempo de acceso para el caso A. En el enunciado no se aclara del todo si en los 20t ciclos que se tarda en acceder a la memoria principal son para leer un bloque o solamente una palabra. Se va a suponer que el acceso es a una palabra ya que el acceso de t ciclos a la caché es también para acceder a una palabra. Lo contrario también tiene sentido ya que entre la memoria principal y la caché los intercambios son siempre a nivel de bloque. Primero hay que recordar la expresión del cálculo del tiempo de acceso a memoria caché: Tacc. caché = Tacc. hit + MR*Tpenal. = Tacc. hit + Tacc. fallo Tacc. cache A = Tacc. hit A + Tacc. fallo A = 20000t + 2*(20t*4) = 20160t En caso de fallo traer un bloque a memoria caché cuesta lo mismo que traer 4 palabras por separado. Como ya se ha comentado anteriormente se podría haber supuesto que los 20t son realmente para traer de M.P. las cuatro palabras en paralelo. Para el caso B se realiza un razonamiento similar: Tacc. cache B = Tacc. hit B + Tacc. fallo B = 20000t + 20000*(20t*4) = 1620000t Como se puede ver con estos valores el hecho de tener una cierta organización u otra en la memoria caché puede influir de forma decisiva en el rendimiento general de un computador en determinadas aplicaciones. Estos factores pueden llegar a ser realmente importantes a la hora de por ejemplo de tener que diseñar de un sistema de tiempo real.

8.

Es una cuestión teórica relativa a la memoria virtual. Para responder a la cuestión hay que explicar el proceso de traducción de dirección lógica o virtual a dirección física y finalmente el acceso al dato a través de la caché. Esto se explica en la teoría y en la bibliografía.

9

Si las páginas son de 16KB (2 14 bytes) y la dirección virtual ocupa 40 bits (se pueden direccionar hasta 2 40 posiciones de memoria) tendremos un total de 2 26 = 67108864 páginas posibles en la tabla de páginas.

9.

¿Cuántos bits hay en cada entrada de la tabla de páginas? Sabemos que la dirección física ocupa 36 bits y que 14 de esos bits son para el desplazamiento dentro de la página. Por lo tanto la dirección de un marco en memoria principal será de 22 bits (36 – 14). ¿Cuánto ocupa por tanto la tabla de páginas? TP = 2 26 páginas en la TP*(22 bits de dirección del marco en MP + 4 bits de control por página) = 26*2 26 bits = 26*64 Mbits = 1664 Mbits = 208 Mbytes El esquema de traducción de direcciones será el siguiente: Dirección virtual

40 bits número de página virtual (26 bits)

Desplazamiento (14 bits)

TABLA DE PÁGINAS Bits de control 0 . . . . . 2

Dirección física

26

Dirección de Marco en MP

4 bits

22 bits

-1

36 bits número de página física o marco (22 bits)

Desplazamiento (14 bits)

Como apunte se podría decir que el tamaño de la tabla de páginas de un proceso es tan grande que habría que recurrir a técnicas de reducción/compactación de tamaño tales como hacer crecer dinámicamente la tabla, funciones hash, paginar la tabla de páginas, ...

10