ARQUITECTURA DE COMPUTADORES I
Examen de Septiembre (16 -9-2005)
1. (1.5 puntos) En un procesador vectorial a 1 GHz, con registros vectoriales de 32 componentes, tres unidades de
carga/almacenamiento de memoria (LV/SV), un sumador, y un multiplicador, se ejecuta el bucle:
for i:=1 to 512 do Z(i):=Z(i)+X[i]*Y[i]
Determine el valor de R∞ teniendo en cuenta que el procesador puede encadenar y solapar los cauces y que cada uno de esos cauces, por
separado, puede terminar un componente por ciclo. ¿Qué ocurriría si los registros vectoriales fuesen de 64 componentes?
Nota: TLI(Mult) = 24 ciclos; TLI(Suma) = 12 ciclos; TLI(LV/SV) = 8; TBASE = 8 ciclos; TBUCLE = 10 ciclos.
2. (1.5 puntos) En un procesador VLIW cuyas instrucciones pueden codificar tres operaciones (tres campos o slots en cada instrucción
VLIW), todas las operaciones pueden predicarse. Para establecer los valores de los predicados se utilizan instrucciones de comparación
(cmp) con el formato (p) p1[, p2] [Link] 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 operación sólo se ejecuta si el predicado p=1 (habrá sido
establecido por otra instrucción de comparación).
Indique cómo sería el código VLIW para la sentencia
if (X > 3) then { Y = X ; X = X / 2; } else if ( (X > 0) and (X < 1) ) then { Y = – X ; X = 2 * X ; } ;
sin ninguna operación de salto, teniendo en cuenta que las instrucciones de comparación sólo pueden aparecer en el primer campo o slot
de la instrucción VLIW (el resto de las instrucciones pueden aparecer en cualquier campo). Considere que dispone del número de
unidades funcionales necesarias en cada momento.
3. (1.5 puntos) Suponga un procesador superescalar en que se decodifican dos instrucciones por ciclo, se emiten tres instrucciones por
ciclo como máximo (con emisión desordenada y no alineada, sin estaciones de reserva), y se retiran hasta dos instrucciones por ciclo
como máximo. La emisión y la ejecución son desordenadas, y las instrucciones, una vez decodificadas, se introducen en un buffer de
reordenamiento (ROB) que permite la finalización ordenada del procesamiento de las instrucciones.
Indique las dependencias entre instrucciones, los ciclos en los que se emiten las instrucciones para su ejecución y cómo evolucionaría el
buffer de reordenamiento hasta que se hayan retirado todas las instrucciones de la siguiente secuencia de instrucciones almacenadas en
la cola de instrucciones captadas:
multd f1,f1,f2; f1=f1*f2
addd f3,f3,f2; f3=f3+f2
multd f4,f1,f3; f4=f1*f3
addd f6,f4,f2; f6=f4+f2
addd f3,f1,f3; f3=f1+f3
subd f6,f2,f1; f6=f2-f1
Suponiendo una frecuencia de 3.0 GHz, ¿cuánto tarda en procesarse la secuencia de instrucciones? ¿Cuál es la velocidad pico del
procesador?
Nota: La suma y la resta consumen dos ciclos de reloj y la multiplicación cuatro ciclos. Considere que no hay limitaciones en la
capacidad de los buffers, pero sólo tiene un multiplicador y dos sumadores/restadores. Se supone que f1, f2, y f3 tienen valores válidos
previos.
4. (1.5 puntos) Se han encontrado dos posibles alternativas para la ejecución de una función F en un cauce con 4 etapas S1, S2, S3, S4.
La alternativa 1 visita las etapas según la secuencia: S1 S3 S1 S3 S2 S4 S4, y la alternativa 2 en el orden: S1 S2 S3 S2 S3 S4 S2. (A)
¿Cuál de las dos alternativas permite ejecutar un número mayor de funciones por unidad de tiempo? Demuestre razonadamente su
respuesta. (B) Obtenga además la ganancia en velocidad que ofrecen cada una de las alternativas con respecto a su ejecución sin cauce
para 1000 operaciones, teniendo en cuenta que sin cauce la función requiere un tiempo de 15 ns; que las etapas del cauce suponen unos
tiempos de ejecución de: 4ns para S1, 4 ns para S2, 3 ns S3 y 4 ns para S4; y que los registros introducen retardos de 0.1 ns.
5. (1 punto) Se dispone de una memoria de 8 Mbytes con entrelazado de orden inferior y acceso de tipo S (simultáneo) distribuida en
módulos de 256 Kbytes. Se ha almacenado un vector de 138 componentes en posiciones de memoria consecutivas a partir de la
posición 34BC5h. ¿Cuántos accesos se necesitan para leer el vector completo? ¿Y si el entrelazado fuera de orden superior
(manteniendo el acceso de tipo S)?
6. (1 punto) En la ejecución de una programa una instrucción se salto condicional (salta a una dirección anterior) genera la secuencia de
saltos (S) y no saltos (N) siguiente:
SSSSN SSSSN SSNSS NSSSN NNNN
Indique la penalización que se introduce si se utiliza:
a) Predicción fija (siempre se considera que se va a producir el salto)
b) Predicción estática (si el desplazamiento es negativo se toma y si es positivo no)
c) Predicción dinámica con dos bits, inicialmente en el estado (11).
Nota: La penalización por saltos incorrectamente predichos es de 5 ciclos y para los saltos correctamente predichos es 0 ciclos.
Solución al Problema 1:
El tamaño de los registros vectoriales del procesador propuesto en el problema es MVL = 32, que es bastante menor que el vector que
deseamos procesar, que tiene un tamaño n = 512 elementos. Por tanto, tendremos que aplicar la técnica de strip-mining para trocear el
vector y procesarlo iterativamente. Dado que R∞ se define como
k × operaciones vectoriales × frecuencia
R∞ = lim R k = lim
k →∞ k →∞ Tk
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 tres cargas vectoriales de X, Y, y Z, una
multiplicación, una suma y un almacenamiento del resultado en Z. El diagrama de tiempos de estas instrucciones es el siguiente:
TLI=8 LV VX, RX
TLI=8 LV VY, RY
TLI=8 LV VZ, RZ
TLI=24 MULT V1, VX, VY
TLI=12 ADD VZ, VZ, V1
TLI=8 SV RZ, VZ
44 32 8
Las latencias de la multiplicación y de la suma se solapan completamente con las cargas vectoriales, por lo que en cuanto se produce el
primer resultado, como ya han terminado las tres unidades LV/SV, ya puede empezar a almacenarse. Por tanto, tenemos que el tiempo
por componente es TPC = 1 y que el tiempo de latencia inicial TLI = 8 + 24 + 12 + 8 = 52. 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:
⎡ k ⎤
Tk = TBASE + ⎢ (TLI + TBUCLE ) + k ⋅ TPC = 8 + ⎡⎢ k ⎤⎥(52 + 10) + 1·k ciclos
⎢ MLV ⎥⎥ ⎢ 32 ⎥
Una vez obtenido Tk, obtenemos R∞:
k × ops vec × frecuencia k × 2 × 1000 2000k
R∞ = lim Rk = lim = lim = lim = 680,85 MFLOPS
k →∞ k →∞ k →∞ ⎡k ⎤ k →∞ ⎡k ⎤
8 + ⎢ ⎥ (52 + 10 ) + 1 ⋅ k 8 + ⎢ ⎥ (62 ) + k
Tk
⎢ 32 ⎥ ⎢ 32 ⎥
Si MLV = 64 TLI y TPC cambian, como se muestra en el siguiente diagrama.
TLI=8 LV VX, RX
TLI=8 LV VY, RY
TLI=8 LV VZ, RZ
TLI=24 MULT V1, VX, VY
TLI=12 ADD VZ, VZ, V1
TLI=8 SV RZ, VZ
8 64 64 8
En este caso, TLI = 8 + 8 = 16 y TPC = 2, ya que el SV debe esperar a los LV (sólo hay tres unidades LV/SV). Con estos valores de
TLI y TPC, obtenemos R∞:
k × ops vec × frecuencia k × 2 × 1000 2000k
R∞ = lim Rk = lim = lim = lim = 831,17 MFLOPS
k →∞ k →∞ k →∞ ⎡k ⎤ k →∞ ⎡k ⎤
8 + ⎢ ⎥ (16 + 10) + 2 ⋅ k 8 + ⎢ ⎥ (26 ) + 2k
Tk
⎢ 64 ⎥ ⎢ 64 ⎥
Solución al Problema 2:
Como en el enunciado nos indican que la secuencia de instrucciones debe quedar sin ningún salto, debemos predicar las instrucciones
que contiene en su interior. A continuación se muestran el organigrama del programa una vez que se han predicado las instrucciones y
su código en ensamblador derivado.
Inicio
addi r1, r0, #1 ; r1 ← 1
(p1) Si No (p2) addi r3, r0, #3 ; r3 ← 3
X>3
lw r10, X(r0) ; r10 ← X
Y←X (p3) Si No p1, p2 [Link] r10, r3 ; p1 ← 1 si X > 3
X>0
X←X/2
p3 [Link] r0, r0 ; p3 ← 0
Si (p4)
p4 [Link] r0, r0 ; p4 ← 0
No
X<1 (p1) sw r10, Y(r0) ;Y←X
(p1) sra r11, r10, r1 ; r11 ← X / 2
(p1) sw r11, X(r0) ; X ← r11
Y ← –X (p2) p3 [Link] r10, r0 ; p3 ← 1 si X > 0
X ← 2*X (p3) p4 [Link] r10, r1 ; p4 ← 1 si X < 1
(p4) sub r12, r0, r10 ; r12 ← –X
(p4) sw r12, Y(r0) ; Y ← –X
(p4) sll r13, r10, r1 ; r13 ← 2*X
(p4) sw r13, X(r0) ; X ← r13
Fin
Tras desenrollar e introducir las operaciones con predicados, sólo nos queda reorganizar el código respetando las dependencias de datos
para construir las instrucciones VLIW:
Slot 1 Slot 2 Slot 3
p3 [Link] r0, r0 addi r1, r0, #1 addi r3, r0, #3
p4 [Link] r0, r0 lw r10, X(r0)
p1, p2 [Link] r10, r3
(p2) p3 [Link] r10, r0 (p1) sw r10, Y(r0) (p1) sra r11, r10, r1
(p3) p4 [Link] r10, r1 (p1) sw r11, X(r0)
(p4) sub r12, r0, r10 (p4) sll r13, r10, r1
(p4) sw r12, Y(r0) (p4) sw r13, X(r0)
Solución al Problema 3:
Ya que el procesador no dispone de estaciones de reserva, la lógica de emisión tiene que esperar a que los operandos le sean facilitados
por la lógica de bypass, por tanto, las dependencias RAW afectarán al orden de emisión de las instrucciones. Existen las siguientes
dependencias RAW:
• La instrucción 3 depende de f1 producido por la instrucción 1 y f3 producido por la instrucción 2.
• La instrucción 4 depende de f4 producido por la instrucción 3.
• La instrucción 5 depende de f1 producido por la instrucción 1 y f3 producido por la instrucción 2.
• La instrucción 6 depende de f1 producido por la instrucción 1.
Teniendo en cuenta estas dependencias, las instrucciones se ejecutarían como se muestra en la siguiente figura:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Instrucción / Ciclo
(1) multd f1, f1, f2 ID ISS EX EX EX EX ROB WB
(2) addd f3, f3, f2 ID ISS EX EX ROB WB
(3) addd f4, f1, f3 ID ISS EX EX EX EX ROB WB
(4) addd f6, f4, f2 ID ISS EX EX ROB WB
(5) multd f3, f1, f3 ID ISS EX EX ROB WB
(6) subd f6, f2, f1 ID ISS EX EX ROB WB
A continuación pasamos a describir la evolución del buffer de reorden:
Ciclo 1: # Cod. Op. Dest. Result. Ok
• Se decodifican las instrucciones 1 y 2 y se 1 multd f1 ? 0
introducen en el ROB 2 addd f3 ? 0
# Cod. Op. Dest. Result. Ok
Ciclo 2: 1 multd f1 ? 0
• Se decodifican las instrucciones 3 y 4 y se 2 addd f3 ? 0
introducen en el ROB 3 addd f4 ? 0
4 addd f6 ? 0
# Cod. Op. Dest. Result. Ok
1 multd f1 ? 0
Ciclo 3: 2 addd f3 ? 0
• Se decodifican las instrucciones 5 y 6 y se 3 addd f4 ? 0
introducen en el ROB 4 addd f6 ? 0
5 multd f3 ? 0
6 subd f6 ? 0
# Cod. Op. Dest. Result. Ok
1 multd f1 ? 0
2 addd f3 f3+f2 1
Ciclo 5:
3 addd f4 ? 0
• Finaliza la instrucción 2
4 addd f6 ? 0
5 multd f3 ? 0
6 subd f6 ? 0
# Cod. Op. Dest. Result. Ok
1 multd f1 f1*f2 1
2 addd f3 f3+f2 1
Ciclo 7:
3 addd f4 ? 0
• Finaliza la instrucción 1
4 addd f6 ? 0
5 multd f3 ? 0
6 subd f6 ? 0
# Cod. Op. Dest. Result. Ok
3 addd f4 ? 0
Ciclo 8:
4 addd f6 ? 0
• Se retiran las instrucciones 1 y 2
5 multd f3 ? 0
6 subd f6 ? 0
# Cod. Op. Dest. Result. Ok
3 addd f4 ? 0
Ciclo 9:
4 addd f6 ? 0
• Finalizan las instrucciones 5 y 6
5 multd f3 f1+f3 1
6 subd f6 f2–f1 1
# Cod. Op. Dest. Result. Ok
3 addd f4 f1*f3 1
Ciclo 11:
4 addd f6 ? 0
Finaliza la instrucción 3
5 multd f3 f1+f3 1
6 subd f6 f2–f1 1
# Cod. Op. Dest. Result. Ok
Ciclo 12: 4 addd f6 ? 0
Se retira la instrucción 3 5 multd f3 f1+f3 1
6 subd f6 f2–f1 1
# Cod. Op. Dest. Result. Ok
Ciclo 13: 4 addd f6 f4+f2 1
Finaliza la instrucción 4 5 multd f3 f1+f3 1
6 subd f6 f2–f1 1
Ciclo 14: # Cod. Op. Dest. Result. Ok
Se retiran las instrucciones 4 y 5 6 subd f6 f2–f1 1
Ciclo 15:
# Cod. Op. Dest. Result. Ok
Se retira la instrucción 6
Si el procesador funciona a 3 GHz, el tiempo de procesamiento sería
15 ciclos * 3,33×10–10 s/ciclo = 5×10–9 s = 5 ns
Para la calcular la velocidad pico, como sólo se pueden retirar dos instrucciones por ciclo, suponiendo que no hubiera atascos en el
cauce se podrían ejecutar 2 instrucciones por ciclo
2 instr./ciclo * 3×109 ciclos/s = 6 GIPS
Solución al Problema 4:
El primer paso para responder al primer apartado es calcular la tabla de reservas para cada una de las dos alternativas:
Alternativa 1 Alternativa 2
1 2 3 4 5 6 7 1 2 3 4 5 6 7
S1 X X S1 X
S2 X S2 X X X
S3 X X S3 X X
S4 X X S4 X
Una vez calculadas las tablas de reservas es fácil obtener las latencias prohibidas y los vectores de colisiones de cada una de las
alternativas:
F1 = {1,2} C1 = (11) F2 = {2,3,5} C2 = (10110)
Para calcular determinar qué alternativa tiene la máxima productividad, realizamos un diagrama de estados a partir de cada vector de
colisiones:
Alternativa 1 Alternativa 2
3
11 1 10110 4
3 6 6
11111 10111
La mínima latencia mínima de cada alternativa es:
1+ 6
MLM1 = 3 MLM2 = = 3,5
2
Para ver qué alternativa es capaz de ejecutar más operaciones por unidad de tiempo basta con calcular la productividad máxima de cada
una de ellas. La productividad máxima se define como:
n n 1
Wmax = lim W (n ) = lim = lim =
n →∞ n →∞ T (n ) n →∞ TLI + MLM ( n − 1) MLM
Para cada una de las alternativas tenemos que:
1 1 1 1
W1 max = = = 0,3 W2 max = = = 0,29
MLM 1 3 MLM 2 3,5
con lo que podemos concluir que la primera alternativa es mejor que la segunda.
Para responder a la segunda cuestión, debemos calcular tanto el tiempo secuencial como el de cada una de las alternativas para realizar
1000 operaciones. En el caso secuencial tenemos que:
TSec(1000) = 1000 operaciones · 15 ns/operación = 15000 ns
Y en el caso paralelo, el tiempo de ejecución se define como:
T ( n ) = Tclock ·(TLI + MLM ( n − 1) )
El tiempo ciclo del reloj se puede obtener como:
Tclock = máx{TS1, TS2, TS3, TS4} + Tacoplo = máx {4, 4, 3, 4} + 0,1 = 4 + 0,1 = 4,1 ns
Por tanto, la ganancia en velocidad de cada una de las alternativas respecto al caso secuencial es de:
TSec (1000) 15000 TSec (1000) 15000
S1 (1000) = = = 1,22 S1 (1000) = = = 1,04
T1 (1000) 4,1(7 + 3(1000 − 1)) T1 (1000) 4,1(7 + 3,5(1000 − 1))
Solución al Problema 5:
El primer paso para resolver este problema es ver cómo se encuentran repartidos los elementos del vector entre los módulos de memoria.
Tenemos una memoria de 8 MB = 223 Bytes, repartida en módulos de 256 KB = 218 Bytes, lo que quiere decir que tendremos un total de
25 = 32 módulos de memoria. Si se utiliza entrelazado inferior y acceso tipo S para acceder a ellos, las posiciones de memoria
consecutivas se encontrarán en módulos de memoria consecutivos, y como hay 32 módulos, en el módulo 0 estarán todas las
direcciones múltiplo de 32, 0x20 en hexadecimal. Teniendo esto en cuenta, y que el mayor múltiplo de 0x20 por debajo de 0x34BC5 es
0x34BC0, los datos estarán colocados en las posiciones de memoria sombreadas de la siguiente figura:
Dirección 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F
0x34BC0
0x34BE0
0x34C00
0x34C20
0x34C40
Con lo que para acceder a todos los datos del vector tendremos que generar las 5 direcciones de la primera columna de la tabla anterior,
es decir, que son necesarios 5 accesos a memoria.
En el caso de que se utilizara entrelazado superior, las posiciones de memoria consecutivas se encontrarían en el mismo módulo. Tanto
la dirección de comienzo como la de final del vector se encontrarían en el módulo de memoria 0, que contendría las posiciones de
memoria desde la dirección 0x000000 a la 0x40000, con lo que harían falta 138 accesos a memoria, tantos como componentes, para leer
el vector.
Solución al Problema 6:
En el primer caso, con predicción fija, se predecirá siempre que se va a producir el salto, por lo que se sufrirá una penalización en
aquellas ocasiones que las que no se produzca el salto. Para la secuencia de saltos del enunciado tenemos:
Predicción S S S S S S S S S S S S S S S S S S S S S S S S
Secuencia S S S S N S S S S N S S N S S N S S S N N N N N
Penalización P P P P P P P P P
Si la penalización es P = 5 ciclos, al final se pierden 9 · P = 9 · 5 = 45 ciclos.
En el caso de usar un predictor estático, como el salto es hacia atrás, el predictor estimará que siempre se va a producir el salto, con lo
que el resultado es exactamente igual al anterior, produciéndose una penalización de 45 ciclos.
En el último caso se utiliza un predictor dinámico de 2 bits inicializado al valor 11 (saltar). Para la secuencia anterior tenemos las
siguientes predicciones:
Estado 11 11 11 11 11 10 11 11 11 11 10 11 11 10 11 11 10 11 11 11 10 01 00 00
Predicción S S S S S S S S S S S S S S S S S S S S S N N N
Secuencia S S S S N S S S S N S S N S S N S S S N N N N N
Penalización P P P P P P
En este caso la penalización es 6 · P = 6 · 5 = 30 ciclos.
