View
10
Download
0
Category
Preview:
Citation preview
Ejercicios de evaluación. Grafos de dependencias y DLX
UNIVERSIDAD Carlos III de MadridEjercicios de evaluación. Grafos de dependencias y DLXDepartamento de Ingeniería de Sistemas y Automática
RAÚL PÉRULA MARTÍNEZLUIS ENRIQUE MORENO LORENTEALBERTO BRUNETE GONZALEZCESAR AUGUSTO ARISMENDI GUTIERREZDOMINGO MIGUEL GUINEA GARCIA ALEGREJOSÉ CARLOS CASTILLO MONTOYA
Esta obra se publica bajo una licencia Creative Commons Reconocimiento-NoComercial-CompartidaIgual 3.0 España.
Ejercicio 1
Se dispone de un procesador que está segmentado en las siguientes etapas: Búsqueda, descodificación, emisión, ejecución y write-back. Dispone de cuatro unidades funcionales de ejecución: una para operaciones en punto flotante (2 ciclos), una para operaciones entereas (1 ciclo) , una para lectura en memoria y otra para escritura en memoria (1 ciclo). Dado el siguiente programa en ensamblador:bucle:ld f2, 0(r1)add f4,f0,f2sto 0(r1), f4ld f6, -4(r1)add f8, f6, f2sto -4(r1), f8sub r1,r1, #8bnez r1, bucleSe pide: Cronograma de ejecución sin adelantamiento. Calcular el CPI.Cronograma de ejecución con adelantamiento. Calcular el CPI.
CPI = 24/8 = 3
CPI = 16/8 = 2
Ejercicio 2Suponiendo que se tiene el siguiente código en lenguaje ensambladorL0: ld r3, # 100ld r2, DIR_Xld r2, DIR_Y1L1: ld f2, 0(r1)2blt f2, 0 , L33L2:ld f4, 0(r2)4ld f6, 4(r2)5add f8, f2, f46add f8, f8, f67store 0(r2), f88br L49L3:store 0(r2), f210L4: add r1, r1, #411add r2, r2, #412sub r3,r3, #413blt r3, 0 L1
donde se lista en primer lugar el operando de destino y a continuación los operandos fuentes, y en el caso de las instrucciones de salto se listan primero los operandos a ser comparados y después la dirección del salto. Se pide:Dado el esquema de arquitectura DLX mostrar los cronogramas de ejecución si el control de riesgos se realiza por software (introduciendo instrucciones no-op).Obtener los cronogramas suponiendo que la arquitectura del procesador incluye hw para interbloqueo y forwarding.
Ejercicio 3El siguiente fragmento de código aplica un filtro sobre un vector A y almacena el resultado en un vector B:for (int i = 1 ; i < 100 ; i++){b[i] = d * a[i-1] + a[i] + d * a[i+1];}El compilador lo traduce al siguiente código DLXaddi r3, r1, 800; condición de finaladdi r1, r1, 8; inicialización de los índicesaddi r2, r2, 8ld f0, d; Carga el coeficiente d1.loopld f2, -8(r1); carga de a[i-1]2.ld f4, 0(r1); carga de a[i]3.ld f6, 8(r1); carga de a[i+1]4.multd f8, f2, f2; d * a[i-1]5.multd f10, f0, f6; d * a[i+1]6.addd f4, f4, f8; d * a[i-1] + a[i]7.addd f4, f4, f10; d * a[i-1] + a[i] + d * a[i+1]8.sd 0(r2), f4; Guarda en b[i]9.addi r2, r2, 8; incremento de índices10.addi r1, r1, 811.addi r1, r1, 812.slt r4, r1, r313.bnez r4, loop
Las operaciones de división/multiplicación en punto flotante tienen un retardo de 4 ciclos y las operaciones de carga y almacenamiento utilizan la memoria de datos durante 2 ciclos para completar las lecturas y escrituras.Dibujar el grafo de dependencias de este programaCronograma de ejecución con y sin adelantamiento. Calcular el CPI para ambas alternativas.
Ejercicio 4Dado el código ensamblador que implementa la operación vectorial Y = (a * X + Y) / X:ld r1, dir_xld r2, dir_yld r4, dir_contld f0, dir_a1.loop:ld f2, 0(r1); carga X[i]2.multd f4, f2, f0; multiplica a * X[i] 3.ld f6, 0(r2); carga Y[i]4.addd f6, f4, f6; suma a * X[i] + Y[i]5.divd f6, f6, f2; Divide (a * X[i] + Y[i]) / X[i]6.sd 0(r2), f6; Almacena Y[i]7.addi r1, r1, 8; incrementa el índice de x8.addi r2, r2, 8; incrementa el índice de Y9.sgt r3, r1, r4; comprueba si fin10.bequz r3, loop
Considerando que el código se ejecuta en una máquina DLX segmentada con unidades funcionales con las siguientes características: Unidad funcionalLatencia (ciclos)ALU entera0Suma PF1Multiplicación PF2División PF3
Obtener el cronograma de una iteración del bucle considerando interbloqueo. Calcular el CPI.Obtener el cronograma de una iteración del bucle considerando interbloqueo y anticipación. Calcular el CPI y el speedup respecto al apartado anterior.
CPI = 29/10 = 2,9
CPI = 20/10 = 2
Ejercicio 5Suponiendo que el siguiente código en C for ( i = 0; i<100; i++)if (X[i ]> 0)Y[i]= X[i ]*X[i] –Y[i];elseY[i]= X[i]*X[i]-Y[i+1]+10;tiene la siguiente traducción a un cierto lenguaje ensamblador L0:ldr3, #100ldr1,DIR_Xldr2,DIR_Y1L1:ldf2, 0(r1)2mulf4, f2, f23bltf2, 0, L34L2:ldf6, 0(r2)5subf6, f4, f66store0(r2), f67brL48L3:ldf8, 4(r2)9subf6, f4, f810addif4,f6, #1011store0(r2), f412L4:addr1, r1, #413addr2, r2, #414subr3, r3, #-115bltr3, 0, L1
Los saltos se resuelven en la primera mitad de la etapa Mem y las instrucciones pueden leerse en la segunda mitad de la etapa If. La arquitectura del procesador es la siguiente (DLX, predict-not-taken):
Muestre el cronograma de la ejecución de una iteración del bucle considerando que los riesgos de datos se resuelven utilizando interbloqueo y que sí se cumple la condición del IF. Calcule el CPI del programa. Muestre el cronograma de la ejecución de una iteración del bucle considerando que los riesgos de datos se resuelven utilizando interbloqueo y anticipación, y que sí se cumple la condición del IF. Calcule el CPI del programa. Sugiera una posible reorganización del código que suponga una mejora en el CPI del programa e indique la modificación en el cronograma.
CPI = 27/11 = 2,45
CPI = 21/11 = 1,9
CPI = 20/11 = 1,82
Sin adelantamiento 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 281. bucle: ld f2, 0(r1) f d x m w2. add f4,f0,f2 f -‐ -‐ d x x m w3. sto 0(r1), f4 f -‐ -‐ -‐ d x m w4. ld f6, -‐4(r1) f d x m w5. add f8, f6, f2 f -‐ -‐ d x x m w6. sto -‐4(r1), f8 f -‐ -‐ -‐ d x m w7. sub r1,r1, #8 f d x m w8. bnez r1, bucle f -‐ -‐ -‐ d x m w
Sinadelantamiento12345678910111213141516171819202122232425262728
1. bucle:ldf2,0(r1)
fdxmw
2. addf4,f0,f2
f--dxxmw
3. sto0(r1),f4
f---dxmw
4. ldf6,-4(r1)
fdxmw
5. addf8,f6,f2
f--dxxmw
6. sto-4(r1),f8
f---dxmw
7. subr1,r1,#8
fdxmw
8. bnezr1,bucle
f---dxmw
Con adelantamiento 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 281. bucle: ld f2, 0(r1) f d x m* w2. add f4,f0,f2 f d -‐ *x x* m w3. sto 0(r1), f4 f -‐ d -‐ *x m w4. ld f6, -‐4(r1) f -‐ d x m* w5. add f8, f6, f2 f d -‐ *x x* m w6. sto -‐4(r1), f8 f -‐ d -‐ *x m w7. sub r1,r1, #8 f -‐ d x* m w8. bnez r1, bucle f d *x m w
Conadelantamiento12345678910111213141516171819202122232425262728
1. bucle:ldf2,0(r1)
fdxm*w
2. addf4,f0,f2
fd-*xx*mw
3. sto0(r1),f4
f-d-*xmw
4. ldf6,-4(r1)
f-dxm*w
5. addf8,f6,f2
fd-*xx*mw
6. sto-4(r1),f8
f-d-*xmw
7. subr1,r1,#8
f-dx*mw
8. bnezr1,bucle
fd*xmw
NO-‐OP SI 0(r1)>0 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 29 30 31L0: ld r3, # 100
ld r2, DIR_Xld r2, DIR_Y
1 L1: ld f2, 0(r1) F D X M WNOP F DNOP F D
2 blt f2, 0 , L3 F D X M WNOP F DNOP F DNOP F D
3 L2: ld f4, 0(r2) F D X M W4 ld f6, 4(r2) F D X M W
NOP F D5 add f8, f2, f4 F D X M W
NOP F DNOP F D
6 add f8, f8, f6 F D X M WNOP F DNOP F D
7 store 0(r2), f8 F D X M W8 br L4 F D X M W
NOP F DNOP F DNOP F D
9 L3: store 0(r2), f210 L4: add r1, r1, #4 F D X M W11 add r2, r2, #4 F D X M W12 sub r3,r3, #4 F D X M W
NOP F DNOP F D
13 blt r3, 0 L1 F D X M W
NO-OPSI0(r1)>0 12345678910111213141516171819202122232425262728293031
L0:ldr3,#100
ldr2,DIR_X
ldr2,DIR_Y
1L1:ldf2,0(r1)FDXMW
NOP FD
NOP FD
2 bltf2,0,L3 FDXMW
NOP FD
NOP FD
NOP FD
3L2:ldf4,0(r2) FDXMW
4 ldf6,4(r2) FDXMW
NOP FD
5 addf8,f2,f4 FDXMW
NOP FD
NOP FD
6 addf8,f8,f6 FDXMW
NOP FD
NOP FD
7 store0(r2),f8 FDXMW
8 brL4 FDXMW
NOP FD
NOP FD
NOP FD
9L3:store0(r2),f2
10L4:addr1,r1,#4 FDXMW
11 addr2,r2,#4 FDXMW
12 subr3,r3,#4 FDXMW
NOP FD
NOP FD
13 bltr3,0L1 FDXMW
INTERBLOQUEO Y FORWARDING1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
1 L1: ld f2, 0(r1) F D X M*W2 blt f2, 0 , L3 F -‐ D *X M W3 L2: ld f4, 0(r2) F D X M*W4 ld f6, 4(r2) F D X M*W5 add f8, f2, f4 F D *X*M W6 add f8, f8, f6 F D *X*M W7 store 0(r2), f8 F D *X M W8 br L4 F D X M W9 L3: store 0(r2), f210 L4: add r1, r1, #4 F D X M W11 add r2, r2, #4 F D X M W12 sub r3,r3, #4 F D X* M W13 blt r3, 0 L1 F D *X M W
INTERBLOQUEOYFORWARDING
1234567891011121314151617181920212223
1L1:ldf2,0(r1)FDXM*W
2 bltf2,0,L3F-D*XMW
3L2:ldf4,0(r2) FDXM*W
4 ldf6,4(r2) FDXM*W
5 addf8,f2,f4 FD*X*MW
6 addf8,f8,f6 FD*X*MW
7 store0(r2),f8 FD*XMW
8 brL4 FDXMW
9L3:store0(r2),f2
10L4:addr1,r1,#4 FDXMW
11 addr2,r2,#4 FDXMW
12 subr3,r3,#4 FDX*MW
13 bltr3,0L1 FD*XMW
Interbloqueo sin Adelantamiento 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 29 30 31 32 33 34 35addi r3, r1, 800addi r1, r1, 8addi r2, r2, 8ld f0, d
1. loop ld f2, -‐8(r1) F D X M M W2. ld f4, 0(r1) F D X -‐ M M W3. ld f6, 8(r1) F D -‐ X -‐ M M W4. multd f8, f2, f2 F -‐ D Xm Xm Xm Xm M W5. multd f10, f0, f6 F -‐ -‐ -‐ D Xm Xm Xm Xm M W6. addd f4, f4, f8 F -‐ -‐ D X -‐ M W7. addd f4, f4, f10 F -‐ -‐ -‐ D X M W8. sd 0(r2), f4 F -‐ -‐ D X M M W9. addi r2, r2, 8 F D X -‐ M W10. addi r1, r1, 8 F D -‐ X M W11. addi r1, r1, 8 F -‐ -‐ -‐ D X M W12. slt r4, r1, r3 F -‐ -‐ D X M W13. bnez r4, loop F -‐ -‐ D X M W
InterbloqueosinAdelantamiento1234567891011121314151617181920212223242526272829303132333435
addir3,r1,800
addir1,r1,8
addir2,r2,8
ldf0,d
1.loopldf2,-8(r1)FDXMMW
2.ldf4,0(r1)FDX-MMW
3.ldf6,8(r1) FD-X-MMW
4.multdf8,f2,f2 F-DXmXmXmXmMW
5.multdf10,f0,f6 F---DXmXmXmXmMW
6.adddf4,f4,f8 F--DX-MW
7.adddf4,f4,f10 F---DXMW
8.sd0(r2),f4 F--DXMMW
9.addir2,r2,8 FDX-MW
10.addir1,r1,8 FD-XMW
11.addir1,r1,8 F---DXMW
12.sltr4,r1,r3 F--DXMW
13.bnezr4,loop F--DXMW
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 231. loop ld f2, -‐8(r1) F D X M M W2. ld f4, 0(r1) F D X -‐ M M W3. ld f6, 8(r1) F D -‐ X -‐ M M* W4. multd f8, f2, f2 F -‐ D -‐ Xm Xm Xm Xm*M W5. multd f10, f0, f6 F -‐ -‐ D *XmXm Xm Xm*M W6. addd f4, f4, f8 F D -‐ *X M W7. addd f4, f4, f10 F -‐ -‐ D *X*M W8. sd 0(r2), f4 F D *X M M W9. addi r2, r2, 8 F D X -‐ M W10. addi r1, r1, 8 F D -‐ X* M W11. addi r1, r1, 8 F -‐ D *X*M W12. slt r4, r1, r3 F D *X*M W13. bnez r4, loop F D *X M W
Interbloqueo con Adelantamiento
1234567891011121314151617181920212223
1.loopldf2,-8(r1)FDXMMW
2.ldf4,0(r1)FDX-MMW
3.ldf6,8(r1) FD-X-MM*W
4.multdf8,f2,f2 F-D-XmXmXmXm*MW
5.multdf10,f0,f6 F--D*XmXmXmXm*MW
6.adddf4,f4,f8 FD-*XMW
7.adddf4,f4,f10 F--D*X*MW
8.sd0(r2),f4 FD*XMMW
9.addir2,r2,8 FDX-MW
10.addir1,r1,8 FD-X*MW
11.addir1,r1,8 F-D*X*MW
12.sltr4,r1,r3 FD*X*MW
13.bnezr4,loop FD*XMW
Interbloqueocon
Adelantamiento
INTERBLOQUEO 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 29ld r1, dir_xld r2, dir_yld r4, dir_contld f0, dir_a
1. loop: ld f2, 0(r1) F D X M W2. multd f4, f2, f0 F -‐ -‐ D Xm Xm Xm M W3. ld f6, 0(r2) F D X M W4. addd f6, f4, f6 F -‐ -‐ D Xa Xa M W5. divd f6, f6, f2 F -‐ -‐ -‐ D Xd Xd Xd Xd M W6. sd 0(r2), f6 F -‐ -‐ -‐ -‐ -‐ D X M W7. addi r1, r1, 8 F D X M W8. addi r2, r2, 8 F D X M W9. sgt r3, r1, r4 F -‐ D X M W10. bequz r3, loop F -‐ -‐ D X M W
INTERBLOQUEO 1234567891011121314151617181920212223242526272829
ldr1,dir_x
ldr2,dir_y
ldr4,dir_cont
ldf0,dir_a
1.loop:ldf2,0(r1)FDXMW
2. multdf4,f2,f0F--DXmXmXmMW
3. ldf6,0(r2) FDXMW
4. adddf6,f4,f6 F--DXaXaMW
5. divdf6,f6,f2 F---DXdXdXdXdMW
6. sd0(r2),f6 F-----DXMW
7. addir1,r1,8 FDXMW
8. addir2,r2,8 FDXMW
9. sgtr3,r1,r4 F-DXMW
10. bequzr3,loop F--DXMW
ANTICIPACIÓN1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1. loop: ld f2, 0(r1) F D X M* W2. multd f4, f2, f0 F -‐ D *XmXm Xm M W3. ld f6, 0(r2) F D X M* W4. addd f6, f4, f6 F -‐ D *Xa Xa*M W5. divd f6, f6, f2 F -‐ D *XdXd Xd Xd*M W6. sd 0(r2), f6 F -‐ -‐ -‐ D *X M W7. addi r1, r1, 8 F D X M* W8. addi r2, r2, 8 F D X M W9. sgt r3, r1, r4 F D *X*M W10. bequz r3, loop F D *X M W
ANTICIPACIÓN
1234567891011121314151617181920
1. loop:ldf2,0(r1)FDXM*W
2. multdf4,f2,f0F-D*XmXmXmMW
3. ldf6,0(r2) FDXM*W
4. adddf6,f4,f6 F-D*XaXa*MW
5. divdf6,f6,f2 F-D*XdXdXdXd*MW
6. sd0(r2),f6 F---D*XMW
7. addir1,r1,8 FDXM*W
8. addir2,r2,8 FDXMW
9. sgtr3,r1,r4 FD*X*MW
10. bequzr3,loop FD*XMW
EX
IDIF
AA
MMM
DDDD
Mem WB
EX
IDIF
AA
MMM
DDDD
Mem WB
SIN ADELANTAMIENTO -‐ IF 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 27L0: ld r3, #100
ld r1,DIR_Xld r2,DIR_Y
1 L1: ld f2, 0(r1) F D X M W2 mul f4, f2, f2 F -‐ -‐ D Xm Xm XmM W3 blt f2, 0, L3 F D X M W4 L2: ld f6, 0(r2) F D X -‐ M W5 sub f6, f4, f6 F -‐ -‐ -‐ D Xa Xa M W6 store 0(r2), f6 F -‐ -‐ -‐ D X M W7 br L4 F D X M W8 L3: ld f8, 4(r2)9 sub f6, f4, f810 addi f4,f6, #1011 store 0(r2), f412 L4: add r1, r1, #4 F D X M W13 add r2, r2, #4 F D X M W14 sub r3, r3, #-‐1 F D X M W15 blt r3, 0, L1 F -‐ -‐ D X M W
SINADELANTAMIENTO-IF 123456789101112131415161718192021222324252627
L0:ldr3,#100
ldr1,DIR_X
ldr2,DIR_Y
1L1:ldf2,0(r1)FDXMW
2mulf4,f2,f2F--DXmXmXmMW
3bltf2,0,L3 FDXMW
4L2:ldf6,0(r2) FDX-MW
5subf6,f4,f6 F---DXaXaMW
6store0(r2),f6 F---DXMW
7brL4 FDXMW
8L3:ldf8,4(r2)
9subf6,f4,f8
10addif4,f6,#10
11store0(r2),f4
12L4:addr1,r1,#4 FDXMW
13addr2,r2,#4 FDXMW
14subr3,r3,#-1 FDXMW
15bltr3,0,L1 F--DXMW
CON ADELANTAMIENTO -‐ IF 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 211 L1: ld f2, 0(r1) F D X M* W2 mul f4, f2, f2 F -‐ D *XmXm XmM W3 blt f2, 0, L3 F D X M W4 L2: ld f6, 0(r2) F D X -‐ M*W5 sub f6, f4, f6 F -‐ -‐ D *XaXa*M W6 store 0(r2), f6 F -‐ D *X M W7 br L4 F D X M W8 L3: ld f8, 4(r2)9 sub f6, f4, f810 addi f4,f6, #1011 store 0(r2), f412 L4: add r1, r1, #4 F D X M W13 add r2, r2, #4 F D X M W14 sub r3, r3, #-‐1 F D X* M W15 blt r3, 0, L1 F D *X M W
CONADELANTAMIENTO-IF 123456789101112131415161718192021
1L1:ldf2,0(r1)FDXM*W
2mulf4,f2,f2F-D*XmXmXmMW
3bltf2,0,L3 FDXMW
4L2:ldf6,0(r2) FDX-M*W
5subf6,f4,f6 F--D*XaXa*MW
6store0(r2),f6 F-D*XMW
7brL4 FDXMW
8L3:ldf8,4(r2)
9subf6,f4,f8
10addif4,f6,#10
11store0(r2),f4
12L4:addr1,r1,#4 FDXMW
13addr2,r2,#4 FDXMW
14subr3,r3,#-1 FDX*MW
15bltr3,0,L1 FD*XMW
REORDENACIÓN DEL IF 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 201 L1: ld f2, 0(r1) F D X M* W12 add r1, r1, #4 F D X M W2 mul f4, f2, f2 F D *XmXm XmM W3 blt f2, 0, L3 F D X M W4 L2: ld f6, 0(r2) F D X -‐ M*W5 sub f6, f4, f6 F -‐ -‐ D *XaXa M W6 store 0(r2), f6 F -‐ D *X M W7 br L4 F D X M W8 L3: ld f8, 4(r2)9 sub f6, f4, f810 addi f4,f6, #1011 store 0(r2), f413 L4: add r2, r2, #4 F D X M W14 sub r3, r3, #-‐1 F D X* M W15 blt r3, 0, L1 F D *X M W
REORDENACIÓNDELIF 1234567891011121314151617181920
1L1:ldf2,0(r1)FDXM*W
12addr1,r1,#4FDXMW
2mulf4,f2,f2FD*XmXmXmMW
3bltf2,0,L3 FDXMW
4L2:ldf6,0(r2) FDX-M*W
5subf6,f4,f6 F--D*XaXaMW
6store0(r2),f6 F-D*XMW
7brL4 FDXMW
8L3:ldf8,4(r2)
9subf6,f4,f8
10addif4,f6,#10
11store0(r2),f4
13L4:addr2,r2,#4 FDXMW
14subr3,r3,#-1 FDX*MW
15bltr3,0,L1 FD*XMW
Recommended