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


\documentclass[a4paper]{article}

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

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

\setlength\textheight{9in}

\setlength\topmargin{0in}
\setlength\headheight{0in}
\setlength\headsep{0in}
\setlength\footskip{.3in}

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

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


\begin{document}
\maketitle

\begin{enumerate}

	\item{Un mapa de memoria tiene $2^{24}$ localizaciones direccionables. ?`Cu\'al es el menor ancho en bits
		que las direcciones pueden tener para poder referenciar toda la memoria?
	}

	\item{Dar la direcci\'on de memoria m\'as baja y m\'as alta en un mapa de memoria direccionable por 20 bits,
		donde la menor unidad direccionable es una palabra de 4 bytes.
	}
	
	\item{\label{ej:swap}
		Escriba un fragmento de c\'odigo ARC que efect\'ue el intercambio del contenido de las posiciones de
		memoria $x$ y $y$. Use la menor cantidad de registros posible.
	}

	\item{\label{ej:sum2array}
		A continuaci\'on se muestra un pedazo de c\'odigo assembler.
		?`Qu\'e es lo que hace? ?`Suma cosas o limpia una zona de la memoria?
		Comente la funcionalidad de cada una de las variables (\Prog{\%r1,\%r2,\%r3,\%r4}) y de las
		posiciones de memoria $k$, $a$, $b$ y $c$, donde estas 3 \'ultimas se suponen definidas en alg\'un
		lugar del c\'odigo.
		Una vez comprendida la funcionalidad del c\'odigo, expr\'esela (tratando de mantener la estructura)
		en alg\'un lenguaje imperativo de alto nivel y en alg\'un lenguaje funcional a manera de
		especificaci\'on abstracta.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			label: \= addcc \= \%r1,\%r2,\%r3 \kill
			Y: \> ld \> [k], \%r1 \\
			\> addcc \>\%r1, -4, \%r1 \\
			\> st \> \%r1, [k] \\
			\> bneg \> X \\
			\> ld \> [a], \%r1, \%r2 \\
			\> ld \> [b], \%r1, \%r3 \\
			\> addcc \> \%r2, \%r3, \%r4 \\
			\> st \> \%r4, \%r1, [c] \\
			\> ba Y \\
			X: \> jmpl \> \%r15 + 4, \%r0 \\
			k: \> 40
		\end{tabbing}
		\end{center}
		\end{small}
		}
	}

	\item{Un pager de bolsillo contiene un peque\~no procesador con $2^{7}$ palabras de memoria de 8 bits.
		La ISA tiene 4 registros: \Prog{R0}, \Prog{R1}, \Prog{R2} y \Prog{R3}.
		Cada instrucci\'on es una palabra de 16 bits (2 lugares de memoria), cuyo formato se muestra a
		continuaci\'on:
			\begin{center}
				\includegraphics[keepaspectratio=true, height=15mm]{ej4-6.eps}
			\end{center}
		
		Los 3 primeros bits de la instrucci\'on define el \emph{opcode} y la siguiente tabla resume los
		8 posibles c\'odigos de operaci\'on:
		
		\begin{small}\begin{center}\begin{tabular}{c|c|l}
			Mnem\'onico & Opcode & Significado \\ \hline
			LOAD & 000 & Dst $\leftarrow$ Src o memoria \\
			STORE & 001 & Dst o memoria $\leftarrow$ Src \\
			ADD & 010 & Dst $\leftarrow$ Src + Dst \\
			AND & 011 & Dst $\leftarrow$ AND(Src,Dst) \\
			BZERO & 100 & Salta si Src=0 \\
			JUMP & 101 & Salto incondicional \\
			COMP & 110 & Dst $\leftarrow$ complemento de Src \\
			RSHIFT	& 111 & Dst $\leftarrow$ Src desplazado a la izq. 1 bit
		\end{tabular}\end{center}\end{small}
		Los 3 bits que definien la fuente o el destino responden a los siguientes patrones:
		\begin{small}\begin{center}\begin{tabular}{cc}
			\begin{tabular}{c|c}
				Modo & Patr\'on de bits \\ \hline
				Registro & 0 \\
				Directo & 1
			\end{tabular}
			&
			\begin{tabular}{c|c}
				Registro & Patr\'on de bits \\ \hline
				R0 & 00 \\
				R1 & 01 \\
				R2 & 10 \\
				R3 & 11 				
			\end{tabular}
		\end{tabular}\end{center}\end{small}
		A lo m\'as 1 operando puede obtenerse de modo directo (en una locaci\'on de memoria), y en caso
		de que alguno de los dos lo sea, el campo fuente o destino no se utiliza y la direcci\'on de memoria
		se obtiene del campo direcci\'on.
		
		\begin{enumerate}
			\item{Escriba un programa utilizando c\'odigo objeto (no c\'odigo ensamblador) que intercambie
				el contenido de los registros $R0$ y $R1$.
				S\'olo utilice registros para no modificar la escasa memoria.
				No deber\'{\i}a emplear m\'as de 4 instrucciones, y es posible	hacerlo en menos.
				Ponga 0's en los bits cuyo valor resulte indistinto.
			}
			\item{Escriba un programa en c\'odigo objeto que intercambie el contenido de las posiciones
				de memoria 12 y 13.
				Como en el punto anterior, usted s\'olo podr\'a usar registros.
				Ponga 0's en los bits cuyo valor resulte indistinto.
			}
		\end{enumerate}		
	}

	\item{Un programa escrito en leguaje ensamblador para la arquitectura ARC llama a la subrutina \Prog{foo},
		pas\'andole 3 argumentos $a$, $b$ y $c$.
		La subrutina tiene 2 variables locales, $n$ y $m$ y no retorna valor alguno.
		
		Usando la notaci\'on de libro muestre la posici\'on del puntero de la pila y los elementos
		relevantes almacenados en ella para la convenci\'on de llamadas basada en pila en los siguientes
		momentos:
		\begin{enumerate}
			\item{Justo antes de ejecutar la instrucci\'on \Prog{call} en la etiqueta $x$.}
			\item{Cuando se completa el marco de pila para la subrutina $foo$.}
			\item{Exactamente antes de ejecutar la instrucci\'on de carga en la etiqueta $z$.}
		\end{enumerate}
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			label: \= addcc \= \%r1,\%r2,\%r3 \kill
			\>\> $\vdots$ \\
			!los argumentos a, b y c estan listos en la pila \\
			x: \> call \> foo \\
			z: \> ld \>\%r1, \%r2 \\
			\>\> $\vdots$ \\
			\>\> $\vdots$ \\
			foo: \> !aqui empieza la subrutina \\
			\>\> $\vdots$ \\
			y: \> jmpl \> \%r15 + 4, \%r0 \\
		\end{tabbing}
		\end{center}
		\end{small}
		}
		
	}
	
	\item{?`Porqu\'e \Prog{sethi} s\'olo carga los 22 bits altos de un registro? ?`No ser\'{\i}a mejor
	cargar los 32 bits de un registro?
	Intente explicar este hecho.
	}

	\item{Un programa compilado para un ISA de SPARC escribe el entero sin signo de 32 bits \Prog{0xABCDEF01}
		a un archivo y lo lee correctamente.
		El mismo programa compilado para un ISA de Pentium tambi\'en trabaja de manera satisfactoria.
		Sin embargo cuando el archivo es transferido entre m\'aquinas, el programa lee incorrectamente
		el entero del archivo como \Prog{0x01EFCDAB}.
		?`Qu\'e es lo que sucede?
	}

	\item{Se tiene una ISA con opcodes de 8 bits, operandos y direcciones de 16 bits, donde los datos se
		mueven desde y hacia la memoria en trozos de 16 bits.
		\begin{enumerate}
			\item{Escriba tres programas usando instrucciones de 3-direcciones, 2-direcciones y
				1-direcci\'on que computen la sentencia $A\!:=\!(B\!+\!C)\!*\!(D\!+\!E)$.
				Su c\'odigo no debe sobreescribir ninguno de los operandos y puede usar tantos
				registros ($R_{0},R_{1},\ldots$) para c\'alculos intermedios como sea necesario.
			}
			\item{Compute el tama\~no en bytes de cada uno de sus programas.}
			\item{Compute el tr\'afico de memoria que cada uno de sus programa generar\'a en
				tiempo de ejecuci\'on, incluyendo la obtenci\'on de cada instrucci\'on
				(\emph{instruction fetching}).}
		\end{enumerate}
	}

	\item{Repita el ejercicio anterior, s\'olo que ahora suponga la ISA de ARC para su programa.
		Utilice los mnem\'onicos \Prog{sub\{cc\}} para la resta y \Prog{smul} para la multiplicaci\'on.
	}
	
	\item{Una arquitectura distinta a la ARC, que se clasifica como \emph{de registros generales}, es la
		arquitectura basada en pila.
		Esta \textsl{stack-based architecture} (junto con la \textsl{acumulator architecture}) dominaron
		el mercado en los 60's y 70's, pero actualmente est\'an en desuso.
		
		Por ejemplo, la siguiente secuencia de instrucciones eval\'ua la expresi\'on $A\!+\!B\!*\!C$:
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			...... \= \kill
			\> PUSH B  \\
			\> PUSH C  \\
			\> MULT    \\
			\> PUSH A  \\
			\> ADD
		\end{tabbing}
		\end{center}
		\end{small}
		}
		Escriba un programa en esta arquitectura que eval\'ue la expresi\'on $(B\!+\!C)\!*\!(D\!+\!E)$.
	}
		

	\item{Cree la tabla de s\'{\i}mbolos para el siguiente fragmento de c\'odigo ARC.
		S\'olo se pide que la tabla muestre el mapeo (s\'{\i}mbolo, valor) y que se marque como ``U'' un
		s\'{\i}mbolo no definido.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			label: \= addcc \= \%r1,\%r2,\%r3 \kill
			x \> .equ \> 4000 \\
			\> .org \> 2048 \\
			\> ba \> main \\
			\> .org \> 2072 \\
			main: \> sethi \> x, \%r2 \\
			\> srl \> \%r2, 10, \%r2 \\
			lab\_4: \> st \> \%r2, [k] \\
			\> addcc \> \%r1, -1, \%r1 \\
			foo: \> st \> \%r1, [k] \\
			\> andcc \> \%r1, \%r1, \%r0 \\
			\> be \> lab\_5 \\
			\> jmpl \> \%r15 + 4, \%r0 \\
			cons: \> .dwb \> 3
		\end{tabbing}
		\end{center}
		\end{small}
		}
	}

	\item{Traduzca el siguiente c\'odigo ensamblador ARC en c\'odigo objeto.
		Asuma que $x$ est\'a en la posici\'on $(4096)_{10}$.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			label: \= addcc \= \%r1,\%r2,\%r3 \kill
			k \> .equ \> 1024 \\
			\>\> $\vdots$ \\
			\> addcc \> \%r4 + k, \%r4 \\
			\> ld \> \%r14, \%r5 \\
			\> addcc \> \%r14, -1, \%r14 \\
			\> st \> \%r5, [x]
		\end{tabbing}
		\end{center}
		\end{small}
		}
	}

	\item{Un {\bf desensamblador} es un programa que efect\'ua la funci\'on inversa al ensamblador,
		es decir, este lee un c\'odigo objeto y re-crea el c\'odigo en lenguaje ensamblador.
		Dado el siguiente c\'odigo objeto, desens\'amblelo en instrucciones del lenguaje de
		m\'aquina ARC.
		Como no hay suficiente informaci\'on en el c\'odigo objeto para determinar los nombre de los
		s\'{\i}mbolos, elija consecutivamente s\'{\i}mbolos del alfabeto $\{a, \ldots, z\}$.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			10000010 10000000 01100000 00000001 \\
			10000000 10010001 01000000 00000110 \\
			00000010 10000000 00000000 00000011 \\
			10001101 00110001 10100000 00001010 \\
			00010000 10111111 11111111 11111100 \\
			10000001 11000011 11100000 00000100
		\end{tabbing}
		\end{center}
		\end{small}
		}
	}
	
	\item{  \label{ej:pushpop}
		Cuando las macros \Prog{push} y \Prog{pop} son utilizadas, instrucciones innecesarias
		son insertadas cuando un \Prog{push} es seguido de manera inmediata por un \Prog{pop}.
		Expanda las macros e identifique que instrucciones resultan innecesarias.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			label: \= .macro \= \%r1,\%r2,\%r3 \kill
			\> .begin \\
			\> .macro \> push arg1 \\
			\> addcc \> \%r14, -4, \%r14 \\
			\> st \> arg1, \%r14 \\
			\> .endmacro \\
			\> .macro \> pop arg1\\
			\> ld \> \%r14, arg1 \\
			\> addcc \> \%r14, 4, \%r14 \\
			\> .endmacro \\
			\\
			! Comienzo del programa \\
			\> .org 2048 \\
			\> pop \> \%r1 \\
			\> push \> \%r2 \\
			\> $\vdots$ \\
			\> .end
		\end{tabbing}
		\end{center}
		\end{small}
		}
	}

	\item{\label{ej:simul}
		El programa ARCSim soporta un conjunto m\'as grande de instrucciones que las mostradas en el libro,
		como por ejemplo \Prog{nop}, \Prog{sra\{cc\}}, \Prog{halt} y \Prog{sub\{cc\}}.
		Aunque resulta m\'as c\'omodo tenerlas como parte de la ISA, estas pueden ser reemplazadas
		f\'acilmente por instrucciones equivalentes y gracias al mecanismo de expansi\'on de macros,
		podemos programar como si estas fueran parte de conjunto de instrucciones.
		\begin{enumerate}
			\item{Muestre 3 instrucciones de distinto opcode para reemplazar \Prog{nop}.}
			\item{De un conjunto de instrucciones que reemplacen \Prog{sub\{cc\}}.}
		\end{enumerate}
	}

	\item{\label{ej:mapDiv4}
		Modifique el programa de la figura 4-14 del libro para que en vez de obtener la suma de los
		elementos de un arreglo, efect\'ue la divisi\'on entera de cada elemento por 4, a la manera de
		un \Prog{map (/4)}.
		Los elementos del arreglo se consideran como enteros \underline{con signo}.
	}
	
	\item{\label{ej:mcd}
		Obtenga un programa en la ISA de ARC que calcule el $mcd(\Prog{\%r1},\Prog{\%r2})$, y que opere
		de manera similar al siguiente programa escrito en el lenguaje de los comandos guardados
		de Dijkstra:
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			......\= \kill
			\> $\{x=X \wedge y=Y\}$ \\
			\> {\bf do}\= \\
			\> \>	$\Box$ \= smtg. \kill
			\> \>	\> x>y $\rightarrow$ x:=x-y \\
			\> \>	$\Box$ \> y>x $\rightarrow$ y:=y-x \\
			\> {\bf od} \\
			\> $\{x=y=mcd(X,Y)\}$
		\end{tabbing}
		\end{center}
		\end{small}
		}
		El registro $\%r1$ mantendr\'a la variable $x$ y $\%r2$ la variable $y$.
		Utilice \Prog{subcc \%r1, \%r2, \%r0} y \Prog{subcc \%r2, \%r1, \%r0} para comparar los registros
		$\%r1$ y $\%r2$.
	}

	\item{\label{ej:mcdCall}
		Modifique el programa anterior introduciendo un bloque de entrada y otro de salida, de manera tal
		que podamos llamar a la subrutina \Prog{mcd} utilizando la convenci\'on de \emph{paso de par\'ametros
		en la pila}.
		
		Se busca que funcione el siguiente programa que hace uso de la rutina \Prog{mcd} e indica si dos
		n\'umeros almacenados en las posiciones de memoria $x$ e $y$ resultan coprimos.
		\Prog{
		\begin{small}
		\begin{center}
		\begin{tabbing}
			isCoprime: \= .begin \= \%r1,\%r2,\%r3 \kill
			\> !\%sp .equ \%r14  esta implicitamente definido\\
			\\
			\> .begin \\
			\> .org 2048 \\
			\> ld \> [x], \%r1 \\
			\> ld \> [y], \%r2 \\
			\> addcc \> \%sp, -4, \%sp \\
			\> st \> \%r1, \%sp !push del 1er argumento \\
			\> addcc \> \%sp, -4, \%sp \\
			\> st \> \%r2, \%sp !push del 2do argumento \\
			\> call \> mcd \\
			\> ld \> \%sp, \%r3 \\
			\> addcc \> \%sp, 4, \%sp !pop del resultado \\
			\> addcc \> \%r3, -1, \%r0 !\%r3=1?\\
			\> be \> isCoprime \\
			\> sethi 0, \%r3 \\
			\> ba cont \\
			isCoprime: \> sethi \> 0,\%r3 \\
			\> add \%r3, 1, \%r3 !el ser coprimo lo indico con \%r3=1 \\
			cont: \> !aqui continua el codigo \\
			\> \> $\vdots$ \\
			mcd: \> $\vdots$ \\
			\> !Bloque de entrada \\
			\> $\vdots$ \\
			\> !Codigo del ejercicio anterior \\
			\> $\vdots$ \\
			\> !Bloque de salida \\
			\> $\vdots$ \\
			\> \> $\vdots$ \\			
			x:\> 231 \\
			y:\> 22 \\
			\> .end
		\end{tabbing}
		\end{center}
		\end{small}
		}
		
		Puede resultar \'util tener a mano las definiciones de \Prog{push} y \Prog{pop} dadas en el ejercicio
		\ref{ej:pushpop}.
	}
	
	\item{?`La ISA de ARC obliga a que \Prog{\%r14} sea el puntero de la pila o esta es solamente una convenci\'on?
		Compare con la situaci\'on de \Prog{\%r15}.
	}


\end{enumerate}

\pagebreak

\section{ARCSim y ARCAssembler en el laboratorio}

En el laboratorio de computaci\'on est\'a instalado todo lo necesario para ejecutar el simulador.
S\'olo basta tener activo el XServer y tipear desde una ventana de comandos
\begin{center}\Prog{ARC}\end{center}

En \Prog{/usr/local/ARC} est\'a el archivo \Prog{ARCTools.jar} que contiene todas las clases de ARCSim y ARCAssembler
junto a varios archivos de documentaci\'on b\'asica y el directorio \Prog{examples/} que justamente contiene
ejemplos de c\'odigos fuentes \Prog{.asm}.

El archivo \Prog{ARC} es un shell script que simplemente llama al JRE con los par\'ametros adecuados y est\'a en
\Prog{/usr/local/bin}.

\smallskip

El objetivo de utilizar el simulador es doble, pues por un lado permiten comprobar los programas codificados
en los ejercicios, y por otra parte dan una idea m\'as acabada de la ISA de ARC.

\smallskip

Los ejercicios que pueden ser codificados de manera m\'as o menos directa son:
\ref{ej:swap}, \ref{ej:sum2array}, \ref{ej:simul}, \ref{ej:mapDiv4}, \ref{ej:mcd}
y especialmente el ejercicio \ref{ej:mcdCall}.

\smallskip

Con las instrucciones que da el programa, m\'as la informaci\'on traducida y compilada que est\'a disponible en la
p\'agina de la materia bastar\'{\i}a para que se puedan codificar los programas.
No obstante habr\'a un par de clases pr\'acticas en el laboratorio donde se podr\'a consultar acerca del manejo
de las ARCTools.

\end{document}











