ARQUITECTURA DE COMPUTADORES I EXAMEN DE FEBRERO DE 2007 1. (2 puntos) Considere que el fragmento de código siguiente:

(1) lf f3, 0(r1) (2) lf f2, 8(r1) (3) addf f4, f2, f3 (4) sf 16(r1), f4 (5) lf f5, 16(r2) (6) addf f6, f5, f2

(7) multf f6, f6, f4 (8) sf 8(r2), f6 (9) addi r3, r2, #32 (10) lf f7, 0(r3) (11) multf f8, f7, f3 (12) sf 0(r3), f8

se ejecuta en un procesador superescalar que es capaz de captar (IF), decodificar/emitir (ID/ISS) y finalizar (WB) 4 instrucciones/ciclo. El procesador utiliza un ROB para realizar el renombramiento y la finalización ordenada y dispone de tres estaciones de reserva de 3 líneas cada una (una para las instrucciones de acceso a memoria, otra para las operaciones de coma flotante, y otra para las operaciones con enteros). Las estaciones de reserva pueden enviar una instrucción por ciclo a cada una de las unidades funcionales conectadas a ellas (la velocidad de envío depende, por tanto, del número de unidades que estén conectadas a cada estación). El procesador permite los adelantamientos de stores por loads no especulativos, pero no permite los especulativos.

(a) Indique el número de ciclos que tardaría en ejecutarse el conjunto de instrucciones anterior suponiendo envío desordenado desde las estaciones de reserva a las unidades funcionales.

(b) ¿Y si el envío fuera ordenado desde las estaciones de reserva para operaciones con enteros y operaciones con datos en coma flotante, pero desordenado para la estación de acceso a memoria?

NOTA: Considere que, conectadas a la estación de reserva para el acceso a memoria, tiene una unidad funcional de carga con un retardo de dos ciclos y una de almacenamiento con retardo de un ciclo; conectadas a la estación de reserva para enteros tiene dos ALUs con retardo de un ciclo; y, conectadas a la estación de reserva para coma flotante tiene una unidad de multiplicación con cinco ciclos de retardo y dos unidades de suma con dos ciclos de retardo. No hay límite en el número de líneas de la cola de instrucciones y del ROB).

2. (2 Puntos) Considere que el siguiente bucle: for i=1 to N do X[i] = a*Y[i]; X[i], Y[i] y a son números en coma flotante Se ejecuta en un procesador vectorial de 32 bits que dispone de una única unidad para acceder a los datos de memoria. Los tiempos de latencia de inicio para los cauces son TLI(LV)=5 ciclos, TLI(MULTSV)=10 ciclos, y TLI(SV)=5 ciclos, y los registros vectoriales tienen 64 componentes (MVL=64). Se tiene que TBASE=15 ciclos, TBUCLE=10 ciclos, y la frecuencia del procesador es igual a 1 GHz

(a) ¿Cuál es el valor de R∞? (b) ¿Cuál sería el código escalar para una arquitectura LOAD/STORE que implemente la secuencia de

instrucciones vectoriales anterior? (c) Suponga que el código escalar se ejecuta en un procesador superescalar de 32 bits a 1 GHz que

puede terminar un promedio de instrucciones por ciclo tal que el tiempo de ejecución está limitado por el tiempo de acceso a los datos. El computador tiene una memoria caché interna para datos y otra para instrucciones de 64 KBytes cada una, líneas de 32 Bytes, mapeo directo, política de actualización de post-escritura (write-back), con asignación de caché en escritura (write-allocate), y tiempo de acceso de un ciclo de reloj de CPU. La memoria principal de 512 MBytes tiene un tiempo de acceso de 50 ns y se conecta a través de un bus de 64 bits a 100 MHz que utiliza ciclos burst 5-1-1-1 para transferir las líneas de caché. Si el array que se multiplica por el escalar tiene N=1024 elementos, ¿se ejecuta antes en el procesador vectorial o en el superescalar?

NOTA: Considere la situación más favorable respecto a la ubicación de los arrays en memoria principal y su correspondencia en caché.

3. (2 Puntos) El siguiente fragmento de código forma parte de una rutina que se ejecuta muy a menudo en cierto procesador VLIW:

mult r1, r2, r3 add r4, r5, r1 beqz r4, cero lw r6, dato add r7, r4, r6 mult r2, r1, r7 cero: sub r8, r1, r4 mult r1, r8, r2 sw resul, r1

La arquitectura VLIW tiene dos slots, pero las instrucciones de comparación sólo pueden colocarse en el primero de ellos. Las latencias de las operaciones son de 1 ciclo para las sumas, restas y comparaciones, de dos ciclos para las multiplicaciones y de cinco ciclos para las cargas de memoria. Debido a esta alta latencia en el acceso a memoria, la arquitectura incorpora una instrucción de carga especulativa de memoria (lw.s rx, desp[ry], repar) que permite cargar un dato anticipadamente. Para dar soporte a esta instrucción, los registros del procesador cuentan con un bit de veneno adicional para marcar aquellos resultados en los que la especulación haya provocado una excepción. La aplicación de cualquier operación con un operando envenenado provocará que se envenene el resultado, y la excepción sólo se atenderá si se intenta almacenar un resultado envenenado. En dicho caso, tras atender la excepción se ejecutará el código de reparación indicado con el puntero repar. Por otra parte, todas las instrucciones pueden predicarse y existen instrucciones de la forma (p) p1[,p2] cmp.cnd x,y donde cnd es la condición que se comprueba entre x e y (lt, ge, eq, ne,…). Si la condición es verdadera p1=1 (y p2=0), y si es falsa, p1=0 (y p2=1). La instrucción sólo se ejecuta si el predicado p=1. Optimice el código anterior de manera que no aparezca ninguna instrucción de salto, se tengan en cuenta las latencias de las operaciones y los slots a los que se pueden emitir, y se adelante la instrucción de carga especulativamente todo lo que sea posible para tratar de ocultar su latencia. 4. (2 puntos) Considere un procesador con arquitectura DLX que implementa un cauce segmentado en cinco etapas (IF, ID, EX, MEM, WB). Para los números en coma flotante se añaden además un sumador con una latencia de 2 ciclos y un multiplicador con una latencia de 3 ciclos. Existen caminos de bypass desde la salida de las unidades de ejecución y desde la etapa de memoria a las entradas de la ALU. Las instrucciones de salto se procesan en la etapa de decodificación, por lo que la nueva dirección a la que se ha de acceder si se produce el salto estará disponible al final de dicha etapa. Se implementa salto retardado en el que no se anula nunca la siguiente instrucción que se haya podido introducir en el cauce tras un salto (el salto se resuelve en la etapa de decodificación). Considerando el código siguiente:

add r1, r0, r0 ; Inicializamos el índice i a 0 subd f0, f0, f0 ; Inicializamos el acumulador a 0 bucle: ld f2, X(r1) ; Cargamos X(i) multd f6, f2, f4 ; Multiplicamos X(i) por a (en f4) addd f0, f0, f6 ; Acumulamos el resultado addi r1, r1, #8 ; Incrementamos el contador del índice subi r3, r3, #8 ; Comprobamos si hemos acabado bnez r3, bucle ; Saltamos si quedan elementos sd R, f0 ; Guardamos el resultado

(a) ¿Se ejecutaría el programa correctamente tal y como está? ¿Qué cambios haría para aprovechar el

salto retardado? (b) ¿Cuál es la productividad del cauce en función del número de iteraciones N?

Solución al Problema 1: Suponiendo un envío desordenado para todas las estaciones de reserva, el código tardaría 28 ciclos en ejecutarse, tal y como se muestra en el siguiente diagrama:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 (1) lf f3, 0(r1) IF ID EX EX ROB WB (2) lf f2, 8(r1) IF ID X X EX EX ROB WB (3) addf f4, f2, f3 IF ID EX EX ROB WB (4) sf 16(r1), f4 IF ID EX WB (5) lf f5, 16(r2) IF ID EX EX ROB WB (6) addf f6, f5, f2 IF ID EX EX ROB WB (7) multf f6, f6, f4 IF ID EX EX EX EX EX ROB WB (8) sf 8(r2), f6 IF X X ID EX WB (9) addi r3, r2, #32 IF X ID EX ROB WB (10) lf f7, 0(r3) IF X X X X X ID EX EX ROB WB (11) multf f8, f7, f3 IF X X X X X ID EX EX EX EX EX ROB WB (12) sf 0(r3), f8 IF X X X X X X ID EX WB

En el enunciado se especifica que las cargas podrán adelantar a los almacenamientos siempre que no sean especulativas, es decir cuando se sepa que va a acceder a direcciones de memoria diferentes. Las instrucciones (5) y (4), acceden a memoria con el mismo desplazamiento y dos registros índice diferentes (r2 y r1), con lo que si r2 tuviera un valor diferente al de r1, la instrucción (5) podría adelantar a la (4). Como no sabemos los valores de estos registros, se ha supuesto el peor caso, que es la coincidencia de r1 y r2, lo que obliga a que la instrucción (5) tenga que esperar a la (4). Por otro lado, las instrucciones (10) y (8) acceden a posiciones de memoria diferentes, ya que la instrucción (8) almacena en la posición 8+r2 y la instrucción (10) lee de la posición 0+r3 = 32+r2. Como suponemos que las direcciones efectivas se calculan en el primer ciclo de la etapa de ejecución de las instrucciones de acceso a memoria, aunque las direcciones finales sean diferentes, este hecho no se puede comprobar por la lógica de envío de la estación de reserva, lo que obliga a enviar primero el almacenamiento y luego la carga. Estas dos dependencias están marcadas en el diagrama mediante flechas de color amarillo. Las colisiones que se producen en el cauce están marcadas con el símbolo X. Estas colisiones pueden ser bien en las estaciones de reserva o en las unidades de ejecución. Como las estaciones de reserva tienen sólo tres entradas cada una, cuando alguna se llena no permite que se puedan emitir más instrucciones hacia ella hasta que envíe alguna instrucción y deje algún hueco. Este fenómeno se puede apreciar en la instrucción (8), que no puede entrar hasta que se envía la instrucción (2) y se quedan en la estación de reserva las instrucciones (4) y (5). También se crea un cuello de botella en la estación de reserva de acceso a memoria con la instrucción (10), que no puede emitirse hasta que se envía la instrucción (4), y que retrasa la emisión de la instrucción (11), ya que la emisión es ordenada. Por último, la instrucción (12) se bloqueará en la cola de instrucciones hasta que se envíe a ejecutar la instrucción (5). En cuanto a las colisiones en las unidades de ejecución, la instrucción (2) debe esperar a que la (1) libere la unidad de carga, y lo mismo ocurre entre las instrucciones (11) y (7) por el multiplicador y entre las instrucciones (10) y (5) al acceder a memoria. Por último, los riesgos de datos adelantados por los caminos de bypass están marcados mediante flechas negras en el diagrama. En el caso de que el envío fuese desordenado sólo para la estación de reserva de acceso a memoria, el resultado sería exactamente el mismo, ya que debido a los riesgos del programa, todas las instrucciones se han enviado ordenadamente.

Solución al Problema 2: Dado que el tamaño de los registros vectoriales del procesador propuesto en el problema es MVL = 64 y que el vector que deseamos procesar tiene un tamaño N que no está definido, tendremos que aplicar la técnica de strip-mining para trocear el vector y procesarlo iterativamente. El compilador realizará un cambio al código similar a este:

Al traducir este código a ensamblador, el bucle que se encuentra sombreado se cambiará por instrucciones vectoriales y el resto de instrucciones permanecerán tal y como están. Dado que R∞ se define como

kkkk T

RR frecuenciaes vectorialsoperacioneklimlim ××==

∞→∞→∞

el primer paso consistirá en estimar el tiempo Tk. Para ello, debemos determinar las instrucciones vectoriales que se ejecutarán dentro del bucle interno y la forma en que se solaparán y encadenarán. Dichas instrucciones serán la carga vectorial de Y, una multiplicación, y un almacenamiento del resultado en X. El diagrama de tiempos de estas instrucciones es el siguiente:

Como sólo tenemos una unidad de carga/almacenamiento, la instrucción SV debe esperar a que termine la instrucción LV, por tanto, tenemos que el tiempo por componente es TPC = 2 y que el tiempo de latencia inicial TLI = 5 + 5 = 10, ya que la multiplicación ha quedado solapada con las instrucciones de carga y de almacenamiento. Con estos valores de TLI y TPC y con los valores de TBASE y TBUCLE que nos dan en el enunciado del problema, podemos calcular Tk como:

( ) ( ) ciclos ·2101064

51TPCTLIMLV BUCLEBASE kkkTkTTk ++⎥⎥

⎤⎢⎢⎡+=⋅++⎥⎥

⎤⎢⎢⎡+=

Una vez obtenido Tk, obtenemos R∞:

( )MFLOPS 43,432

·2101064

51

00101limfrecuencia vecopslimlim =++⎥⎥

⎤⎢⎢⎡+

××=

××==

→∞→∞→∞∞

kkk

TkRR

kk

kkk

Si se desea implementar el fragmento de código del enunciado en un procesador escalar, el código podría ser así:

low = 1; VL = (n mod MVL); /* resto de la division */ for ( j = 0 ; j <= (n / MVL) ; j++) { for ( i = low ; i < low + VL ; i++) X(i):= a*Y(i); low += VL; VL = MVL; }

5 64 64 5

LV VY, RY

MULTSV VX, a, VY

SV RX, VX

10

5

5

lf f0, a ; Cargamos la constante a add r1, r0, r0 ; Inicializamos el índice i=0 lw r2, N ; Tamaño del vector en elementos slli r2, r2, #2 ; Multiplicamos por 4 para obtener el tamaño del vector en ; bytes. Cada elemento ocupa 32 bits (4 bytes) bucle: lf f2, Y(r1) ; Cargamos X(i) multf f4, f0, f2 ; Multiplicamos Y(i) por a sf X(r1), f4 ; Guardamos el resultado addi r1, r1, #4 ; Pasamos al siguiente elemento sub r3, r1, r2 ; Comprobamos si hemos acabado bnez r3, bucle ; Saltamos si quedan elementos En el enunciado se afirma que el tiempo de ejecución de este fragmento de código está limitado por el tiempo que se tarda en acceder a los datos. Este tiempo dependerá de la ubicación de los datos en la memoria principal. Como se nos indica que consideremos la ubicación más favorable, asumiremos que el primer dato de cada vector está alineado a una frontera de 32 Bytes, de forma que se ocupen el menor número de líneas, y que los vectores X e Y están almacenados en posiciones de memoria tales que la correspondencia directa de la memoria cache los llevará a líneas diferentes. De esta forma sólo se producirán fallos de cache cada vez que se acceda a una línea diferente de la cache de datos. Como el procesador es de 32 bits, asumimos que cada elemento del vector ocupa 4 Bytes, por tanto, si cada vector tiene N = 1024 elementos, ocupará 4 KB de memoria. La ubicación que hemos supuesto más arriba implica que sólo se cometerá un fallo de cache cuando se intente leer o escribir un dato de una línea que no haya sido llevada a cache, con lo que el número de fallos a la cache de datos en el acceso a un vector se puede calcular como:

128B 32

KB 4línea de Tamaño

vectordel Tamañovector ===f

Además de para leer los elementos del vector Y, como la cache realiza asignación en escritura (write-allocate), cada vez que se intente escribir un elemento de X y no esté en cache se traerá una línea de elementos de X. Por último, también hay que cargar las variables a y N, que supondremos que están las dos en otro línea de cache, lo que añadirá un fallo más a los fallos que se produzcan en la manipulación de los vectores. Por tanto, el total de fallos de la cache de datos es de:

25712 vectortotales =+×= ff Se accede a los 1024 elementos de cada vector más a las variables a y N, por lo que el número total de accesos a datos es:

2050210242totales =+×=a Por tanto, las tasas de fallos y aciertos se pueden calcular como:

125,02050257

totales

totalesfallos ===

aft 875,01 fallosaciertos =−= tt

Suponiendo que se tarda 1 ciclo de CPU en acceder a la cache, el tiempo medio de acceso a un dato es:

( ) ( ) ( ) ( ) ns 7,25501875,011875,01 memoriacacheaciertoscacheaciertosacceso =+×−+×=+×−+×= TTtTtT Por lo que el tiempo total de acceso a datos sería, o lo que es lo mismo, el tiempo de ejecución del programa en el procesador superescalar es de:

ns 14862,5205025,7totalesaccesomemoria =×=×= aTT El tiempo de ejecución en el procesador vectorial es de:

( ) ns 238310242101064

1024511024 =×++⎥⎥⎤

⎢⎢⎡+=T

Con lo que se puede concluir que el programa tardaducho más en el procesador superescalar debido al tiempo que se tarda en acceder a los datos.

Solución al Problema 3: Lo primero que vamos a hacer es escribir el programa usando predicados:

mult r1, r2, r3 add r4, r5, r1 p1 cmp.ne r4, r0 (p1) lw r6, dato (p1) add r7, r4, r6 (p1) mult r2, r1, r7 sub r8, r1, r4 mult r1, r8, r2 sw resul, r1

Si empaquetamos estas instrucciones en instrucciones VLIW para el procesador descrito en el enunciado, respetando los tipos de instrucciones que se pueden emitir en cada slot y las latencias de las instrucciones, comprobamos que el programa tarda en ejecutarse 15 ciclos, de los cuales el procesador está cuatro ocioso debido a la alta latencia de la carga de memoria:

Ciclo Slot 1 Slot 2 1 mult r1, r2, r3 2 3 add r4, r5, r1 4 p1 cmp.ne r4, r0 sub r8, r1, r4 5 (p1) lw r6, dato 6 7 8 9

10 (p1) add r7, r4, r6 11 (p1) mult r2, r1, r7 12 13 mult r1, r8, r2 14 15 sw resul, r1

Sería interesante que la carga se realizara al principio del programa para tratar de ocultar esta latencia. Como está vigilada por p1, se debe hacer especulativamente para ignorar las posibles excepciones que puedan ocurrir en su procesamiento, ya que si al calcular r4 toma el valor 0, la carga no debería haberse realizado y por tanto, no debería haber ocurrido ninguna excepción. El código para adelantar la carga es el siguiente:

lw.s r6, dato, repar mult r1, r2, r3 add r4, r5, r1 p1 cmp.ne r4, r0 (p1) add r7, r4, r6 (p1) mult r2, r1, r7 sub r8, r1, r4

mult r1, r8, r2 sw resul, r1

Y una vez colocado en forma de instrucciones VLIW, podemos comprobar que tarda 4 ciclos menos en ejecutarse, siempre que no falle la carga especulativa, o que no se use el valor envenenado en caso de que falle (si p1 toma el valor 0):

Ciclo Slot 1 Slot 2 1 mult r1, r2, r3 lw.s r6, dato, repar 2 3 add r4, r5, r1 4 p1 cmp.ne r4, r0 sub r8, r1, r4 5 6 (p1) add r7, r4, r6 7 (p1) mult r2, r1, r7 8 9 mult r1, r8, r2

10 11 sw resul, r1

Sin embargo, si la carga especulativa falla y además p1 toma el valor 1 en la comparación, r6 envenenaría a r7, r7 a r2, y r2 a r1, por lo que al ejecutarse la instrucción de almacenamiento se intentaría almacenar un resultado envenenado, permitiendo detectar al procesador que se produjo una excepción en la carga especulativa. En este punto, el sistema saltaría automáticamente a la rutina de reparación apuntada por repar, que tendría que recalcular todos los resultados envenenados hasta que se ha atendido la excepción:

repar: lw r6, dato add r7, r4, r6 mult r2, r1, r7 mult r1, r8, r2 sw resul, r1

El código VLIW para la rutina de reparación es el siguiente:

Ciclo Slot 1 Slot 2 1 lw r6, dato 2 3 4 5 6 add r7, r4, r6 7 mult r2, r1, r7 8 9 mult r1, r8, r2

10 11 sw resul, r1

Como se puede observar, la rutina de reparación tarda en ejecutarse otros 11 ciclos debido a la latencia de la carga de memoria, por lo que cuando haya un fallo de página el programa tardará en ejecutarse 22 ciclos, que es más tiempo del que tardaba sin aplicar la optimización. Por tanto, esta optimización debería aplicarse sólo si la probabilidad de que se produzca un fallo de página al cargar el dato es baja, o bien si la probabilidad de que r4 tome el valor 0 es pequeña. Estas probabilidades se pueden estimar realizando algunas ejecuciones del programa sin optimizar y analizando su comportamiento.

Solución al Problema 4:

El programa se ejecuta correctamente, ya que en cada iteración se ejecutará la instrucción de almacenamiento que hay detrás del salto y el efecto que tendrá será simplemente el de almacenar la suma parcial acumulada en f0. Sin embargo, esta operación, aunque no provoca que el resultado sea incorrecto, sí que repercute en el tiempo de ejecución del programa, ya que si el vector X tiene N elementos, se realizarán N – 1 almacenamientos que consumen un tiempo de ejecución que podría usarse para algo más provechoso. Por ejemplo, una posible optimización podría ser la siguiente:

add r1, r0, r0 ; Inicializamos el índice i a 0 subd f0, f0, f0 ; Inicializamos el acumulador a 0 bucle: ld f2, X(r1) ; Cargamos X(i) subi r3, r3, #8 ; Comprobamos si hemos acabado multd f6, f2, f4 ; Multiplicamos X(i) por a (en f4) addd f0, f0, f6 ; Acumulamos el resultado bnez r3, bucle ; Saltamos si quedan elementos addi r1, r1, #8 ; Incrementamos el contador del índice sd R, f0 ; Guardamos el resultado

En este caso, la instrucción de después del salto retardado se utiliza para incrementar el puntero al siguiente elemento de X, instrucción que hay que realizar de todas formas, con lo que el cuerpo del bucle pasa a tener una instrucción menos que antes. Además, la instrucción de resta se ha colocado detrás la instrucción de carga para ocultar su retardo carga-uso. Para obtener la productividad del cauce primero tenemos que calcular cuánto tiempo tarda en ejecutarse el programa para un vector de N elementos:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 add r1, r0, r0 IF ID EX MEM WB subd f0, f0, f0 IF ID EX EX MEM WB ld f2, X(r1) IF ID EX X MEM WB subi r3, r3, #8 IF ID X EX MEM WB multd f6, f2, f4 IF X ID EX EX EX MEM WB addd f0, f0, f6 IF ID X X EX EX MEM WB bnez r3, bucle IF X X ID addi r1, r1, #8 IF ID X EX MEM WB sd R, f0 IF X ID EX MEM WB

Las partes sin sombrear de la figura indican el tiempo de inicialización y finalización del programa, mientras que la parte que está sombreada es el tiempo que transcurre entre dos iteraciones del bucle, es decir, que tardamos 2 ciclos en comenzar la primera iteración, que transcurren 9 ciclos entre el comienzo de una iteración y el comienzo de la siguiente, y que tras la última iteración se tardan 6 ciclos en acabar. Por tanto, el tiempo que tardaría en ejecutarse el programa para procesar un vector de N elementos sería:

89692 +=++= NNTN Sabiendo el tiempo de ejecución, la productividad del cauce se puede expresar en términos de resultados por ciclo o de instrucciones por ciclo:

loinstr./cic 8936

Tiemponesinstruccio Nº

++

==NNWN /cicloresultados

89Tiemporesultados Nº

+==

NNWN