\documentclass[12pt,a4paper]{book}
\usepackage[spanish]{babel}
\usepackage[latin1]{inputenc}
\usepackage[dvips]{epsfig}
\usepackage{latexsym,fancybox}
\usepackage{pifont}
\usepackage{graphics}
\usepackage{alltt}

\voffset=-0.7in
\hoffset=-1in
\textwidth=17.5cm
\textheight=24cm
\oddsidemargin 1.8cm
\evensidemargin 1.8cm
\headheight=16pt
\footskip=42pt
%\topmargin=0.5cm
\parskip=2mm


\begin{document}

\begin{center}
\Large
\bf {Fundamentos de Arquitectura de Ordenadores}
\bf {Ingeniería Técnica en Informática Sistemas}


\LARGE
\vspace{0.25cm}
%\Large
\textbf{PRÁCTICA IV \\
Procesador DLX. Camino de datos segmentado \\ }
\end{center}

\vspace{0.25cm}
\flushbottom
\addtolength{\parskip}{1ex}


\section*{Objetivos}


    \begin{itemize}
        \item Comprender  la terminología y los conceptos manejados en el
estudio de los computadores segmentados: dependencias de datos, de control,
tiempos de riesgos, adelantamiento, saltos retardados, etc.         
\item
Realizar programas en ensamblador del DLX y probar distintas técnicas de
planificación estática de instrucciones. 	

\item Comprobar cómo el
rendimiento obtenido por una determinada arquitectura segmentada tiene una
dependencia importante del código ejecutado, y cómo se puede optimizar el
rendimiento de una arquitectura dada modificando adecuadamente el software que
la utiliza.     
\end{itemize}


\section*{Introducci\'on}

Al ejecutar un programa, uno de los objetivos que generalmente
perseguimos es que dicho programa se ejecute lo mas r\'apidamente
posible, obteniendo el m\'aximo provecho del procesador, el m\'aximo
rendimiento. Para medir este rendimiento, son varios los par\'ametros
que podemos tener en cuenta:
        
\begin{itemize}

\item {\bf NC:} N\'umero de ciclos de reloj de CPU para ejecutar un
programa.

\item {\bf NI:} N\'umero de instrucciones de las que se compone el
programa.

\item {\bf TC:} Duraci\'on de un ciclo de reloj.

\item {\bf Tcpu=$NC*TC$:} Tiempo requerido en ejecutar un programa.

\item {\bf CPI=$NC/NI$:} N\'umero medio de ciclos por instrucci\'on.

\end{itemize}

De aqu\'{\i}, 
$$Tcpu=CPI*TC*NI$$ 

Si queremos hacer este tiempo lo m\'as peque\~no posible,
tendr\'{\i}amos que disminuir alguno de los tres factores (CPI, TC, NI).
No obstante, esta tarea no es tan simple, ya que los factores
interact\'uan mutuamente y cuando disminuye alguno de ellos los otros
aumentan. El ciclo de reloj depende de la tecnolog\'{\i}a usada en el
hardware, el CPI de la organizaci\'on y repertorio de las
instrucciones, y el NI de el repertorio de instrucciones y de la
tecnolog\'{\i}a del compilador.

La idea de segmentar la ejecuci\'on de las instrucciones pretende
acercar el valor de CPI a su valor m\'as pequeño posible (1), valor
ideal en el que todas las instrucciones tardan un ciclo de reloj.

En este tema nos centraremos en la simulaci\'on del procesador RISC
segmentado DLX, procesador que presenta un gran n\'umero de
similaridades con el procesador MIPS.


\section*{El procesador DLX}

A continuaci\'on resumimos las caracter\'{\i}sticas m\'as importantes
de la arquitectura del procesador DLX:

\begin{itemize}

\item {\bf Arquitectura de carga y almacenamiento}: s\'olo las
instrucciones del tipo load/store acceden a memoria (las instrucciones
de operaci\'on son s\'olo entre registros).
        
\item {\bf Unidades de operaciones aritm\'eticas separadas}: Una de
n\'umeros enteros y varias de punto flotante (suma, multiplicaci\'on y
divisi\'on).

\item {\bf Tama\~no de palabra de 32 bits} (1 word = 32 bits, 1 halfword = 16 bits).

\item {\bf 32 registros de prop\'osito general (GPR) de 32 bits para
enteros}.  Se denotan: R0,R1,R2,...,R31. El registro R0 siempre tiene
el valor 0.

\item {\bf 32 registros de n\'umeros en punto flotante} de simple
precisi\'on (32 bits), a los que se refiere como: F0,F1,...F31. Los
registros Fx se pueden agrupan en pares consecutivos para operaciones
de punto flotante en doble precisión (64 bits); a estos registros de
doble precisi\'on nos referiremos como D0,D1,...D30. (El registro Di
est\'a constitu\'{\i}do por los registros Fi+1:Fi).

\item {\bf Estructura segmentada}: La ejecuci\'on de una instrucci\'on
se divide en 5 etapas. Dichas etapas (pipeline) son las siguientes:

\begin{enumerate}

\item {\bf Etapa IF}: B\'usqueda de instruci\'on.

\item {\bf Etapa ID}: Decodificaci\'on de instrucci\'on.

\item {\bf Etapa EX}: Ejecuci\'on (operaci\'on o c\'alculo de
direcci\'on efectiva). Esta etapa puede realizarse en diferentes
unidades, seg\'un la instrucci\'on sea una operaci\'on de enteros
(intEX), o flotantes (y estos \'ultimos: suma, producto o divisi\'on,
denomin\'andose faddEX, fmulEX, fdivEX (las unidades fmulEX y fdivEX
tambi\'en realizan la multiplicaci\'on y divisi\'on de enteros).

\item {\bf Etapa MEM}: Carga o almacenamiento de datos en memoria.

\item {\bf Etapa WB} (write back): Almacenamiento de los resultados de
la instrucci\'on en los registros correspondientes. Se realiza en la
primera mitad del ciclo de reloj, de forma que una instrucci\'on que
simult\'aneamente est\'e en la etapa ID puede tomar el valor de los
registros en la segunda mitad del ciclo, sin necesidad de
cortocircuito (forwarding).

\end{enumerate}

Todas las etapas ocupan un ciclo de reloj, salvo las de ejecuci\'on de
punto flotante (faddEX, fmulEX, fdivEX) que tardan m\'as de un ciclo
en ser realizadas.

\item {\bf Conjunto reducido de instrucciones}. Dicho conjunto
contiene los siguientes 4 tipos de instrucciones:

\begin{itemize}

\item Transferencia de datos (carga, almacenamiento...).

\item Instrucciones aritm\'eticas y l\'ogicas sobre enteros.

\item Instrucciones de control.

\item Instrucciones de punto flotante.

\end{itemize}

\item {\bf Modos de direccionamiento} soportados:

\begin{itemize}

\item Inmediato. Ejemplo:

\hspace{2cm}{\tt addi r1,r0,\#1 ; r1=r0+1}

\item Directo a memoria. Ejemplo:

\hspace{2cm}{\tt lb r1,0x10  ; r1=[0x10]}
 
\hspace{2cm}{\tt lb r1,label ; r1=[label]}

Los n\'umeros en hexadecimal se expresan como {\tt 0xN}.

\item Indirecto: Se expresa como {\tt c(Rx)}, donde {\tt c} es un
desplazamiento de 16 bits y {\tt Rx} es un registro que contiene una
direcci\'on de memoria. Ejemplo:
 
\hspace{2cm}{\tt addi r1,r0,label ; r1=label (direcci\'on de memoria)}

\hspace{2cm}{\tt lb r2,8(r1)      ; r2=[label+8]}

\end{itemize}

Para mayor detalle acerca de las instrucciones es conveniente
consultar el contenido de la ayuda del programa simulador.

\end{itemize}

\section*{Riesgos en la segmentaci\'on}

Aunque hemos pensado en la segmentaci\'on como un m\'etodo para
mejorar la eficiencia del procesador, la aparici\'on de dependencias
entre las instrucciones limita dicha mejora. La dependencia entre
instrucciones provoca que la instrucci\'on que sucede a aquella con la
cual posee dependencias, no pueda ejecutarse en el ciclo de reloj que
le corresponde, ya que ha de esperar alg\'un resultado para poder
efectuar su ejecuci\'on.  Denominamos riesgo ({\em hazard}) a esta
situaci\'on que impide a una instrucci\'on la ejecuci\'on de sus
etapas al depender de otra anterior. Los riesgos se traducen en una
parada ({\em stall}) en el flujo del {\it pipeline}.

La causa de los riesgos puede ser variada. Los que podemos encontrar
en el procesador DLX son los siguientes:

\begin{enumerate}

\item Riesgos de datos: son aquellos en los que una instrucci\'on
necesita de un resultado obtenido en una instrucci\'on previa. Podemos
distinguir:

\begin{itemize}
\item {\bf Riesgo RAW} (read after write): una instrucci\'n intenta leer
un valor calculado en una instrucci\'on previa. Por ejemplo:

\hspace{2cm}{\tt add r3,r2,r1 ; r3=r2+r1}

\hspace{2cm}{\tt add r4,r3,r3 ; r4=r3+r3}

\item {\bf Riesgo WAW} (write after write): una instrucci\'on intenta
escribir un operando antes que una instrucci\'on previa que tambi\'en
lo modifica. Este riesgo deriva en las instrucciones de punto flotante
ya que su ejecuci\'on tarda un n\'umero de ciclos de reloj mayor al
resto de instrucciones. En este tipo de instrucciones multiciclo
pueden terminar instrucciones en un orden diferente al que se
emitieron, por ejemplo en la siguiente secuencia la segunda
instrucci\'on es m\'as r\'apida que la primera e intenta escribir f2
antes cuando no deber\'{\i}a de ser as\'{\i}.

\hspace{2cm}{\tt multf f2,f1,f0 ; f2=f1*f0}

\hspace{2cm}{\tt movf f2,f0     ; f2=f0}

\end{itemize}
              
\item Riesgos estructurales: derivan de la imposibilidad del hardware
en realizar a la vez dos actividades. As\'{\i}, si tenemos solamente
una unidad para multiplicar flotantes, mientras que se realiza una
multiplicaci\'on es imposible realizar otra. En el siguiente ejemplo,
la segunda instrucci\'on ha de esperar a que la primera acabe la
multiplicaci\'on para poder efectuar su multiplicaci\'on. Por ejemplo:
 
\hspace{2cm}{\tt multf f4,f1,f0  ; como ocupa mas de un ciclo}

\hspace{2cm}{\tt multf f5,f2,f0  ; la unidad fmulEX esta ocupada}

\item Riesgos de control: en aquellas instrucciones en las que se
modifica el contador del programa (PC), como saltos, llamadas a
subrutinas, interrupciones .... En DLX, a diferencia de MIPS, la
direcci\'on de salto es conocida en la etapa ID, con lo que la
cancelaci\'on de la siguiente instrucci\'on en caso de fallo es menos
costosa.

\end{enumerate}

Como se ha dicho, los riesgos se traducen en una parada (stall) en el
flujo de las instrucciones dentro de la etapas de la segmentaci\'on, a
la espera de que la dependencia causante se resuelva.

La forma m\'as intuitiva de visualizar estos conceptos es la
representaci\'on de un cronograma en el que representamos la
evoluci\'on del tiempo en el eje horizontal y las diferentes
instrucciones el eje vertical. El simulador winDLX, permite la
visualizaci\'on de dicho cronograma.

En el cronograma nos pueden aparecer diferentes tipos de paradas: 

\begin{itemize}

\item {\bf R-Stall}: causada por un riesgo RAW.

\item {\bf W-Stall}: causada por un riesgo WAW.

\item {\bf S-Stall}: causada por un riesgo estructural.

\item {\bf T-Stall}: causada por una interrupci\'on (denominada
excepci\'on o {\it TRAP}). Espera a que se ejecute por completo la
instrucci\'on anterior.

\item {\bf Stall}: causada por una parada de una instrucci\'on
anterior.

\end{itemize}

Las dependencias RAW y WAW se muestran mediante una flecha roja.

Para paliar la posibilidad de riesgos, se introduce una mejora en la
segmentaci\'on, que se denomina anticipaci\'on ({\em forwarding} o
{\em short-circuit}). Dicha mejora consiste en facilitar el operando
que produce la dependencia a la siguiente instrucci\'on, en la etapa
en que est\'a disponible, sin esperar a que se llegue en la \'ultima
etapa cuando es escrito en los registros. As\'{\i} logramos una mayor
eficiencia. El simulador WinDLX permite habilitar o deshabilitar la
opci\'on de {\it forwarding}. En caso de que est\'e activa, una flecha
verde muestra las etapas a trav\'es de las cuales se anticipa el valor
del operando. Por ejemplo en las instrucciones:

\hspace{2cm}{\tt add r3,r2,r1 ; r3=r2+r1}

\hspace{2cm}{\tt add r4,r3,r3 ; r4=r3+r3}

\noindent el valor de {\tt r3} est\'a disponible en la ALU a la salida de la
etapa de ejecuci\'on (EX), con lo cual se puede pasar directamente a
entrada de la etapa de ejecuci\'on (EX) de la siguiente instrucci\'on
sin necesidad de esperar a que sea guardado en {\tt r3} (etapa WB).

%\newpage 

\section*{Ejemplo}

En este apartado se presenta un peque\~no c\'odigo ensamblador para
DLX y se explica el proceso a seguir para su simulaci\'on con el
simulador WINDLX.

El c\'odigo ensamblador se carga desde la opci\'on {\it FILE}. Primero se
selecciona el nombre del archivo (*.s) ({\it SELECT}) y luego se carga
({\it LOAD}). Con ello cargamos en la memoria simulada el c\'odigo. Desde la
opci\'on {\it FILE} podemos hacer un reset, bien del procesador (sin borrar
la memoria) o de todo el sistema (incluyendo la memoria, borr\'andose por tanto
el programa cargado).  Como ejemplo cargaremos el siguiente c\'odigo:
%{\small
\begin{verbatim}

                .data 0
                ;comienzo de los datos
                .global dato1
dato1:          .word 1, 6
                .global dato2
dato2:          .float  17.0, 26.0 
		
                .text 0x100
                ;comienzo del codigo
                .global start

start:          addi    r8,r0,#12       ; inicializa r8 a 12
                addi    r6,r0,#8        ; inizializa r6 a 8
                add     r10,r0,r0       ; inizializa r10 a 0
                lw      r1,0(r10)       ; r1 <- [r10]=[0]=1
                addi    r3,r1,#2        ; inizializa r3 a 2

lazo1:          add     r2,r3,r0
                subi    r3,r3,#1
                bnez    r3,lazo1        ; saltar si r3 no es cero
                add     r3,r3,r0
                addi    r11,r0,#4
                lw      r3,0(r11)       ; r3 <- [r11]=[4]=6
                addi    r1,r3,#4
                add     r4,r0,r0
                addi    r5,r0,#7

                lf      f3,0(r8)        ; f3 <- [r8]=[12]=26.0
                lf      f2,0(r6)        ; f2 <- [r6]=[8]=17.0
                multf   f4,f3,f2
                divf    f5,f4,f2
                addf    f5,f3,f2
                sf      0(r8),f5        ; Mem[r8]=Mem[12] <- f5
                j       fin             ; saltar al final del prog. 
                nop
                nop
                nop
fin:            trap 0                  ; finalizar el programa 

\end{verbatim}
%}
%\normalsize

El c\'odigo ({\tt ejemplo.s}) consta de dos partes: datos y c\'odigo. Las
l\'{\i}neas que comienzan con un punto (p.e. {\tt .data 0}) son {\it directivas}. La parte de
datos empieza en la direcci\'on 0, y se define con la directiva {\tt
.data 0x0}. La parte de c\'odigo empieza en la direcci\'on 0x100, y se
indica con la directiva {\tt .text 0x100}.  Para que el simulador
funcione correctamente hemos de inicializar estas posiciones (comienzo
de los datos y c\'odigo). Para ello en la opci\'on {\it MEMORY SYMBOLS}
del simulador (donde se muestran los valores de las etiquetas), hemos
de cambiar los valores de las etiquetas {\it TEXT} y {\it DATA}, a los valores
0x100 y 0x0 respectivamente. De esta forma indicamos al simulador
donde comienzan los datos y la primera l\'{\i}nea ejecutable.

La \'ultima l\'{\i}nea del programa es una llamada a la interrupci\'on 
(excepci\'on 0) que finaliza la ejecuci\'on del programa.

En la opci\'on {\it CONFIGURATION} debemos de asegurarnos que la
configuraci\'on de punto flotante ({\it FLOAT POINT STAGES}) est\'a puesta a
los siguientes valores (aconsejados, no obligatorio):

\begin{verbatim}
                               count           delay
 addition units                  1                2
 multiplication units            1                5
 division units                  1               19
\end{verbatim}

\noindent (con esto decimos el n\'umero de unidades de punto flotante y el
n\'umero de ciclos necesarios para la ejecuci\'on de estas etapas). En
{\it MEMORY SIZE} nos aseguraremos que la memoria tiene un tama\~no de
0x8000 bytes.

En la opci\'on {\it CONFIGURATION} tambi\'en habilitamos o deshabilitamos
la anticipaci\'on con {\it ENABLE FORWARDING}.

El manejo del simulador es bastante intuitivo, constando de diferentes
ventanas en las que se muestra: el cronograma de ejecuci\'on, el
c\'odigo cargado, contenido de los registros, estado del pipeline,
puntos de ruptura y estad\'{\i}sticas de ejecuci\'on. Es posible
tambi\'en ver el contenido de la memoria en la opci\'on {\it DISPLAY} de
{\it MEMORY}.

Para la ejecuci\'on del programa, dentro de la opci\'on {\it EXECUTE},
podemos ejecutar el c\'odigo en su totalidad ({\it RUN\/}), ejecutar un
n\'umero de ciclos ({\it MULTIPLE CYCLES}), ejecutar hasta una posici\'on
dada ({\it RUN TO}), o ejecutar un s\'olo ciclo de reloj ({\it SINGLE CYCLE}).
Cuando se ejecuten varios ciclos de reloj de una vez, se debe tener en cuenta
que el simulador solo conserva los \'ultimos, por lo que, si se ejecutan muchos
de una vez, puede que se pierda la informaci\'on de los primeros. 

\clearpage
\section*{Ejercicio 1}

\begin{enumerate} 

\item Ejecutar el c\'odigo ({\tt ejemplo.s}) en el simulador DLX.
Explica en pocas palabras que es lo que hace el c\'odigo.
¿Funciona correctamente o deben introducirse algunas
operaciones {\tt nop}?

\vspace{3cm}

\item Realizar la ejecución completa del código y calcular el
número de ciclos que consume en el caso de que la anticipación esté
activada y en el caso de que no lo esté. Calcular el CPI en ambos
casos.

\begin{center}
\begin{tabular}{|c|c|c|}\hline
  & Activada & No activada \\ \hline
Ciclos & & \\ \hline
CPI & & \\ \hline
\end{tabular}  
\end{center}

\item Con la anticipación (\textit{forwarding}) activa, ¿qué
tipos de riesgos existen en el programa? 

\begin{center}
\begin{tabular}{|c|c|c|c|}\hline
  Riegos: & Estructurales & Control & Datos \\\hline
  N\'umero: & & & \\\hline
\end{tabular}
\end{center}

\item En el caso de que sean dependencias de datos, ¿Cuáles son los
registros causantes y de qu\'e tipo son estas dependencias?

\begin{itemize}
    \item[RAW:]
    \item[WAW:]
\end{itemize}

\item ¿Que tipo de estrategia se emplea para los saltos?
(anticipación, anulación, etc.) ¿Cómo aparece reflejado en el diagrama
de tiempos?

\vspace{2cm}

\item Analizar los cortocircuitos implementados (entre qu\'e etapas se
dan).

\vspace{2cm}

\item ¿Es posible reducir el número de ciclos empleados en la
ejecución del código mediante una reordenación del mismo? En caso
afirmativo indicar cómo quedaría el nuevo código y calcular el nuevo
número de ciclos empleados en la ejecución y el CPI resultante.

Marca en el codigo original las modificaciones que crees necesarias:


%\small
\begin{verbatim}
                .text 0x100
                ;comienzo del codigo
                .global start

start:          addi    r8,r0,#12
                addi    r6,r0,#8 
                add     r10,r0,r0
                lw      r1,0(r10)
                addi    r3,r1,#2 

lazo1:          add     r2,r3,r0
                subi    r3,r3,#1
                bnez    r3,lazo1
                add     r3,r3,r0
                addi    r11,r0,#4
                lw      r3,0(r11)
                addi    r1,r3,#4
                add     r4,r0,r0
                addi    r5,r0,#7
                                   
                lf      f3,0(r8)   
                lf      f2,0(r6)   
                multf   f4,f3,f2
                divf    f5,f4,f2
                addf    f5,f3,f2
                sf      0(r8),f5
                j       fin     
                nop
                nop
                nop
fin:            trap 0

\end{verbatim}

CPI resultante: \framebox[2cm]{$\phantom{A^c}$}
%\normalsize

\end{enumerate}

\clearpage
\section*{Ejercicio 2}


Cargue el siguiente código ensamblador en el simulador WinDLX, prepare
el simulador para su ejecución y responda a las cuestiones:

%\small
\begin{verbatim}

        .data 0x0
        ;comienzo de los datos
        .global a
a:      .float 3.1416
        .global b
b:      .float 2.1727
        .global x
x:      .float 1,2,3
        .global xtop
xtop:   .float 4

        .text 0x100
        ;comienzo del codigo
start:  add r3,r0,r0
        addi r2,r0,#4
        addi r1,r0,xtop
        lf f2,a
        lf f6,b
loop:   add r3,r3,r2
        sub r2,r2,#1
        lf f0,0(r1)     
        multf f4,f0,f2
        addf f4,f4,f6
        sf 0(r1),f4
        sub r1,r1,#4
        bnez r1,loop
end:    nop            
        trap #0     
    
\end{verbatim}
%\normalsize

\begin{enumerate}

      \item Realice la ejecución completa del código y calcular el
número de ciclos que consume en el caso de que la anticipación esté
activada y no lo esté. Calcule el CPI
($\frac{Ciclos\_consumidos}{instrucciones\_ejecutadas}$) en ambos casos.
\vspace{12ex}


      \item Con la anticipación ('forwarding') activa, ¿qué tipo de
riesgos se dan hasta que la instruccion {\tt sf} se ejecuta
completamente por primera vez? En el caso de que sean de datos,
¿Cuáles son los registros causantes de las dependencias?
\vspace{12ex}


      \item ¿Existe algún riesgo estructural (S-Stall) en 
la ejecución?. ¿Por qué?
\vspace{8ex}

      \item ¿En qué etapa (del 'pipeline') de la instrucción de
control {\tt bnez} se conoce la dirección del salto? ¿Qué ocurre
con la siguiente instrucción que sigue en memoria al salto? 
\vspace{10ex}

      \item ¿Entre qué etapas (del 'pipeline') se produce la
aticipación desde la instrucción {\tt lf f0,0(r1) } y la siguiente?
\vspace{8ex}

      \item Configure la etapa de punto flotante de forma que el
tiempo en ejecutar la multiplicación (fmulEX) sea el mismo que el de
las suma (faddEX) (5 unidades de reloj). ¿Qué tipo de riesgo se
elimina con esta modificación en la arquitectura del procesador?
\vspace{10ex}

      \item Proponer modificaciones (reordenación, adición de 'nop's
...) que puedan mejorar el rendimiento en este código.

\end{enumerate}
\end{document}
