\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}