Organización del Computador
Práctico 7

B. Gonzalez Kriegel - N. Wolovick

1. Se implementa una FSM con una ROM como lookup-table y dos FFD.
   

   Locación				Valor
   $A_{0}$		$A_{1}$		$A_{2}$	$R_{0}$		$R_{1}$		$R_{2}$
   0		0		0	0		0		1
   0		0		1	1		1		0
   0		1		0	1		0		0
   0		1		1	0		0		0
   1		0		0	1		0		1
   1		0		1	1		1		1
   1		1		0	0		0		1
   1		1		1	0		0		0

   Construya la tabla y el diagrama de transición de estados para esta máquina de estados finitos.

2. Diseñe una RAM de 8 palabras $\times$ 32 bits ($8\times 32$) usando RAMs de $8\times 8$.

3. Con memorias de $2^{n}$ palabras y 8 bits por palabra muestre:
   1. Como construir una memora de $2^{n}\times 4p$.
   2. Como construir una memora de $2^{n+2}\times p$.

4. Diseñe el circuito de un decodificador árbol 4-a-16 sin tener en cuenta restricciones de fan-in y fan-out.

5. Una memoria caché de mapeo directo consiste en 128 ranuras, cada una conteniendo un bloque de 16 palabras. La memoria contiene 256K¹ palabras. El tiempo de acceso a la caché es de 10ns y el tiempo necesario para llenar una ranura de la caché desde la memoria principal es de 200ns.
   1. Muestre como esta estructura de caché divide las direcciones de memoria.
   2. Calcule el porcentaje de aciertos de un programa que itera 10 veces sobre las direcciones de memoria de la 10 a la 200.
   3. Compute el tiempo de acceso efectivo a memoria para este programa teniendo en cuenta que no se usa load-through.

6. Una caché de mapeo completamente asociativo tiene 16 ranuras para bloques de 8 palabras. La memoria principal es de $2^{16}$ palabras y la cache está vacía inicialmente. El tiempo de acceso a la caché es de 40ns y el tiempo requerido para transferir las 8 palabras desde la memoria principal a la ranura es de $1\mu$s.
   1. Calcule el tamaño de los campos tag y word.
   2. Compute el porcentaje de aciertos para un programa que ejecuta la secuencia de instrucciones $20\ldots 45(28\ldots 45)^{4}$.
   3. Calcule el tiempo de acceso efectivo a memoria, suponiendo nuevamente que no se utiliza load-through.

7. Explique como el caché de mapeo directo y el caché completamente asociativo pueden ser vistos como una particularización de un mapeo asociativo de conjunto de N elementos.

8. Dada una jerarquía de memoria con caché de mapeo directo de $2^{14}$ ranuras de $2^{5}$ palabras y memoria principal de $2^{32}$ palabras.
   1. ¿Cuán alejados deben estar los accesos a memoria para que todas causen una falla en la caché?
   2. Usando el ejercicio (8a) calcule la taza de aciertos y el tiempo de acceso efectivo para un programa con $T_{miss}=1000ns$ y $T_{hit}=10ns$. Asuma que se opera utilizando load-through.

9. A primera vista, la presencia o ausencia de memoria caché no parece tener nada que ver con la decisión de ubicar registros de entrada/salida en el espacio de direcciones de memoria. Piense en los problemas potenciales que esto podría traer.

10. Una computadora tiene 16 páginas de espacio de memoria virtual, pero sólo 4 marcos de página físicos. Tomando inicialmente la memoria vacía, un programa hace referencia a las páginas $(0,7,2,7,5,8,9,2,4)$.

    Indique que referencias causan un fallo de página para la política de reemplazo

    1. LRU.
    2. FIFO.

11. Un sistema de memoria virtual tiene un tamaño de página de 1024 palabras, 8 páginas virtuales, 4 físicas y usa la política de reemplazo LRU. Dado el siguiente estado de la tabla de páginas

    Pag	Present	Disk	PagFrame
    #	Bit	Addr	Field
    0	0	01001011100	xx
    1	0	10100100111	xx
    2	1	01001000110	00
    3	0	00101010000	xx
    4	1	00000111100	01
    5	0	11001100100	xx
    6	1	11101000111	11
    7	0	10101000000	xx

    1. ¿Cuál es la dirección física de la dirección virtual 4096?
    2. ¿Y para la dirección virtual 1024?
    3. Se referencia a una posición de memoria en la página 0 de la memoria virtual, produciéndose una falla de página, ¿Qué marco de página físico será utilizado para almacenar esta página virtual?

12. Un programa dado tiene $N$ accesos a memoria en una arquitectura con caché y memoria virtual paginada. Se producen $M$ fallas en la caché y $F$ fallas de página en la memoria virtual. Dados los tiempos $T_{1}$:acierto caché, $T_{2}$:acierto memoria principal y $T_{3}$:tiempo para cargar una página de memoria desde disco, calcular:
    1. Tasa de aciertos de la caché.
    2. Tasa de aciertos de la memoria principal, donde un acierto es cuando una referencia a memoria no genera una falla de página.
    3. Tiempo de acceso efectivo del sistema completo de memoria.

13. Calcule el almacenamiento necesario para la tabla de páginas de un sistema de memoria virtual de $2^{32}$bytes, con $2^{12}$ bytes por página y 8 bytes por entrada de la tabla de páginas.

14. Compute la cantidad de entradas de compuerta para un decodificador de una RAM de $64\times 1$, utilizando decodificadores 2D y 2-1/2D. Suponga fan-in/fan-out ilimitado y para ambos utilize decodificadores ordinarios de 2 niveles.

    En el caso del esquema 2-1/2D, suponga que la memoria sólo es leída, evitando el uso del DEMUX para las columnas.

15. * Intente mostrar como hacer benchmarks tramposos. Se tienen 2 máquinas con el mismo procesador y memoria principal, pero organizaciones de memoria caché diferentes. Asuma que el miss time es 10 veces el tiempo de un acierto para ambas máquinas. Asuma también que escribir una palabra de 32 bits toma 5 veces más que que un acierto de caché (para una caché write-through) y que escribir un bloque entero de 32 bytes toma 10 veces más que un acierto de caché (para el esquema write-back). El caché está unificado, es decir contiene instrucciones y datos.