%==============================================================================
%TODO
%
%==============================================================================


\documentclass[a4paper]{article}

\newcommand{\Prog}[1]{\texttt{#1}}

\setlength\textwidth{6.5in}
\setlength\oddsidemargin{0in}
\setlength\evensidemargin{0in}

%\setlength\topmargin{0in}
%\setlength\textwidth{6.7in}
%setlength\oddsidemargin{0in}
%\setlength\evensidemargin{0in}
%\setlength\headheight{0in}
%\setlength\headsep{0in}
%\setlength\footskip{0in}


\usepackage{latexsym}
\usepackage[spanish]{babel}
\usepackage[]{graphicx}

\title{Organizaci\'{o}n del Computador \\ Pr\'{a}ctico 6}
\author{B. Gonzalez Kriegel - N. Wolovick}


\begin{document}
\maketitle

\begin{enumerate}

	\item{Se implementa una FSM con una ROM como \emph{lookup-table} y dos FFD.
		
%		\bigskip
		\begin{center}
		\begin{tabular}{cc}
		\includegraphics[keepaspectratio=true, height=35mm]{p6e1.eps}
		&
		\begin{tiny}
		\begin{tabular}{|c@{}c@{}c|c@{}c@{}c|}
			\hline \multicolumn{3}{|c}{Locaci\'on} & \multicolumn{3}{|c|}{Valor}\\
			$A_{0}$ &  $A_{1}$ & $A_{2}$ & $R_{0}$ & $R_{1}$ & $R_{2}$  \\
			\hline 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 \\
			\hline
		\end{tabular}
		\end{tiny}
		\end{tabular}
		\end{center}
		
		Construya la tabla y el diagrama de transici\'on de estados para esta
		m\'aquina de estados finitos.
	}
	

	\item{Dise\~ne una RAM de 8 palabras $\times$ 32 bits ($8\times 32$) usando RAMs de
		$8\times 8$.
	}
	
	\item{Con memorias de $2^{n}$ palabras y 8 bits por palabra muestre:
		\begin{enumerate}
			\item{Como construir una memora de $2^{n}\times 4p$.}
			\item{Como construir una memora de $2^{n+2}\times p$.}
		\end{enumerate}
	}
	
	\item{Dise\~ne el circuito de un decodificador \'arbol 4-a-16 sin tener en cuenta restricciones
		de \emph{fan-in} y \emph{fan-out}.
	}
	
	\item{Una memoria cach\'e de mapeo directo consiste en 128 ranuras, cada una
		conteniendo un bloque de 16 palabras.
		La memoria contiene 256K\footnote{Cuando hablamos de memorias 1K=1024} palabras.
		El tiempo de acceso a la cach\'e es de 10ns y el tiempo necesario para llenar una
		ranura de la cach\'e desde la memoria principal es de 200ns.
		\begin{enumerate}
			\item{Muestre como esta estructura de cach\'e divide las direcciones de memoria.}
			\item{Calcule el porcentaje de aciertos de un programa que itera 10 veces sobre
			las direcciones de memoria de la 10 a la 200.}
			\item{Compute el tiempo de acceso efectivo a memoria para este programa
				teniendo en cuenta que no se usa \emph{load-through}.}
		\end{enumerate}
	}
	
	\item{Una cach\'e de mapeo completamente asociativo tiene 16 ranuras para bloques de 8 palabras.
		La memoria principal es de $2^{16}$ palabras y la cache est\'a vac\'{\i}a inicialmente.
		El tiempo de acceso a la cach\'e es de 40ns y el tiempo requerido para transferir las 8
		palabras desde la memoria principal a la ranura es de $1\mu$s.
		\begin{enumerate}
			\item{Calcule el tama\~no de los campos \emph{tag} y \emph{word}.}
			\item{Compute el porcentaje de aciertos para un programa que ejecuta la secuencia
				de instrucciones $20\ldots 45(28\ldots 45)^{4}$.}
			\item{Calcule el tiempo de acceso efectivo a memoria, suponiendo nuevamente que
				no se utiliza \emph{load-through}.}
		\end{enumerate}
	}
	
	\item{Explique como el cach\'e de mapeo directo y el cach\'e completamente asociativo pueden
		ser vistos como una particularizaci\'on de un mapeo asociativo de conjunto de N elementos.
	}
	
	\item{Dada una jerarqu\'{\i}a de memoria con cach\'e de mapeo directo de $2^{14}$ ranuras de $2^{5}$
		palabras y memoria principal de $2^{32}$ palabras.
		\begin{enumerate}
			\item{\label{ej:jera_a}?`Cu\'an alejados deben estar los accesos a memoria para que todas causen
				una falla en la cach\'e?}
			\item{Usando el ejercicio (\ref{ej:jera_a}) 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 \emph{load-through}.}
		\end{enumerate}
	}

	\item{A primera vista, la presencia o ausencia de memoria cach\'e no parece tener nada que ver
		con la decisi\'on de ubicar registros de entrada/salida en el espacio de direcciones
		de memoria.
		Piense en los problemas potenciales que esto podr\'{\i}a traer.
	}

	\item{Una computadora tiene 16 p\'aginas de espacio de memoria virtual, pero s\'olo 4 marcos
		de p\'agina f\'{\i}sicos.
		Tomando inicialmente la memoria vac\'{\i}a, un programa hace referencia a las
		p\'aginas $(0,7,2,7,5,8,9,2,4)$.
		
		Indique que referencias causan un fallo de p\'agina para la pol\'{\i}tica de reemplazo
		\begin{enumerate}
			\item{LRU.}
			\item{FIFO.}
		\end{enumerate}
	}

	\item{Un sistema de memoria virtual tiene un tama\~no de p\'agina de 1024 palabras, 8 p\'aginas
		virtuales, 4 f\'{\i}sicas y usa la pol\'{\i}tica de reemplazo LRU.
		Dado el siguiente estado de la tabla de p\'aginas
		\begin{center}
		\begin{tiny}
		\begin{tabular}{c|c|c|c|}
			Pag & Present & Disk & PagFrame \\
			\# & Bit & Addr & Field \\
%			Pag\# & PresentBit & DiskAddr & PagFrameField \\
			\cline{2-4} 0 & 0 & 01001011100 & xx \\
			\cline{2-4} 1 & 0 & 10100100111 & xx \\
			\cline{2-4} 2 & 1 & 01001000110 & 00 \\
			\cline{2-4} 3 & 0 & 00101010000 & xx \\
			\cline{2-4} 4 & 1 & 00000111100 & 01 \\
			\cline{2-4} 5 & 0 & 11001100100 & xx \\
			\cline{2-4} 6 & 1 & 11101000111 & 11 \\
			\cline{2-4} 7 & 0 & 10101000000 & xx \\
 			\cline{2-4}
		\end{tabular}
		\end{tiny}
		\end{center}
		
		\begin{enumerate}
			\item{?`Cu\'al es la direcci\'on f\'{\i}sica de la direcci\'on virtual 4096?}
			\item{?`Y para la direcci\'on virtual 1024?}
			\item{Se referencia a una posici\'on de memoria en la p\'agina 0 de la memoria
				virtual, produci\'endose una falla de p\'agina, ?`Qu\'e marco de p\'agina
				f\'{\i}sico ser\'a utilizado para almacenar esta p\'agina virtual?}
		\end{enumerate}
	}

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

	\item{Calcule el almacenamiento necesario para la tabla de p\'aginas de un sistema de memoria
		virtual de $2^{32}$bytes, con $2^{12}$ bytes por p\'agina y 8 bytes por entrada de
		la tabla de p\'aginas.
	}

	\item{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 \emph{fan-in}/\emph{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\'olo es le\'{\i}da,
		evitando el uso del DEMUX para las columnas.
	}

	\item{* Intente mostrar como hacer \emph{benchmarks tramposos}.
		Se tienen 2 m\'aquinas con el mismo procesador y memoria principal, pero
		organizaciones de memoria cach\'e diferentes.
		Asuma que el \emph{miss time} es 10 veces el tiempo de un acierto para ambas m\'aquinas.
		Asuma tambi\'en que escribir una palabra de 32 bits toma 5 veces m\'as que que un acierto
		de cach\'e (para una cach\'e \emph{write-through}) y que escribir un bloque entero de 32 bytes
		toma 10 veces m\'as que un acierto de cach\'e (para el esquema \emph{write-back}).
		El cach\'e est\'a unificado, es decir contiene instrucciones y datos.
		\vspace{-.2in}
		\paragraph{Cach\'e A} 128 conjuntos, 2 elementos por conjunto, bloques de 32 bytes,
			con \emph{write-through} y \emph{no-write-allocate}.
		\vspace{-.2in}
		\paragraph{Cach\'e B} 256 conjuntos, 1 elemento por conjunto, bloques de 32 bytes, con
			\emph{write-back} y \emph{write-allocate}.
		\begin{enumerate}
			\item{Describa un programa en ensamblador que haga correr la m\'aquina A
				lo m\'as r\'apido posible respecto a la m\'aquina B.}
			\item{Idem pero con la m\'aquina B gan\'andole a la A.}
		\end{enumerate}
	}
	
	\item{* En este ejercicio se correr\'a un programa para evaluar el comportamiento de un sistema
		de memoria.
		Un programa en C para UNIX que se encuentra para bajar en la p\'agina de la materia,
		nos permite hacer estas mediciones (\Prog{stride.c}).
		
		En la primera parte este programa se presenta una funci\'on para obtener una medici\'on
		precisa del tiempo.
		En la segunda parte, un arreglo se lee y escribe en rangos crecientes
		de longitud $2^{n}$ y por cada uno de estos rangos se hacen accesos de a saltos
		(\emph{strides}) cada vez m\'as grandes, desde $2^{0}$ hasta $2^{n-1}$.
		El c\'odigo se repite varias veces a fin de obtener mayor precisi\'on en la medici\'on.
		
		La tercera parte repite exactamente el mismo lazo pero no efectua operaciones con la
		memoria para poder medir y luego restar el tiempo de \emph{overhead} que tiene la
		repetici\'on.
		La parte final imprime los tiempos de acceso de la memoria para cada tama\~no y salto.
		
		Resulta importante asegurar que el compilador hace caso al modificador \Prog{register},
		a fin de no interferir la memoria con lecto-escrituras de las variables que controlan
		los lazos.
		\begin{enumerate}
			\item{Grafique los resultados experimentales con el eje $X$ indicando
				saltos de memoria y el eje $Y$ los tiempo de acceso y una serie por cada
				tama\~no de de cach\'e.
				Use escala logar\'{\i}tmica para el eje $X$.}
			\item{?`Cu\'antos niveles de cach\'e hay en la jerarqu\'{\i}a de memoria?}
			\item{?`Cu\'al es el tama\~no de la cache L1? ?`Cu\'al es su asociatividad?}
			\item{?`Cu\'al es el tama\~no de la cache L2 (si existe)? ?`Cu\'al es su asociatividad?}
			\item{?`Hay algo m\'as que usted haya descubierto acerca de la jerarqu\'{\i}a de memoria
				a partir de estos experimentos?}
		\end{enumerate}
	}
	
\end{enumerate}
\end{document}

	











