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


\documentclass[a4paper]{article}

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

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

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

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


\begin{document}
\maketitle

\begin{enumerate}

	\item{Dise\~ne una ALU de 1 bit utilizando el esquema parcial de la figura siguiente.
		Esta ALU realiza las operaciones de suma, AND, OR y NOT sobre las entradas de 1 bit $A,B$
		poniendo el resultado en la salida $Z$ seg\'un las entradas $F_{0},F_{1}$ como muestra la tabla.
		
		Solo interconecte los componentes dados, no agregue ning\'un tipo de dispositivo l\'ogico.
		
		\bigskip
		\begin{tabular}{cc}
		\includegraphics[keepaspectratio=true, height=65mm]{p5e1.eps}
		&
		\begin{small}
		\begin{tabular}{|cc|c|}
			\hline $F_{0}$ & $F_{1}$ & Funci\'on \\
			\hline 0 & 0 & ADD(A,B) \\
			\hline 0 & 1 & AND(A,B) \\
			\hline 1 & 0 & OR(A,B)  \\
			\hline 1 & 1 & NOT(A)   \\
			\hline
		\end{tabular}
		\end{small}
		\end{tabular}
	}
	

	\item{Dise\~ne una ALU (que s\'olo realiza operaciones l\'ogicas) de 8 bits que tome dos entradas
		$X,Y$ de 8 bits y produzca una salida $Z$ tambi\'en de 8 bits.
		Las entradas de control son $C_{1}C_{0}$ y operan de la siguiente forma:
		\begin{small}
		\begin{center}
		\begin{tabular}{|cc|c|}
			\hline $C_{1}$ & $C_{0}$ & Funci\'on \\
			\hline 0 & 0 & AND(X,Y) \\
			\hline 0 & 1 & OR(X,Y) \\
			\hline 1 & 0 & NOR(X,Y)  \\
			\hline 1 & 1 & XOR(X,Y)   \\
			\hline
		\end{tabular}
		\end{center}
		\end{small}
		Realice un dise\~no \emph{top-down}, mostrando primero el diagrama en bloques
		utilizando ALUs de 1 bit, luego cree la tabla de verdad de cada una de estas ALU y finalmente
		obtenga una implementaci\'on de la ALU de 1 bit utilizando un MUX 8-a-1.
	}
	
	\item{Siguiendo el diagrama del \emph{datapath} de una peque\~n\'{\i}sima arquitectura que se muestra a
		continuaci\'on, obtenga la \emph{secuencia de control} para realizar las operaciones
		\begin{enumerate}
			\item{$r_{0} \leftarrow r_{0}-r_{1}$}
			\item{$r_{0} \leftarrow nxor(r_{0},r_{1})$}
		\end{enumerate}
		\begin{center}
		\begin{tabular}[t]{cc}
			\includegraphics[keepaspectratio=true, height=40mm]{p5e3.eps}
			&
			\begin{small}
			\begin{tabular}{|cc|c|}
				\hline $F_{0}$ & $F_{1}$ & Funci\'on \\
				\hline 0 & 0 & ADD(A,B) \\
				\hline 0 & 1 & AND(A,B) \\
				\hline 1 & 0 & A  \\
				\hline 1 & 1 & NOT(A) \\
				\hline
			\end{tabular}
			\end{small}
		\end{tabular}
		\end{center}
		
		La resta deber\'a ser utilizando complemento a 2's, y no podr\'a modificar ning\'un registro
		excepto $r_{0},r_{1}$.
		Para la operaci\'on $nxor$ necesitar\'a un registro temporal.
		Suponga que inicialmente el registro $r_{3}$ contiene el valor 1.

		A continuaci\'on se muestra el formato de la palabra de control que deber\'a utilizar.
		\begin{small}
		\begin{center}
		\begin{tabular}{|c|c|c|c||c|c|c|c||c|c|c|c||c|c|}
			\hline \multicolumn{4}{|c||}{Hab.Escr.} & \multicolumn{4}{c||}{Hab.Bus A} &
				\multicolumn{4}{c||}{Hab.Bus B} & \multicolumn{2}{c|}{} \\
			\hline 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & 0 & 1 & 2 & 3 & $F_{0}$ & $F_{1}$ \\
			\hline &&&&&&&&&&&&&\\
			\hline
		\end{tabular}
		\end{center}
		\end{small}
		Cuando no necesite realizar operaciones en un bus, puede poner todas sus l\'{\i}neas de
		selecci\'{o}n en 0.
	}

	\item{\label{ej:ass}
		Escriba la forma binaria para las $\mu$instrucciones mostradas.
		Utilize el formato del ejercicio~\ref{ej:dis} y rellene con 0's los bits cuyo valor resulta indistinto.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			60: \= R[temp0] \= $\leftarrow$ \= NOR(R[0],R[temp0]); \= IF Z THEN GOTO 64; \\
			61: \> R[rd] \> $\leftarrow$ \> INC(R[rs1]); \\
		\end{tabbing}
		\end{center}
		\end{small}
		}
	}
	
	\item{\label{ej:dis}
		Realice ahora el proceso inverso, es decir a partir de las palabras binarias de control que se
		dan, obtenga la versi\'on nemot\'ecnica utilizando el lenguaje $\mu$assembler como se mostr\'o en
		el ejercicio~\ref{ej:ass}.
		\texttt{
		\begin{small}
		\begin{center}
		\begin{tabular}{|c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}
				c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c|}
			\hline &&&&&&A&&&&&&&B&&&&&&&C&R&W&\multicolumn{18}{c|}{} \\
			\multicolumn{6}{|c}{A} & $M_{x}$ & \multicolumn{6}{c}{B} & $M_{x}$ &
				\multicolumn{6}{c}{C} & $M_{x}$ & D & R &
				\multicolumn{4}{c}{ALU} & \multicolumn{3}{c}{Cond} &
				\multicolumn{11}{c|}{DirSalto} \\
			\hline
			1&0&0&0&0&0& 0& 1&0&0&0&0&1& 0& 1&0&0&0&0&0& 0& 0& 0& 1&0&0&0& 1&1&0& 0&0&0&0&0&0&0&0&0&0&0 \\
			1&0&0&1&0&1& 0& 1&0&0&1&0&1& 0& 1&0&0&1&0&1& 0& 0& 0& 1&0&0&0& 1&0&1& 0&0&0&0&0&0&1&0&0&0&0 \\
			0&0&0&0&0&0& 0& 0&0&0&0&0&0& 0& 0&0&0&0&0&0& 0& 0& 0& 0&1&0&1& 1&0&0& 0&0&0&0&0&0&0&1&1&0&0 \\
			\hline
		\end{tabular}
		\end{center}
		\end{small}
		}
		?`Que secci\'on del microc\'odigo es?
	}
	
	\item{?`Cu\'antas $\mu$instrucciones puede tener una instrucci\'on ARC sin tener que cambiar el
		flujo de control a la parte baja del almacenamiento de control luego que la $\mu$operaci\'on
		\Prog{Decode} produjo el salto a la parte alta correspondiente al opcode combinado?
	}
	
	\item{Extienda el juego de instrucciones de ARC para incluir una nueva instrucci\'on, modificando
		el $\mu$programa.
		La nueva instrucci\'on es \Prog{andn}, realiza la operaci\'on l\'ogica $nand$ entre
		sus operandos y \underline{no} modifica los c\'odigos de condici\'on.
		La instrucci\'on estar\'a entre las de formato artim\'etico ($op=10$) y tendr\'a $op3=010100$.
		Deber\'a interpretar adecuadamente el bit 13 de direccionamiento inmediato.
	}
	
	\item{En muchas porciones del $\mu$c\'odigo se utilizan instrucciones del tipo \Prog{ADD(a,a)}
		para obtener desplazamientos aritm\'eticos a izquierda.
		Demuestre formalmente a partir de las especificaciones que
		\Prog{s$\leftarrow$a+a $\equiv$ s$\leftarrow$LSHIFT(a)}.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			$\{a=(a_{n-1},\ldots,a_{0})\}$ \\
			\ \ \ s$\leftarrow$a+b \\
			$\{s=(s_{n-1},\ldots,s_{0}) \wedge s_{0}=a_{0}\oplus b_{0} \wedge
			   (\forall i : i\geq 1 : s_{i}=a_{i}\oplus b_{i}\oplus c_{i})$ \\
			$\ \ \ \ \ \ \ [ c_{0}=0 \wedge (\forall i : i\geq 0 :
					c_{i+1} = a_{i}b_{i}+a_{i}c_{i}+b_{i}c_{i}) ] \}$ \\
			\\
			$\{a=(a_{n-1},\ldots,a_{0})\}$ \\
			\ \ \ s$\leftarrow$LSHIFT(a) \\
			$\{s=(s_{n-1},\ldots,s_{0}) \wedge s_{0}=0 \wedge (\forall i : i\geq 0 : s_{i+1}=a_{i}) \}$
		\end{tabbing}
		\end{center}
		\end{small}
		}
	}	
	
	\item{Comparar la cantidad pasos que toma ejecutar con control $\mu$programado y control cableado:
		\begin{enumerate}
			\item{La instrucci\'on \Prog{ld} con y sin operador inmediato.}
			\item{El salto por signo negativo \Prog{bneg} suponiendo que $N=1$ o sea el salto
				se realiza.}
		\end{enumerate}
		
		En el control $\mu$programado la cuenta est\'a dada por la \emph{cantidad de $\mu$instrucciones}
		que se ejecutan desde el comienzo en la direcci\'on 0 hasta que se vuelve a ella.
		Para el control cableado la cuenta es la \emph{cantidad de estados} visitados desde el inicio
		en el estado 0 hasta que la secuencia regresa a \'el.
		
		En ambos casos escriba la secuencia de ejecuci\'on. En un tipo de contol ser\'a una
		secuencia de $\mu$direcciones y en el otro de estados.
		
		Compare ambos acercamientos con los elementos obtenidos.
	}
	
	\item{La l\'{\i}nea 2047 del $\mu$programa ARC contiene una $\mu$instrucci\'on \Prog{GOTO 0}.
		?`Cambiar\'a el comportamiento del $\mu$programa si cambiamos esta $\mu$instrucci\'on por un
		\Prog{skip}?
	}
	
	\item{En la \emph{$\mu$programaci\'on horizontal}, las $\mu$palabras son anchas, mientras que en la
		\emph{$\mu$programaci\'on vertical} resultan angostas.
		En general la diferencia reside en que para la $\mu$programaci\'on horizontal las se\~nales de
		selecci\'on de los buses se encuentran decodificadas, mientras que en la vertical es necesario
		incluir decodificadores $n$ en $2^{n}$, perdiendo velocidad pero reduciendo los requerimientos
		de la memoria de control~\footnote{\emph{Trade-off} entre
		almacenamiento y velocidad.}.
		
		Si hici\'eramos m\'as anchas las $\mu$palabras expandiendo $A$, $B$ y $C$ a 38 bits para contener
		un \'unico bit de selecci\'on por cada uno de los 38 registros:
		\begin{enumerate}
			\item{Calcular el ancho de la nueva $\mu$palabra.}
			\item{?`En qu\'e procentaje se incrementar\'a el $\mu$almacenamiento?}
		\end{enumerate}
	}
	
	\item{Se quiere llevar la idea de la nanoprogramaci\'on un paso m\'as all\'a y crear una
		picomemoria que ser\'{\i}a referenciada por la nanomemoria donde esta ahora contendr\'{\i}a
		picodirecciones.
		?`Tiene sentido este planteamiento?
	}
	
	\item{La ALU de ARC se implementa con una tabla de b\'usqueda (\emph{lookup table - LUT}).
		Muestre la tabla LUT$_{0}$ y LUT$_{x}\ x>0$ para la operaci\'on \Prog{INC(A)}
		($F_{3}F_{2}F_{1}F_{0}=1101$).
	}
	
	\item{?`Habr\'a que cambiar el $\mu$programa de la ARC si se modifica la ALU para que trabaje
		en cpl1's en vez de cpl2's? Donde suponemos que siempre tomamos la representaci\'on
		adecuada de los	n\'umeros con signo en nuestros programas.
	}

	\item{*\footnote{La primera persona que entregue el ejercicio correcto y completo, sumar\'a 1
		punto m\'as en la nota del examen final escrito.}
		En el pr\'actico 4a se utiliz\'o mucho la siguiente
		construcci\'on en la ISA de ARC para compilar la expresi\'on booleana $a\geq b$.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			label: \= addcc \= \%r1,\%r2,\%r3 \kill
			\> subcc \>\%r1, \%r2, \%r0 \\
			\> bpos \> label
		\end{tabbing}
		\end{center}
		\end{small}
		}

		Sin embargo esto produce problemas si, por ejemplo el primer argumento es positivo y el segundo negativo.
		Para n\'umeros de 8 bits con signo en complemento a 2's, este test dice que $\neg (2\geq -128)$.
		
		La soluci\'on est\'a en verificar en conjunto los bits de estado $N$ y $V$.
		\begin{enumerate}
			\item{Encuentre la expresi\'on l\'ogica entre $N$ y $V$ que si resulte equivalente
				a $a\geq b$ luego de hacer la resta.}
			\item{Modifique el $\mu$programa de ARC para incluir la instrucci\'on de salto \Prog{bge}
				(\emph{branch greater equal}) con lo realizado en el punto anterior.}
			\item{Muestre como, a partir de esta instrucci\'on, podemos compilar guardas de la
				forma $a>b$, $a\leq b$ y $a<b$.}
		\end{enumerate}
	}
\end{enumerate}
\end{document}
	


