Post on 02-Jun-2018
8/10/2019 documento-120.pdf
1/49
2 curso / 2 cuatr.
Grado en
Ing. Informtica
Arquitectura de Computadores.
Algunos ejercicios resueltos
Tema 1. Arquitecturas Paralelas: Clasificacin y Prestaciones
Material elaborado por los profesores responsables de la asignatura:
Mancia Anguita, Julio Ortega
Licencia Creative Commons
1 Ejercicios
Ejercicio 1.
Ejercicio 2.(Tenga en cuenta que la redaccin de este ejercicio no coincide totalmente con la redaccin del
ejercicio 2 de la relacin de problemas del tema 2) En un procesador no segmentado que funciona a 300
MHz, hay un 20% de instrucciones LOAD que necesitan 4 ciclos, un 10% de instrucciones STORE que
necesitan 3 ciclos, un 25% de instrucciones con operaciones de enteros que necesitan 6 ciclos, un 15% de
instrucciones con operandos en coma flotante que necesitan 8 ciclos, y un 30% de instrucciones de salto que
necesitan 3 ciclos. Las operaciones con enteros se realizan en una ALU con un retardo de 3 ciclos, y las de
coma flotante en una unidad funcional con un retardo de 5 ciclos.
(a) Cul es la mxima ganancia que se puede obtener por reduccin en el tiempo en la ALU de las
operaciones con enteros? y (b) cul es la mxima ganancia que se puede obtener por reduccin en el
tiempo en la unidad funcional de las operaciones en coma flotante?
Solucin
Datos del ejercicio:
Tipo i de instr. CPIi (c/i) NIi/NI Comentarios
LOAD 4 0,20
STORE 3 0,10
ENTEROS 6 0,25 Con retardo de 3 ciclos en ALU
FP 8 0,15 Con retardo de 5 ciclos en unidad funcional
BR 3 0,30
TOTAL 100
La frecuencia de reloj no har falta.
La ley de Amdahl establece que la mxima ganancia de velocidad, S, que se puede conseguir al mejorar la
velocidad de un recurso en un factor p depende de la fraccin f del tiempo de procesamiento sin la mejora
en la que NO se puede aprovechar dicha mejora segn la expresin:
S p/(1+f(p-1)
La mxima ganancia que se podra conseguir debido a mejoras en algn recurso se podra obtener aplicando
el lmite cuando p tiende a infinito a la expresin de la ley de Amdahl. Es decir que Smax(1/f)
8/10/2019 documento-120.pdf
2/49
2 / 14 Arquitectura de Computadores
Grado en Ingeniera Informtica. ETSIIT Universidad de Granada
Por lo tanto, para resolver el problema utilizando esta expresin habra que evaluar los valores de f en cada
uno de los casos que se indican.
Tipo i de instr. CPIi (c/i) NIi/NI CPIicon mejora max. ENT. en ALU CPIicon mejora max. FP en UF
LOAD 4 0,20 4 4
STORE 3 0,10 3 3
ENTEROS 6 0,25 3 (se eliminan los 3 de la ALU) 6
FP 8 0,15 8 3 (se eliminan los 5 de la UF)
BR 3 0,30 3 3
TOTAL 100
El tiempo total de procesamiento antes de la mejora es igual a:
Tsin_mejora=(NI*0.2)*4*(Tciclo)+(NI*0.1)*3*(Tciclo)+(NI*0.25)*6*(Tciclo)+(NI*0.15)*8*(Tciclo)+(NI*0.3)*3*(Tciclo)=CPI
*NI*Tciclo
donde NI es el nmero de instruciones y Tciclo=1/frecuencia
(a) En el caso de mejoras en la ALU de enteros, el tiempo en el que no se puede aplicar la mejora sera (se
supone que el tiempo de procesamiento de la operacin en la ALU es 0 ciclos):
Tmejora_ent=(NI*0.2)*4*(Tciclo)+(NI*0.1)*3*(Tciclo)+(NI*0.25)*3*(Tciclo)+(NI*0.15)*8*(Tciclo)+(NI*0.3)*3*(Tciclo)
y por tanto
Smax (1/f) = Tmejora_ent/Tsin_mejora = 0.2*4+0.1*3+0.25*6+0.15*8+0.3*3/0.2*4+0.1*3+0.25*3+0.15*8+0.3*3=
4,7/3,95 = 1,8987
Smax1.19
(b) En el caso de mejoras en operaciones de coma flotante , el tiempo en el que no se puede aplicar la
mejora sera (se supone que el tiempo de procesamiento de la operacin en coma flotante es 0 ciclos):
Tmejora_fp=(NI*0.2)*4*(Tciclo)+(NI*0.1)*3*(Tciclo)+(NI*0.25)*6*(Tciclo)+(NI*0.15)*3*(Tciclo)+(NI*0.3)*3*(Tciclo)
y por tanto
Smax (1/f) = Tmejora_fp/Tsin_mejora = 0.2*4+0.1*3+0.25*6+0.15*8+0.3*3/0.2*4+0.1*3+0.25*6+0.15*3+0.3*3=
4,7/3,95
Smax1.19
Como se puede comprobar se obtiene lo mismo puesto que (NI*0.25)*3*T ciclo, que es el tiempo mximo que
se puede reducir al acelerar las operaciones de enteros, es igual a (NI*0.15)*5*Tciclo, que es el tiempo
mximo que se puede reducir al acelerar las operaciones de coma flotante.
Ejercicio 3.Un circuito que implementaba una operacin en Top=450 ns. se ha segmentado mediante un
cauce lineal con cuatro etapas de duraccin T1=100 ns., T2=125 ns., T3=125 ns., y T4=100 ns.
respectivamente, separadas por un registro de acoplo que introduce un retardo de 25 ns. (a) Cul es la
8/10/2019 documento-120.pdf
3/49
Prof. responsables: M. Anguita, J. Ortega 3 / 14
Ejercicios del tema 1
mxima ganancia de velocidad posible? Cul es la productividad mxima del cauce? (b) A partir de qu
nmero de operaciones ejecutadas se consigue una productividad igual al 90% de la productividad mxima?
Solucin
Datos del ejercicio:
Cauce del circuito
(a)El circuito se ha segmentado en cuatro etapas separadas por un registro de acoplo con un retardo de
d=25 ns. El tiempo de ciclo del cauce, t, se obtiene a partir de la expresin:
t = max {T1, T2, T3, T4} + d = max{ 100, 125, 125, 100} + 25 ns. = 150 ns
En ese cauce, una operacin tarda un tiempo TLI = 4 * 150 ns. = 600 ns. (tiempo de latencia de inicio) en
pasar por las cuatro etapas del mismo, y la ganancia de velocidad del cauce para n operaciones viene dada
por:
S(n) = Top*n /(TLI+(n-1)*t) = 450*n/(600+(n-1)*150)
El valor mximo de la ganancia de velocidad se obtiene aplicando el lmite cuando n tiende a infinito. Es decir
Smax= limn( Top *n/(TLI+(n-1)*t)) = Top/t = 450/150 = 3
(b)La productividad del cauce es W(n)=n/(TLI+(n-1)*t) = n/(600+(n-1)*150)
La productividad mxima es Wmax=limn(n/(TLI+(n-1)*t))=1/t=1/150 (op*ns-1
) = 6.67 Mop/s.
El valor de n para el que se consigue una productividad igual al 90% de la productividad mxima es:
0.9*(1/150) = n/(600+(n-1)*150) n = (0,9x4+0,9(n-1) n*0.1=(0.9*3)n = 27
Con 27 operaciones se alcanza el 90% de la productividad mxima. La productividad aumentar conforme se
incremente n.
Ejercicio 4.En un procesador sin segmentacin de cauce, determine cul de estas dos alternativas para
realizar un salto condicional es mejor:
ALT1: Una instruccin COMPARE actualiza un cdigo de condicin y es seguida por una instruccin BRANCH
que comprueba esa condicin.
ALT2: Una sola instruccin incluye la funcionalidad de las instrucciones COMPARE y BRANCH.
Hay que tener en cuenta que hay un 20% de saltos condicionales en ALT1; que las instrucciones BRANCH en
ALT1 y COMPARE+BRANCH en ALT2 necesitan 4 ciclos mientras que todas las dems necesitan slo 3; y que
el ciclo de reloj de la ALT1 es un 25% menor que el de la ALT2, dado que en ste caso la mayor funcionalidad
de la instruccin COMPARE+BRANCH ocasiona una mayor complejidad en el procesador.
Solucin
Datos del ejercicio:
25ns
100ns25ns
125ns25ns
125ns25ns
100ns
8/10/2019 documento-120.pdf
4/49
4 / 14 Arquitectura de Computadores
Grado en Ingeniera Informtica. ETSIIT Universidad de Granada
Tiempo de ciclo de ALT1 = 0,75 * Tiempo de ciclo de ALT2 = Tiempo de ciclo de ALT2 0,25 * Tiempo de ciclo
de ALT2
T1
ciclo = T2
ciclo 0,25* T2
ciclo = 0,75* T2
ciclo
ALT1
Instrucciones i ciclos NIi/NI
1
Proporcin (%) ComentariosBRANCH en ALT1 4 0,2 20
RESTO en ALT1 3 0,8 80 Incluye instrucciones COMPARE
TOTAL 100
ALT2
Instrucciones i ciclos NIi/NI1 Proporcin (%) Comentarios
COMPARE+BRANCH en
ALT24 0,2
20*100/80 =
25
ALT2 no tendr aparte las
instrucciones COMPARE, que son un
20% en ALT1
RESTO en ALT2 3 0,6
(80-
20)*100/80 =75
ALT2 no tendr aparte las
instrucciones COMPARE, que son un20% en ALT1
TOTAL 0,8 100NI
2= 0,8 * NI
1(al no tener instr.
COMPARE aparte)
El tiempo de CPU se puede expresar como:
T CPI NI T CPU CICLO= * *
donde CPI es el nmero medio de ciclos por instruccin, NI es el nmero de instrucciones, y T CICLOel tiempo
de ciclo del procesador.
Para la alternativa primeraALT1, se tiene:
CPI(1)=0.2*4+0.8*3=3.2
y por tanto
TCPU(1)=CPI(1)*NI(1)*Tciclo(1)=3.2*NI(1)*Tciclo(1)= 3.2*NI(1)*0,75*Tciclo(2)=2,4*NI(1)*Tciclo(2)
Para la alternativa primeraALT2, se tiene:
TCPU(2)=CPI(2)*NI(2)*Tciclo(2)=(0.2*4+0.6*3)*NI(1)/NI(2) *NI(2)*Tciclo(2)= 2.6*NI(1)*Tciclo(2)
A continuacin se calcula el tiempo de CPU para la segunda alternativa,ALT2, que se expresar en trminos
del nmero de instrucciones y del tiempo de ciclo de la alternativaALT1.
Por una parte, se tiene que como enALT2no se ejecutan instrucciones COMPARE, se ejecutarn:
- 0.2 NI(1)instrucciones BRANCH deALT1que ahora sern BRANCH+COMPARE
- 0.6 NI(1) instrucciones que quedan al restar a las 0.8 NI(1) de ALT1 las 0.2NI(1) instrucciones
COMPARE (ya que haba una por cada BRANCH y se tenan 0.2 NI(1)
As, el nmero de instrucciones que quedan enALT2son
NI(2) = 0.2NI(1) + 0.6NI(1) = 0.8NI(1)
y por lo tanto el valor de CPI(2)es:
8/10/2019 documento-120.pdf
5/49
Prof. responsables: M. Anguita, J. Ortega 5 / 14
Ejercicios del tema 1
CPINI NI
NI( )
. * ( ) * . * ( ) *
. * ( )
. .
. .2
0 2 1 4 0 6 1 3
0 8 1
0 8 18
0 8 3 25=
+
=
+
=
Adems, se tiene que el ciclo de reloj de ALT2es ms largo que el de ALT1. Concretamente, se dice que el
ciclo de ALT1 es un 25% menor que el de ALT2, lo que implica que:
TCICLO(1) = 0.75*TCICLO(2)
TCICLO(2) = 1.33*TCICLO(1)
Sustituyendo NI(2), CPI(2), y TCICLO(2)en la expresin de TCPU(2)se tiene que:
T NI T NI T CPU CICLO CICLO( ) . *( . * ( )) *( . * ( )) . * ( ) * ( )2 3 25 0 8 1 133 1 3458 1 1= =
As, como TCPU(1) < TCPU(2) se tiene que ALT2 no mejora a la ALT1. Es decir, aunque un repertorio con
instrucciones ms complejas puede reducir el nmero de instrucciones de los programas, reduciendo el
nmero de instrucciones a ejecutar, esto no tiene que suponer una mejora de prestaciones si al implementar
esta opcin la mayor complejidad del procesador lo hace algo ms lento.
Ejercicio 5.
Qu ocurrira en el problema anterior si el ciclo de reloj fuese nicamente un 10% mayor para
la ALT2?
Solucin
Como en el problema anterior, para la primera alternativa, ALT1, se tiene:
T NI T CPU CICLO( ) . * ( ) * ( )1 3 2 1 1=
Para la segunda alternativa, se tiene tambin que
NI(2) = 0.2NI(1) + 0.6NI(1) = 0.8NI(1)
y que CPI(2)es:
CPINI NI
NI( )
. * ( ) * . * ( ) *
. * ( )
. .
. .2
0 2 1 4 0 6 1 3
0 8 1
0 8 18
0 8 3 25=
+
=
+
=
No obstante, como ahora el tiempo de ciclo deALT2es un 10% mayor que el de laALT1se cumple que:
TCICLO(2) = 1.10*TCICLO(1)
y sustituyendo,
T NI T NI T CPU CICLO CICLO( ) . *( . * ( )) * ( . * ( )) . * ( ) * ( )2 3 25 0 8 1 110 1 286 1 1= =
As, ahora TCPU(2) < TCPU(1)y por lo tanto, la segunda alternativa s que es mejor que la primera. Es decir, elmismo planteamiento que antes no mejoraba la situacin de partida ahora s lo consigue. Slo ha sido
necesario que el aumento del ciclo de reloj que se produce al hacer un diseo ms complejo del procesador
sea algo menor.
La situacin reflejada en estos dos ejercicios (4 y 5) pone de manifiesto la necesidad de estudiar la
arquitectura del computador desde un enfoque cuantitativo, y no slo teniendo en cuenta razonamientos
que pueden ser correctos, pero que pueden llevar a resultados finales distintos segn el valor de las
magnitudes implicadas.
Ejercicio 6.Considere un procesador no segmentado con una arquitectura de tipo LOAD/STORE en la que las
operaciones slo utilizan como operandos registros de la CPU. Para un conjunto de programas
8/10/2019 documento-120.pdf
6/49
6 / 14 Arquitectura de Computadores
Grado en Ingeniera Informtica. ETSIIT Universidad de Granada
representativos de su actividad se tiene que el 43% de las instrucciones son operaciones con la ALU (3 CPI),
el 21% LOADs (4 CPI), el 12% STOREs (4 CPI) y el 24% BRANCHs (4 CPI).
Adems, un 25% de las operaciones con la ALU utilizan operandos en registros, que no se vuelven a utilizar.
Se mejoraran las prestaciones si, para sustituir ese 25% de operaciones se aaden instrucciones con un
dato en un registro y otro en memoria, teniendo en cuenta que para ellas el valor de CPI es 4 y que
ocasionaran un incremento de un ciclo en el CPI de los BRANCHs, pero que no afectan al ciclo de reloj?
Solucin
Datos del ejercicio:
Alternativa 1
Ii1 CPIi
1 Fraccin fi
1(NIi
1=fi
1*NI
1) Comentarios
LOAD 4 0,21
STORE 4 0,12
ALU 3 0,4325 % inst. que usan opernados en registros que no se
vuelven a utilizar
BR 4 0,24TOTAL 1
Alternativa 2
Ii2 CPIi
2 Fraccin fi(NIi
2=fi
2*NI
1) Comentarios
LOAD 4 0,21 - 0,25 * 0,43 = 0,1025El 25 % de 43% desaparece al usarse ese mismo nmero de
operaciones con la ALU que acceden a memoria
STORE 4 0,12
ALU r-r 3 0,75 * 0,43 = 0,3225
ALU r-m 4 0,25 * 0,43 = 0,1075 25% de las operaciones con la ALU; es decir el 25% del 43%
BR 5 0,24
TOTAL 0,8925 Es decir, NI2 = 0,8925 * NI1
En primer lugar se calcula el tiempo de CPU para la situacin inicial. Para ello, se tiene que:
CPI(1)=0.43*3+0.21*4+0.12*4+0.24*4 = 1.29 + 0.57*4 = 1.29 + 2.28 = 3.57
y, por tanto:
T CPI NI T NI T CPU CICLO CICLO( ) ( ) * ( ) * ( ) . * ( ) * ( )1 1 1 1 357 1 1= =
TCPU(1)=CPI(1)*NI(1)*Tciclo=3.57*NI(1)*Tciclo
En segundo lugar se calcula el tiempo de CPU para la alternativa 2. Para ello, se tiene que:
CPI(2)=[0.3225*3+(0.12+0,1025+0,1075)*4+5*0,24]*NI(1)/NI(2)= (0,9675+0,33*4+0,24*5)*NI(1)/NI(2) =
(0.9675+1,32+1,2)*NI(1)/NI(2)= 3.4875*NI(1)/NI(2)
y, por tanto:
TCPU(2)=CPI(2)*NI(2)*Tciclo=3.4875*NI(1)/NI(2) *NI(2)*Tciclo= 3.4875*NI(1)*Tciclo
En la Tabla anterior para Alternativa 2 se muestra que, al introducir las nuevas instrucciones de operacin
con la ALU con uno de los operandos en memoria:
- Se reduce el 25% de las 0.43*NI(1) instrucciones de operacin con la ALU y operandos en registros a
las que las nuevas instrucciones sustituyen.
- Se reduce en 0.25*0.43*NI(1) el nmero de LOADs, ya que segn se indica en el enunciado, esos
LOADs slo estn en el programa para cargar uno de los operandos de las operaciones con la ALU,que no se vuelven a utilizar nunca ms.
8/10/2019 documento-120.pdf
7/49
Prof. responsables: M. Anguita, J. Ortega 7 / 14
Ejercicios del tema 1
- Hay que contabilizar las 0.25*0.43*NI(1) nuevas instrucciones de operacin con la ALU que se
introducen en el repertorio (y que sustituyen a las operaciones con la ALU y operandos en registros).
- Como resultado, al sumar todas las instrucciones que se tienen en la nueva situacin, el nmero
total de instrucciones se reduce (lgicamente, ya que se han ahorrado instrucciones LOADs)., siendo
igual a
NI(2)=0.8925*NI(1)
Teniendo en cuenta la nueva distribucin de instrucciones y sus nuevos CPIs, se tiene que:
CPI( ). . * .
. *
. . * .
. *
. * .
. *
.
. *
.
. *2
0 43 0 25 0 43
08925 3
0 21 0 25 0 43
08925 4
0 2 5 0 43
08925 4
0 12
08925 4
0 24
08925 5=
+
+ + + =
= 3.908
Como el tiempo de ciclo no vara se tiene que:
T CPI NI T NI T NI T CPU CICLO CICLO CICLO( ) ( ) * ( ) * ( ) . * . * ( ) * ( ) . * ( ) * ( )2 2 2 2 3 908 0 8925 1 1 3 488 1 1= = =
Como se puede ver, en este caso, TCPU(1) > TCPU(2), y por lo tanto se mejoran las prestaciones, pero si elporcentaje de instrucciones sustituidas fuese un 20% en lugar de un 25%, en ese caso, se puede ver que
CPI(2) = 3.9302
NI(2) = 0.914*NI(1)
y, por tanto:
T CPI NI T NI T NI T CPU CICLO CICLO CICLO( ) ( ) * ( ) * ( ) . * . * ( ) * ( ) . * ( ) * ( )2 2 2 2 3 9302 0 914 1 1 3 59 1 1= = =
Ahora, en cambio, la segunda opcin no mejora la primera. Como conclusin, se puede indicar que una
determinada decisin de diseo puede suponer una mejora en el rendimiento del computador
correspondiente segn sean las caractersticas de las distribuciones de instrucciones en los programas que
constituyen la carga de trabajo caracterstica del computador.
Por tanto, queda clara tambin la importancia que tiene el proceso de definicin de conjuntos de
benchmarkspara evaluar las prestaciones de los computadores, y las dificultades que pueden surgir para
que los fabricantes se pongan de acuerdo en aceptar un conjunto de benchmarks estndar.
Ejercicio 7.Se ha diseado un compilador para la mquina LOAD/STORE del problema anterior. Ese
compilador puede reducir en un 50% el nmero de operaciones con la ALU, pero no reduce el nmero de
LOADs, STOREs, y BRANCHs. Suponiendo que la frecuencia de reloj es de 50 Mhz. Cul es el nmero de
MIPS y el tiempo de ejecucin que se consigue con el cdigo optimizado? Comprelos con los
correspondientes del cdigo no optimizado.
Solucin
Datos del ejercicio:
Alternativa 1
Ii1 CPIi
1 Fraccin fi
1(NIi
1=fi
1*NI
1)
LOAD 4 0,21
STORE 4 0,12
ALU 3 0,43
BR 4 0,24
TOTAL 1
8/10/2019 documento-120.pdf
8/49
8 / 14 Arquitectura de Computadores
Grado en Ingeniera Informtica. ETSIIT Universidad de Granada
Alternativa 2
Ii2 CPIi
2 Fraccin fi(NIi
2=fi
2*NI
1) Comentarios
LOAD 4 0,21
STORE 4 0,12
ALU r-r 3 0,5 * 0,43 = 0,215 Se reducen las instrucciones que usan la ALU en un 50%
BR 4 0,24
TOTAL 0,785 Es decir, NI2
= 0,785 * NI1
En la situacin inicial del problema anterior se tena que
T CPI NI T NI T CPU CICLO CICLO( ) ( ) * ( ) * ( ) . * ( ) * ( )1 1 1 1 357 1 1= =
TCPU(1)=CPI(1)*NI(1)*Tciclo=3.57*NI(1)*Tciclo
y, por lo tanto
MIPSNI
T sg
NI
CPI NI T
f MHz
CPI MIPS
CPU CICLO
( )( )
( )( . ) *
( )
( ( ) * ( ) * ( )) *
( )
( ) . .1
1
1 10
1
1 1 1 10 1
50
357 14 005
6 6= = = = =
TCPU(1)=CPI(1)*NI(1)*Tciclo=3.57*NI(1)*Tciclo
En segundo lugar se calcula el tiempo de CPU para la alternativa 2. Para ello, se tiene que:
CPI(2)=[0.215*3+(0.21+0,12+0,24)*4]*NI(1)/NI(2)= (0,645+0.57*4)*NI(1)/NI(2) = (0.645+2.28)*NI(1)/NI(2)=
2.925*NI(1)/NI(2)
y, por tanto:
TCPU(2)=CPI(2)*NI(2)*Tciclo=2.925*NI(1)/NI(2) *NI(2)*Tciclo= 2.925*NI(1)*Tciclo
MIPS(2) = NI(2) / (CPI(2)*NI(2)*Tciclo*106)=f(MHz)/CPI(2) = 50 * 0.785/ 2.925 MIPS = 13,4188 MIPS
En la Tabla de la Alternativa 2 se muestra que se reduce el nmero de operaciones con la ALU a la mitad, y
que, por tanto, tambin se reduce el nmero total de instrucciones a ejecutar, NI(2):
NI(2)=0.785*NI(1)
Teniendo en cuenta la nueva distribucin de instrucciones y sus nuevos CPIs, se tiene que:
CPI( ). . /
. *
.
. *
.
. *
.
. * .2
0 43 0 43 2
0785 3
0 21
0785 4
012
0785 4
0 24
0785 4 3 72=
+ + + =
Como el tiempo de ciclo no vara se tiene que:
T CPI NI T NI T NI T CPU CICLO CICLO CICLO( ) ( ) * ( ) * ( ) . * . * ( ) * ( ) . * ( ) * ( )2 2 2 2 3 72 0 785 1 1 2 92 1 1= = =
El nmero de MIPS para este caso es:
MIPSNI
T sg
NI
CPI NI T
f MHz
CPI MIPS
CPU CICLO
( )( )
( )( .) *
( )
( ( ) * ( ) * ( )) *
( )
( ) . .2
2
2 10
2
2 2 2 10 2
50
3 72 13446 6= = = = =
Como se puede ver, se consigue una reduccin de tiempo de ejecucin (T CPU(2) es un 21% menor que
TCPU(1)), pero sin embargo, el nmero de MIPS para la segunda opcin es menor. Se tiene aqu un ejemplo de
que los MIPS dan una informacin inversamente proporcional a las prestaciones. La razn de esta situacin,
en este caso, es que se ha reducido el nmero de las instrucciones que tenan un menor valor de CPI. As, se
incrementan las proporciones de las instrucciones ms lentas en el segundo caso (por eso crece el valor de
CPI), y claro, el valor de los MIPS se reduce. No obstante, hay que tener en cuenta que aunque las
instrucciones que se ejecutan son ms lentas, hay que ejecutar un nmero mucho menor de instrucciones, yal final, el tiempo se reduce.
8/10/2019 documento-120.pdf
9/49
Prof. responsables: M. Anguita, J. Ortega 9 / 14
Ejercicios del tema 1
Ejercicio 8.
Ejercicio 9.
Ejercicio 10.Suponga que en el cdigo siguiente N=109 , y que a[] es un array de nmeros de 32 bits encoma flotante y b es otro nmero de 32 bits en coma flotante:
for (i=0; i
8/10/2019 documento-120.pdf
10/49
10 / 14 Arquitectura de Computadores
Grado en Ingeniera Informtica. ETSIIT Universidad de Granada
Ejercicio 11.
2 Cuestiones
Cuestin 1.Indique cul es la diferencia fundamental entre una arquitectura CC-NUMA y una arquitectura
SMP.
Solucin.
Ambos, SMP y CC-NUMA, son multiprocesadores, es decir, comparten el espacio de direcciones fsico.
Tambin en ambos se mantiene coherencia entre caches de distintos procesadores (CC-Cache-Coherence).
En un SMP (Symmetric Multiprocessor) la memoria se encuentra centralizada en el sistema a igual distancia
(latencia) de todos los procesadores mientras que, en un CC-NUMA (Cache-Coherence Non Uniform Memory
Access), cada procesador tiene fsicamente cerca un conjunto de sus direcciones de memoria porque los
mdulos de memoria estn fsicamente distribuidos entre los procesadores y, por tanto, los mdulos noestn a igual distancia (latencia) de todos los procesadores.
La memoria centralizada del SMP hace que el tiempo de acceso a una direccin de memoria en un SMP sea
igual para todos los procesadores y el tiempo de acceso a memoria de un procesador sea el mismo
independientemente de la direccin a la que se est accediendo; por estos motivos se denomina
multiprocesador simtrico (Symmetric Multiprocessor) o UMA (Uniform Memory Access).
Los mdulos de memoria fsicamente distribuidos entre los procesadores de un CC-NUMA hacen que el
tiempo de acceso a memoria dependa de si el procesador accede a una direccin de memoria que est en la
memoria fsica que se encuentra en el nodo de dicho procesador (cercana, por tanto, al procesador que
accede) o en la memoria fsica de otro nodo. Por este motivo el acceso no es uniforme o simtrico y recibe el
nombre de NUMA.
Cuestin 2.Cundo dira que un computador es un multiprocesador y cundo que es un multicomputador?
Solucin. Ser un multiprocesador si todos los procesadores comparten el mismo espacio de direcciones
fsico y ser un multicomputador si cada procesador tiene su espacio de direcciones fsico propio.
Cuestin 3.Un CC-NUMA escala ms que un SMP? Por qu?
Solucin. S, un CC-NUMA escala ms que un SMP, porque al aadir procesadores al clculo el incremento
en el tiempo de acceso a memoria medio aumenta menos que en un SMP si el sistema operativo, el
compilador y/o el programador se esfuerzan en ubicar en la memoria cercana a un procesador la carga de
trabajo que va a procesar. La menor latencia media se debe a un menor nmero de conflictos en la red en el
acceso a datos y a la menor distancia con el mdulo de memoria fsico al que se accede. Al aumentar menos
la latencia se puede conseguir un tiempo de respuesta mejor en un CC-NUMA que en un SMP al ejecutar un
cdigo paralelo o mltiples cdigos secuenciales a la vez.
Cuestin 4.Indique qu niveles de paralelismo implcito en una aplicacin puede aprovechar un PC con un
procesador de 4 cores, teniendo en cuenta que cada core tiene unidades funcionales SIMD (tambinllamadas unidades multimedia) y una microarquitectura segmentada y superscalar. Razone su respuesta.
8/10/2019 documento-120.pdf
11/49
Prof. responsables: M. Anguita, J. Ortega 11 / 14
Ejercicios del tema 1
Solucin.
Paralelismo a nivel de operacin. Al ser una arquitectura con paralelismo a nivel de instruccin por tener una
arquitectura segmentada y superescalar, puede ejecutar operaciones en paralelo, luego puede aprovechar el
paralelismo a nivel de operacin.
Paralelismo a nivel de bucle (paralelismo de datos). Las operaciones realizadas en las iteraciones del bucle
sobre vectores y matrices se podran implementar en las unidades SIMD de los cores, lo que reducira el
nmero de iteraciones de los bucles. Adems las iteraciones de los bucles, si son independientes, se podran
repartir entre los 4 cores.
Paralelismo a nivel de funcin. Las funciones independientes se podran asignar a cores distintos para que se
puedan ejecutar a la vez.
Paralelismo a nivel de programa. Los programas del mismo o distinto usuario se pueden asignar a distintos
cores para as ejecutarlos al mismo tiempo.
Cuestin 5.Si le dicen que un ordenador es de 20 GIPS puede estar seguro que ejecutar cualquier
programa de 20000 instrucciones en un microsegundo?
Solucin. Los MIPS se definen como el nmero de instrucciones que puede ejecutar un procesador (en
millones) divididos por el tiempo que tardan en ejecutarse.
MIPSNumero de Instrucciones
tiempo sg=
_ _
( . ) *106
Los MIPS suelen utilizarse como medida de las prestaciones de un procesador, pero realmente slo
permiten estimar la velocidad pico del procesador, que solo permitira comparar procesadores con el mismo
repertorio de instrucciones en cuanto a sus velocidades pico. Esto se debe a que esta medida
- No tiene en cuenta las caractersticas del repertorio de instrucciones de procesador. Se da el mismo
valor a una instruccin que realice una operacin compleja que a una instruccin sencilla.
- Pueden tenerse valores de MIPS inversamente proporcionales a la velocidad del procesador. Si un
procesador tiene un repertorio de instrucciones de tipo CISC que permite codificar un algoritmo con,
por ejemplo, 1000 instrucciones, y otro con un repertorio de tipo RISC lo codifica con 2000, si el
primero tarda 1 microsegundo y el segundo 1.5 microsegundos, tendremos que el primer
procesador tiene 1000 MIPS y el segundo 1333 MIPS. Por tanto, si nos fijamos en los MIPS, el
segundo procesador ser mejor que el primero, aun precisando un 50% ms de tiempo que el
primero, para resolver el mismo problema.
De ah que incluso se haya dicho que MIPS significa Meaningless Information of Processor Speed(informacin sin sentido de la velocidad del procesador).
En relacin a la pregunta que se plantea, la respuesta puede tener en cuenta dos aspectos:
- El nmero de instrucciones que constituyen un programa (nmero esttico de instrucciones) puede
ser distinto del nmero de instrucciones que ejecuta el procesador finalmente (nmero dinmico de
instrucciones), ya que puede haber instrucciones de salto, bucles, etc. que hacen que ciertas
instrucciones del cdigo se ejecuten ms de una vez, y otras no se ejecuten nunca. Si la pregunta, al
hacer referencia al nmero de instrucciones, se refiere al nmero esttico, la respuesta es que NO se
puede estar seguro puesto que puede que al final no se ejecuten 20000 millones de instrucciones.
- Si el repertorio de instrucciones contiene instrucciones que tardan en ejecutarse tiempos diferentes,
para que el programa tardase el mismo tiempo es preciso que se ejecutase el mismo nmero de
instrucciones y del mismo tipo (en cuanto a tiempo de ejecucin de cada una). En este caso,
8/10/2019 documento-120.pdf
12/49
12 / 14 Arquitectura de Computadores
Grado en Ingeniera Informtica. ETSIIT Universidad de Granada
tambin, la respuesta es NO.
Cuestin 6.Aceptara financiar/embarcarse en un proyecto en el que se plantease el diseo e
implementacin de un computador de propsito general con arquitectura MISD? (Justifique su respuesta).
Solucin:El tipo de procesamiento que realiza un procesador MISD puede implementarse en un procesador
MIMD con la sincronizacin correspondiente entre los procesadores del computador MIMD para que los
datos vayan pasando adecuadamente de un procesador a otro (definiendo un flujo nico de datos que pasan
de procesador a procesador). Por esta razn un computador MISD no tiene mucho sentido como
computador de propsito general. Sin embargo, puede ser til un diseo MISD para un dispositivo de
propsito especfico que slo tiene que ejecutar una aplicacin que implica un procesamiento en el que los
datos tienen que pasar por distintas etapas en las que sufren ciertas transformaciones que pueden
programarse (en cada uno de los procesadores). La especificidad del diseo puede permitir generar diseos
muy eficientes desde el punto de vista del consumo, de la complejidad hardware, etc.
Cuestin 7.Deduzca la ley de Amdahl para la mejora de la velocidad de un procesador suponiendo que hay
una probabilidad f de no utilizar un recurso del procesador cuya velocidad se incrementa en un factor p.
Solucin: El tiempo necesario para ejecutar un programa en el procesador sin la mejora es igual a:
Tsin_mejora=f*Tsin_mejora+(1-f)*Tsin_mejora
donde f*Tsin_mejoraes el tiempo que no podra reducirse al aplicar la mejora, y (1-f)*T sin_mejoraes el tiempo que
podra reducirse como mximo en un factor igual a p al aplicar la mejora. Por tanto, el tiempo al aplicar la
mejora sera:
Tcon_mejoraf*Tsin_mejora+((1-f)*Tsin_mejora)/p
Segn esto, la ganancia de velocidad que se podra conseguir sera:
S = Tsin_mejora/Tcon_mejoraTsin_mejora/( f*Tsin_mejora+((1-f)*Tsin_mejora)/p) = 1/(f + (1-f)/p) = p/(1+f(p-1))
y as llegamos a la expresin que se utiliza para describir la Ley de Amdahl: S p/(1+f(p-1))
Cuestin 8.Es cierto que para una determinada mejora realizada en un recurso se observa
experimentalmente que, al aumentar el factor de mejora, llega un momento en que se satura el incrementode velocidad que se consigue? (Justifique la respuesta)
Solucin: Para responder a esta pregunta recurrimos a la ley de Amdahl, que marca un lmite superior a la
mejora de velocidad. Como se tiene que S p/(1+f(p-1)), donde p es el factor de mejora y f la fraccin de
tiempo sin la mejora en el que dicha mejora no puede aplicarse, se puede calcular la derivada de p/(1+f(p-1))
con respecto a p, y ver qu pasa cuando cambia p. As:
d(p/(1+f(p-1))/dp = ((1+f(p-1))-pf)/(1+f(p-1))2= (1-f)/ (1+f(p-1))
2
y como puede verse, a medida que aumenta p el denominador se va haciendo mayor, y como (1-f) se
mantiene fijo, la derivada tiende a cero. Eso significa que la pendiente de la curva que describe la variacin
de p/(1+f(p-1)) con p va hacindose igual a cero y por lo tanto no aumenta la ganancia de velocidad: se
8/10/2019 documento-120.pdf
13/49
Prof. responsables: M. Anguita, J. Ortega 13 / 14
Ejercicios del tema 1
satura, o lo que es lo mismo, llega a una asntota que estar situada en 1/f (que es al valor al que tiende
p/(1+f(p-1) cuando p tiende a infinito).
Cuestin 9.
Es cierto que la cota para el incremento de velocidad que establece la ley de Amdahl crece a
medida que aumenta el valor del factor de mejora aplicado al recurso? (Justifique la respuesta).
Solucin: La respuesta a esta pregunta se deduce de la misma expresin de la derivada de la cota que
establece la ley de Amdahl, calculada al responder la cuestin 4:
d(p/(1+f(p-1))/dp = ((1+f(p-1))-pf)/(1+f(p-1))2= (1-f)/ (1+f(p-1))
2
dado que (1-f) es positivo (solo en el peor de los casos, si no se pudiera aplicar el factor de ganancia a
ninguna parte del programa, tendramos que (1-f)=0 y no se obtendra ninguna ganancia de velocidad), y
puesto que (1+f(p-1))2siempre es positivo, la derivada es positiva. Eso significa que 1+f(p-1) crece al crecer p.
Lo que ocurre es que, tal y como se ha visto en la cuestin 4, este crecimiento es cada vez menor (tiende a
0).
Cuestin 10.Qu es mejor, un procesador superescalar capaz de emitir cuatro instrucciones por ciclo, o un
procesador vectorial cuyo repertorio permite codificar 8 operaciones por instruccin y emite una instruccin
por ciclo? (Justifique su respuesta).
Solucin:Considrese una aplicacin que se codifica con N instrucciones de un repertorio de instrucciones
escalar (cada instruccin codifica una operacin). La cota inferior para el tiempo que un procesador
superescalar podra tardar en ejecutar ese programa sera
Tsuperescalar= (N*Tciclo_superesc)/4
Un procesador vectorial ejecutara un nmero de instrucciones menor puesto que su repertorio de
instrucciones permitira codificar hasta ocho operaciones iguales (sobre datos diferentes) en una instruccin.
Si suponemos que la aplicacin permite que todas las operaciones que hay que ejecutar se puedan
empaquetar en instrucciones vectoriales, el procesador vectorial tendra que ejecutar N/8 instrucciones.
Por tanto, considerando tambin que el procesador vectorial consigue terminar instrucciones segn su
velocidad pico (como supusimos en el caso del superescalar), la cota inferior para el tiempo que tarda la
ejecucin del programa en el procesador vectorial sera:
Tvectorial= (N/8)*Tciclo_vectorial/1
Por tanto
Tsuperescalar/ Tvectorial= 8*Tciclo_superesc/4*Tciclo_vectorial = 2 * Tciclo_superesc/Tciclo_vectorial
Segn esto, si los dos procesadores funcionan a la misma frecuencia, el procesador vectorial podra ser
mejor (siempre y cuando las hiptesis que se estn considerando de que estn procesando instrucciones
segn su mximo rendimiento se puedan considerar suficientemente aproximada a la realidad).
No obstante, hay que tener en cuenta que usualmente, los procesadores superescalares han sido los que
ms rpidamente han incorporado las mejoras tecnolgicas, y normalmente, los procesadores
superescalares funcionan a frecuencias ms altas que los procesadores vectoriales contemporneos. En el
ejemplo, si la frecuencia del superescalar fuera ms del doble de la del vectorial, sera mejor utilizar unprocesador superescalar.
8/10/2019 documento-120.pdf
14/49
14 / 14 Arquitectura de Computadores
Grado en Ingeniera Informtica. ETSIIT Universidad de Granada
Adems, hay que tener en cuenta que para que los procesadores vectoriales sean eficientes (se puedan
admitir las hiptesis en cuanto a codificacin de las operaciones y funcionamiento segn la velocidad pico)
es necesario que el programa tenga un alto grado de paralelismo de datos (son procesadores ms
especficos que los superescalares). Por eso, para dar una respuesta ms precisa habra que conocer ms
detalles de la carga de trabajo que se piensa ejecutar en los procesadores.
8/10/2019 documento-120.pdf
15/49
2 curso / 2 cuatr.
Grado en
Ing. Informtica
Arquitectura de Computadores.
Algunos ejercicios resueltos
Tema 2. Programacin paralela
Profesores responsables: Mancia Anguita, Julio Ortega
Licencia Creative Commons
1 Ejercicios
Ejercicio 1. Un programa tarda 40 s en ejecutarse en un multiprocesador. Durante un 20% de ese tiempo se
ha ejecutado en cuatro procesadores (core); durante un 60%, en tres; y durante el 20% restante, en un
procesador (consideramos que se ha distribuido la carga de trabajo por igual entre los procesadores que
colaboran en la ejecucin en cada momento, despreciamos sobrecarga). Cunto tiempo tardara en
ejecutarse el programa en un nico procesador?Cul es la ganancia en velocidad obtenida con respecto al
tiempo de ejecucin secuencial?Y la eficiencia?
Solucin
Datos del ejercicio:
En el grfico de la derecha se representan los datos del
ejercicio. Estos datos son la fraccin del tiempo de
ejecucin paralelo (Tp) que supone el cdigo no
paralelizable (20% de Tp ,
es decir, 0,2*Tp), la fraccin que
supone el cdigo paralelizable en 3 procesadores (0,6*Tp) y
la que supone el cdigo paralelizable en 4 procesadores
(0,2*Tp). Al distribuirse la carga de trabajo por igual entre
los procesadores utilizados en cada instante, los trozos
asignados a 3 procesadores suponen todos el mismo
tiempo (por eso se han dibujado en el grfico de igual
tamao) e, igualmente, los trozos asignados a 4
procesadores tambin suponen todos el mismo tiempo.
Tiempo de ejecucin secuencial, TS?:
Los trozos de cdigo representados en la grfica anterior se deben ejecutar secuencialmente, es decir,
uno detrs de otro, como se ilustra el grfico siguiente:
TS ?
1 2 3 1 2 3 4
0,2*T 0,6*T 0,2*T0,2*T
( ) ssTTTTTT PPPPPS 112408,28,28,08,12,02,046,032,0 ===++=++=
Ganancia en velocidad, S(p)?:
20%
3
TP
Procesadores
1 1
2
3
44
1
2
3
60% 20%
Tiempo
paralelo
8/10/2019 documento-120.pdf
16/49
2 / 12 Arquitectura de Computadores
Grado en Ingeniera Informtica
( )
( )
( ) 8,2
4
48,2
4)4( =
==
P
P
P
S
T
T
T
TS
Eficiencia, E(p)?:
7,04
8,2
4
)4(S
p
)p(S
)4(E ====
Ejercicio 2.
Ejercicio 3.Cul es fraccin de cdigo paralelo de un programa secuencial que, ejecutado en paralelo en 8
procesadores, tarda un tiempo de 100 ns, durante 50ns utiliza un nico procesador y durante otros 50 ns
utiliza 8 procesadores (distribuyendo la carga de trabajo por igual entre los procesadores)?
Solucin
Datos del programa:
50nsTP
Procesadores
1 1
3
5
7
8
50ns
Tiempo
paralelo
2
4
6
8
Fraccin de cdigo paralelizable del programa secuencial, fP?:
50ns
TS
1 3 5 7
50ns
2 4 6 8
fP
9
8
50850
508508=
+
=
=
nsns
ns
T
nsf
Sp
Ejercicio 4.
Ejercicio 5.
Ejercicio 6.
Ejercicio 7.
Se quiere paralelizar el siguiente trozo de cdigo:{Clculos antes del bucle}for( i=0; i
8/10/2019 documento-120.pdf
17/49
Prof. responsables: M. Anguita, J. Ortega 3 / 12
Ejercicios del tema 2
constante), los procesos se comunican y se sincronizan, lo que supone un tiempo k2p(k2constante); k1p+ k2p
constituyen la sobrecarga.
(a)
Obtener una expresin para el tiempo de ejecucin paralela del trozo de cdigo en pprocesadores
(Tp).
(b)Obtener una expresin para la ganancia en velocidad de la ejecucin paralela con respecto a una
ejecucin secuencial (Sp).(c) Tiene el tiempo Tpcon respecto a puna caracterstica lineal o puede presentar algn mnimo? Por
qu? En caso de presentar un mnimo, para qu nmero de procesadorespse alcanza?
Solucin
Datos del ejercicio:
{Clculos antes del bucle}
for( i=0; i
8/10/2019 documento-120.pdf
18/49
4 / 12 Arquitectura de Computadores
Grado en Ingeniera Informtica
0
50
100
150
200
250
300
2 4 6 810
12
14
16
18
20
22
24
26
28
30
p
Tiempoparalelo
Tiempo paralelo
Tiempo clculo
Tiempo sobrecarga
TP(p)= 4 + 200/p 3 + 4p_______
p=200*3/4 = 12,25
0
50
100
150
200
250
300
2 3 4 5 6 7 8 910
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
p
Tiempoparale
lo
Tiempo paralelo
Tiempo clculo
Tiempo sobrecarga
TP(p)= 4 + 50/p 30 + 4p
______
p= 50*30/4 = 19,36
Figura 3.Tiempo de ejecucin paralelo para un caso
particular en el que w=200, ties 3 unidades detiempo, tson 4 unidades de tiempo y kson 4
unidades de tiempo. El mnimo se alcanza parap=12
Figura 4.Tiempo de ejecucin paralelo para un caso particular
en el que w=50, ties 30 unidades de tiempo, tson 4unidades de tiempo y kson 4 unidades de tiempo. El
mnimo se alcanza parap=17. Aqu el efecto del
redondeo se ve ms claramente que en la Figura 3
0
50
100
150
200
250
300
2 3 4 5 6 7 8 9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
p
Tiempoparalelo
Tiempo paralelo
Tiempo clculo
Tiempo sobrecarga
TP(p)= 4 + 50/p 20 + 4p
______p=50*20/4 = 15,81
0
10 0
20 0
30 0
40 0
50 0
60 0
2 3 4 5 6 7 8 9
1
0
1
1
1
2
1
3
1
4
1
5
1
6
1
7
1
8
1
9
2
0
2
1
2
2
2
3
2
4
2
5
2
6
2
7
2
8
2
9
3
0
p
Tiem
poparalelo
Tiempo paralelo
Tiempo clculo
Tiempo sobrecarga
TP(p)= 4 + 30/p 32 + 15p
_______p=30*32/15 = 8
Figura 5.
Tiempo de ejecucin paralelo para un caso
particular en el que w=50, ties 20 unidades de
tiempo, tson 4 unidades de tiempo y kson 4
unidades de tiempo. El mnimo se alcanza parap=17.
Figura 6.
Tiempo de ejecucin paralelo para un caso particular
en el que w=30, ties 32 unidades de tiempo, tson 4
unidades de tiempo y kson 15 unidades de tiempo. El
mnimo se alcanza parap=10.
Se puede encontrar el mnimo analticamente igualando a 0 la primera derivada de Tp. De esta forma se
obtiene los mximos y mnimos de una funcin continua. Para comprobar si en un punto encontrado de esta
forma hay un mximo o un mnimo se calcula el valor de la segunda derivada en ese punto. Si, como
resultado de este clculo, se obtiene un valor por encima de 0 hay un mnimo, y si, por el contrario, se
obtiene un valor por debajo de 0 hay un mximo. Para realizar el clculo se debe eliminar el redondeo de la
expresin (1) (ms abajo se comentar la influencia del redondeo en el clculo del mnimo):
8/10/2019 documento-120.pdf
19/49
Prof. responsables: M. Anguita, J. Ortega 5 / 12
Ejercicios del tema 2
)2(0),('
),(
22 k
twpkt
p
wkt
p
wwpT
pktp
wtwpT
i
iiP
iP
==+=
++=
El resultado negativo de la raz se descarta. En cuanto al resultado positivo, debido al redondeo, habr que
comprobar para cul de los naturales prximos al resultado obtenido (incluido el propio resultado si es un
nmero natural) se obtiene un menor tiempo. Debido al redondeo hacia arriba de la expresin (1), se
deberan comprobar necesariamente:
1.
El natural pmenor o igual y ms alejado al resultado p generado con (2) para el que
'p
w =
p
w
(obsrvese, que en el ejemplo de la Figura 4, aunque de (2) se obtiene 19,36, el pcon menor tiempo
es 17 debido al efecto del redondeo) y
2. El natural pmayor y ms prximo al pgenerado con (2) para el que
'p
w =
p
w -1 (obsrvese, que en
el ejemplo de la Figura 5, aunque de (2) se obtiene 15,81, el pcon menor tiempo es 17 debido al
redondeo).
En cualquier caso, el nmero de procesadores que obtengamos debe ser menor que w(que es el grado de
paralelismo del cdigo).
La segunda derivada permitir demostrar que se trata de un mnimo:
02
02
),(''
),(
34
>
=+
+=
++=
p
tw
p
twpwpT
pktp
wtwpT
ii
P
iP
La segunda derivada es mayor que 0, ya que w, p y ti son mayores que 0; por tanto, hay un mnimo.
Ejercicio 8.
Ejercicio 9.
Se va a paralelizar un decodificador JPEG en un multiprocesador. Se ha extrado para la aplicacin
el siguiente grafo de tareas que presenta una estructura segmentada (o de flujo de datos):
T2T4
T5T1
T3 Salida:Bloquedecodificado de 8x8
pixels
Entrada:Bloque de la
imagen a decodificar(supone 8x8 pixels de
la imagen)
La tareas 1, 2 y 5 se ejecutan
en un tiempo igual a t,
mientras que las tareas 3 y 4
suponen 1,5t
El decodificador JPEG aplica el grafo de tareas de la figura a bloques de la imagen, cada uno de 8x8 pxeles. Si
se procesa una imagen que se puede dividir en nbloques de 8x8 pxeles, a cada uno de esos nbloques se
aplica el grafo de tareas de la figura. Obtenga la mayor ganancia en prestaciones que se puede conseguir
paralelizando el decodificador JPEG en (suponga despreciable el tiempo de comunicacin/sincronizacin): (a)
5 procesadores, y (b) 4 procesadores. En cualquier de los dos casos, la ganancia se tiene que calcular
suponiendo que se procesa una imagen con un total de nbloques de 8x8 pxeles.
Solucin
8/10/2019 documento-120.pdf
20/49
6 / 12 Arquitectura de Computadores
Grado en Ingeniera Informtica
Para obtener la ganancia se tiene que calcular el tiempo de ejecucin en secuencial para un tamao del
problema de nbloques Ts(n)y el tiempo de ejecucin en paralelo para un tamao del problema de ny los p
procesadores indicados en (a), (b) y (c) Tp(p,n).
Tiempo de ejecucin secuencial Ts(n). Un procesador tiene que ejecutar las 5 tareas para cada bloque de
8x8 pxeles. El tiempo que dedica el procesador a cada bloque es de 3t (tareas 1, 2 y 5) + 3 t (tareas 2 y 4) =
6t, luego para n bloques el tiempo de ejecucin secuencial ser el siguiente:
( )tnTS 6=
(a)Tiempo de ejecucin paralelo y ganancia en prestaciones para 5 procesadores Tp(5,n), S(5,n). Cada
tarea se asigna a un procesador distinto, por tanto todas se pueden ejecutar en paralelo (ver asignacin de
tareas a procesadores en la Tabla 1). El tiempo de ejecucin en paralelo en un pipeline consta de dos
tiempos: el tiempo que tarda en procesarse la primera entrada (ver celdas con fondo verde en la tabla) + el
tiempo que tardan cada uno del resto de bloques (entradas al cauce) en terminar. Este ltimo depende de la
etapa ms lenta, que en este caso es la etapa 3 (1,5t frente a t en el resto de etapas).
tnttntnTP
5,135,1)1(5,4),5( +=+=
45,13
6
),5(
)(),5(
+
==
n
p
s
tnt
tn
nT
nTnS La ganancia se aproxima a 4 para n suficientemente
grande.
Tabla 1.Asignacin de tareas a procesadores, ocupacin de las etapas del cauce para los primeros bloques
procesados y tiempo de procesamiento del primer bloque y de los siguientes para 5 procesadores
T2
T4
T5T1
T3
P1 (t) P2 (t)
P4(1,5t)
P3(1,5t)
P5 (t)Asignacin de tareas a 5 procesadores
Etapa 1 (t) Etapa 2 (t) Etapa 3 (1,5t) Etapa 4 (t) Terminado Tiempo procesa.
T1 (procesador
P1)
T2 (procesador
P2)
T3 (procesador P3) y
T4 (procesador P4)
T5 (procesador P5)
0 - Bloque 1 - t
Procesamiento
Bloque 1 (4,5t)
t - Bloque 2 - 2t t - Bloque 1 - 2t
2t - Bloque 3 - 3t 2t- Bloque 2 - 3t 2t - Bloque 1 - 3,5t
3t - Bloque 4 - 4t 3t - Bloque 3 - 4t 3,5t - Bloque 2 - 5t 3,5t - Bloque 1 - 4,5t
4t - Bloque 5 - 5t 4t - Bloque 4 - 5t 5t - Bloque 3 - 6,5t 5t - Bloque 2 - 6t Bloque 1 t + t + 1,5t + t = 4,5t
5t - Bloque 6 - 6t 5t - Bloque 5 - 6t 6,5t - Bloque 4 - 8t 6,5t - Bloque 3 - 7,5t Bloque 2 4,5t + 1,5t = 6t
6t - Bloque 7 - 7t 6t - Bloque 6 - 7t 8t - Bloque 5 - 9,5t 8t - Bloque 4 - 9t Bloque 3 6t + 1,5t = 7,5t Bloque 4 7,5t + 1,5t = 9t
T_entrada_etapa Bloque x T_salida_etapa
(b) Tiempo de ejecucin paralelo y ganancia en prestaciones para 4 procesadores Tp(4,n), S(4,n). Se
deben asignar las 5 tareas a los 4 procesadores de forma que se consiga el mejor tiempo de ejecucin
paralelo, es decir, el menor tiempo por bloque una vez procesado el primer bloque. Una opcin que nos
lleva al menor tiempo por bloque consiste en unir la Etapa 1 y 2 del pipeline del caso (a) en una nica etapa
asignando T1 y T2 a un procesador (ver asignacin de tareas a procesadores en la Tabla 2). Con esta
asignacin la etapa ms lenta supone 2t (Etapa 1); habra adems una etapa de 1,5 t (Etapa 2) y otra de t
(Etapa 3). Si, por ejemplo, se hubieran agrupado T3 y T4 un procesador la etapa ms lenta supondra 3t.
tnttntnTP 25,22)1(5,4),4( +=+=
8/10/2019 documento-120.pdf
21/49
Prof. responsables: M. Anguita, J. Ortega 7 / 12
Ejercicios del tema 2
325,2
6
),4(
)(),4(
+
==
n
p
s
tnt
tn
nT
nTnS La ganancia se aproxima a 3 para n suficientemente
grande.
Ejercicio 10.Se quiere implementar un programa paralelo para un multicomputador que calcule la siguiente
expresin para cualquier x (es el polinomio de interpolacin de Lagrange): ( )=
=n
i
ii xLbxP0
)()( , donde
( ) ( ) ( ) ( )ni
k
ax
k
axaxaxaxxL
i
n
ijj
j
i
niii ,...,1,0
)(
......)(
0
110 =
=
=
=
+
( ) ( ) ( ) ( ) niaaaaaaaaaakn
ijj
jiniiiiiii ,...,1,0)(......0
110 === =
+
Inicialmente ki, ai y bi se encuentra en el nodo i y x en todos los nodos. Slo se van a usar funciones de
comunicacin colectivas. Indique cul es el nmero mnimo de funciones colectivas que se pueden usar,cules seran y en qu orden se utilizaran y para qu se usan en cada caso.
Solucin
Los pasos ((1) a (5)) del algoritmo para n=3 y un nmero de procesadores de n+1 seran los siguientes:
Pr. Situacin
Inicial
(1) Resta paralela Ai=(x-ai)
((x-ai) se obtiene en Pi)(2) Todos reducen Aicon resultado en Bi : ( )
=
=n
i
ii AB0
P0 a0 x k0 b0 (x-a0) (x-a0).(x-a1).(x-a2).(x-a3)
P1 a1 x k1 b1 (x-a1) (x-a0).(x-a1).(x-a2).(x-a3)
P2 a2 x k2 b2 (x-a2) (x-a0).(x-a1).(x-a2).(x-a3)P3 a3 x k3 b3 (x-a3) (x-a0).(x-a1).(x-a2).(x-a3)
Tabla 2.
Asignacin de tareas a procesadores, ocupacin de las etapas del cauce para los primeros bloquesprocesados y tiempo de procesamiento del primer bloque y de los siguientes para 4 procesadores
T2
T4
T5T1
T3
P1 (2t)
P3(1,5t)
P2(1,5t)
P4 (t) Posible asignacin de tareas a 4
procesadores
Etapa 1 (2t) Etapa 2 (1,5t) Etapa 3 (t) Terminado Tiempo procesamiento
T1 y T2 (procesador P1) T3 (procesador P2) y
T4 (procesador P3)
T5 (procesador P4)
0 - Bloque 1 - 2t Procesamiento Bloque 1
(4,5t)2t - Bloque 2 - 4t 2t - Bloque 1 - 3,5t
4t - Bloque 3 - 6t 4t- Bloque 2 - 5,5t 3,5t - Bloque 1 - 4,5t
6t - Bloque 4 - 8t 6t - Bloque 3 - 7,5t 5,5t - Bloque 2 - 6,5t Bloque 1 2t + 1,5t + t = 4,5t
8t - Bloque 5 - 10t 8t - Bloque 4 - 9,5t 7,5t - Bloque 3 - 8,5t Bloque 2 4,5t + 2t = 6,5t
10t - Bloque 6 - 12t 10t - Bloque 5 - 11,5t 9,5t - Bloque 4 - 10,5t Bloque 3 6,5t + 2t = 8,5t
12t - Bloque 7 - 14t 12t - Bloque 6 - 13,5t 11,5t - Bloque 5 - 12,5t Bloque 4 8,5t + 2t = 10,5t
Bloque 5 10,5t + 2t = 12,5t
T_entrada_etapa Bloque x T_salida_etapa
8/10/2019 documento-120.pdf
22/49
8 / 12 Arquitectura de Computadores
Grado en Ingeniera Informtica
Pr. (3) Clculo de todos los Li(x)
en paralelo Li= Bi./( Ai. ki)
(Li(x) se obtiene en Pi)
(4) Clculo en paralelo Ci =bi . Li(bi. Li (x) se obtiene en Pi)
(5) Reduccin del contenido de Cicon resultado en P0
(P(x) se obtiene en P0)
P0 (x-a1).(x-a2).(x-a3)/ k0 b0.(x-a1).(x-a2).(x-a3)/ k0 ( ) ( ) ====
n
iii
n
ii LbCP 00
P1 (x-a0).(x-a2).(x-a3)/ k1 b1.(x-a0).(x-a2).(x-a3)/ k1
P2 (x-a0).(x-a1). (x-a3)/ k2 b2.(x-a0).(x-a1). (x-a3)/ k2
P3 (x-a0).(x-a1).(x-a2)/ k3 b3.(x-a0).(x-a1).(x-a2)/ k3
Como se puede ver en el trazado del algoritmo para n=3 mostrado en las tablas, se usan un total de 2
funciones de comunicacin colectivas (pasos (2) y (5) en la tabla). En el paso (2) del algoritmo se usa una
operacin de todos reducen para obtener en todos los procesadores los productos de todas las restas (x-
ai). En el paso (5) y ltimo se realiza una operacin de reduccin para obtener las sumas de todos los
productos (bix Li) en el proceso 0.
Ejercicio 11.
(a) Escriba un programa secuencial con notacin algortmica (podra escribirlo en C) que
determine si un nmero de entrada, x, es primo o no. El programa imprimir si es o no primo. Tendr
almacenados en un vector, NP, los Mnmeros primos entre 1 y el mximo valor que puede tener tener un
nmero de entrada al programa.
(b) Escriba una versin paralela del programa anterior para un multicomputador usando un estilo de
programacin paralela de paso de mensajes. El proceso 0 tiene inicialmente el nmero xy el vector NPen su
memoria e imprimir en pantalla el resultado. Considere que la herramienta de programancin ofrece
funciones send()/receive() para implementar una comunicacin uno-a-uno asncrona, es decir, con funcin
send(buffer,count,datatype,idproc,group) no bloqueante yreceive(buffer,count,datatype,idproc,group) bloqueante. En las funciones send()/receive() se
especifica:
group: identificador del grupo de procesos que intervienen en la comunicacin.
idproc:identificador del proceso al que se enva o del que se recibe.
buffer: direccin a partir de la cual se almacenan los datos que se envan o los datos que se
reciben.
datatype:tipo de los datos a enviar o recibir (entero de 32 bits, entero de 64 bits, flotante de 32
bits, flotante de 64 bits, ).
count: nmero de datos a transferir de tipo datatype.
Solucin
(a) Programa secuencial que determina si xes o no primo
Versin 1 Pre-condicin
x: nmero de entrada {2,,MAX_INPUT}. MAX_INPUT: mximo valor de la entrada
M: nmero de primos entre 2 y MAX_INPUT (ambos incluidos).
NP: vector con M+1 componentes (los M n primos desde 2 hasta MAX_INPUT enNP[0] hastaNP[M-
1], a NP[M]se asignar en el cdigo x+1)
Versin 1 Pos-condicin
Imprime en pantalla si el nmero xes primo o no
8/10/2019 documento-120.pdf
23/49
Prof. responsables: M. Anguita, J. Ortega 9 / 12
Ejercicios del tema 2
CdigoVersin 1 A Versin 1 B
if (x>NP[M-1]) {
print(%u supera el mximo primo adetectar %u \n, x, NP[M-1]);
exit(1);}NP[M]=x+1;i=0;while (xNP[M-1]) {print(%u supera el mximo primo a
detectar %u \n, x, NP[M-1]);
exit(1);}NP[M]=x+1;
for (i=0; xNP[M-1]) {print(%u supera el mximo primo a detectar %u \n, x, NP[M-1]);exit(1);
}xr = sqrt(x);for ( i=0 ; (NP[i]
8/10/2019 documento-120.pdf
24/49
10 / 12 Arquitectura de Computadores
Grado en Ingeniera Informtica
Se van a repartir las iteraciones del bucle entre los procesadores del grupo. Todos los procesos ejecutan el
mismo cdigo
Pre-condicin
x: nmero de entrada {2,,MAX_INPUT}; MAX_INPUT: mximo valor de la entrada
xr: almacena la raz cuadrada de x (slo se usa en la versin 2)
M: nmero de primos entre 2 y MAX_INPUT (ambos incluidos)
grupo: identificador del grupo de procesos que intervienen en la comunicacin.
num_procesos: nmero de procesos en grupo.
idproc:identificador del proceso (dentro del grupo de num_procesosprocesos) que ejecuta el cdigo
tipo:tipo de los datos a enviar o recibir
NP: vector con los Mn primos entre 2 y MAX_INPUT (en la versin 1 tendr M+1 componentes)
b, baux: variables que podrn tomar dos valores 0 (=false) o 1 (=true, si se localiza xen la lista de nmeros
primos)
Pos-condicin
Imprime en pantalla si el nmero xes primo o no
CdigoVersin 1 Versin 2
if (x>NP[i]) {print(%u supera el mximo primo a
detectar %u \n, x, NP[M-1]);exit(1);
}NP[M]=x+1;
//Difusin de x y NPif (idproc==0)
for (i=1; i
8/10/2019 documento-120.pdf
25/49
Prof. responsables: M. Anguita, J. Ortega 11 / 12
Ejercicios del tema 2
Versin 1:El nmero de instrucciones de comparacin en la parte de clculo paralelo depende de en qu
posicin se encuentre el nmero primo en NP. En el peor caso (cuando xno es primo) se recorre todo elvector entre todos los procesos, pero cada uno accede a un subconjunto de componentes del vector; en
particular, a M/num_procesos componentes sinum_procesosdivide a M. Entonces, si num_procesos
divide a M,cada proceso realizarM/num_procesos+1comparaciones y M/num_procesosen el bucle y 1
comparacin ms para obtener b. Se realiza ese nmero de comparaciones en el bucle porque cada procesoactualiza el ndice idel whileen cada iteracin sumndole el nmero de procesos num_procesos. Por
tanto,se asignan a los procesos las posiciones de NP con las que comparar en Round-Robin; por ejemplo, el
proceso 0 ejecutar las iteraciones para i igual a 0, num_procesos, 2*num_procesos ,
3*num_procesos, En total, todos los procesos en conjunto haran
(M/num_procesos+1+1)*num_procesos comparaciones en paralelo (M+2*num_procesos) . Todos los
procesos realizarn el mismo nmero de comparaciones si num_procesos divide a M (como se ha
comentado ms arriba), en caso contrario, debido a la asignacin Round-Robin, algunos harn una iteracin
ms del bucle que otros y, por tanto, una comparacin ms.
Resumiendo:
Si num_procesosdivide a M: cada proceso realiza M/num_procesos+1 comparaciones en el bucley 1 comparacin ms para obtener b (Orden de M/num_procesos)
Si num_procesos NO divide a M: algunos procesos realizan una comparacin ms que el resto,
estos procesos realizan Truncado(M/num_procesos)+2comparaciones en el bucle y 1 comparacin
ms para obtener b (Orden de M/num_procesos)
Versin 2:El nmero de instrucciones de comparacin en la parte de clculo paralelo depende de en qu
posicin, nr, de NPse encuentre el primer nmero primo mayor que sqrt(x). En el peor caso (cuando xnoes primo) se recorre hasta nr entre todos los procesos, pero cada uno accede a un subconjunto de
componentes del vector entre 0 y nr; en particular, a nr/num_procesos componentes sinum_procesos
divide anr
. Entonces, sinum_procesos
divide anr,
cada proceso realizar nr/num_procesos
+1
comparaciones y nr/num_procesos mdulos/comparaciones en el bucle y 1 comparacin ms para
obtener b. Se realiza ese nmero de operaciones en el bucle porque cada proceso actualiza el ndice idel
whileen cada iteracin sumndole el nmero de procesos num_procesos. Por tanto,se asignan a los
procesos las posiciones de NP con las que comparar en Round-Robin; por ejemplo, el proceso 1 ejecutar las
iteraciones para i igual a 1, num_procesos+1 , 2*num_procesos+1 , 3*num_procesos+1 ,. En total,
todos los procesos en conjunto haran 2*nr+2*num_procesos operaciones (operacin comparacin y
operacin mdulo/comparacin). Todos los procesos realizarn el mismo nmero de operaciones si
num_procesos divide a nr, en caso contrario, debido a la asignacin Round-Robin, algunos harn una
iteracin ms del bucle que otros y, por tanto, dos operaciones ms (una operacin comparacin ms una
operacin mdulo/comparacin).
Resumiendo:
Si num_procesos divide a nr: cada proceso realiza 2*nr+2*num_procesos operaciones
(operacin comparacin y operacin mdulo/comparacin). El orden de complejidad es denr/num_procesos.
Si num_procesosNO divide a nr: algunos procesos realizan dos comparaciones y un mdulo ms
que el resto, estos procesos realizan 2*Truncado(nr /num_procesos)+3operaciones en el bucle y
1 operacin de comparacin para obtener b.El orden de complejidad es denr/num_procesos.
Ejercicio 12.
8/10/2019 documento-120.pdf
26/49
12 / 12 Arquitectura de Computadores
Grado en Ingeniera Informtica
Ejercicio 13.
Ejercicio 14.
8/10/2019 documento-120.pdf
27/49
2 curso / 2 cuatr.
Grado en
Ing. Informtica
Arquitectura de Computadores.Algunos ejercicios resueltos
Tema 3. Arquitecturas con paralelismo a nivel de thread (TLP)
Profesores responsables: Mancia Anguita, Julio Ortega
Licencia Creative Commons
1 Ejercicios
Ejercicio 1.En un multiprocesador SMP con 4 procesadores o nodos (N0-N3) basado en un bus, queimplementa el protocolo MESI para mantener la coherencia, supongamos una direccin de memoria incluida
en un bloque que no se encuentra en ninguna cache. Indique los estados de este bloque en las caches y lasacciones que se producen en el sistema ante la siguiente secuencia de eventos para dicha direccin:
1. Lectura generada por el procesador 12. Lectura generada por el procesador 23.
Escritura generada por el procesador 14.
Escritura generada por el procesador 25. Escritura generada por el procesador 3
Solucin
Datos del ejercicio
Se accede a una direccin de memoria cuyo bloque kno se encuentra en ninguna cache, luego debeestar actualizado en memoria principal y el estado en las caches se considera invlido.
Estado del bloque en las caches y acciones generadas ante los eventos que se refiere a dicho bloque
Hay 4 nodos con cache y procesador (N0-N3). Intervienen N1, N2 y N3. En la tabla se van a utilizar lassiguentes siglas y acrnimos:
MP: Memoria Principal.
PtLec(k): paquete de peticin de lectura del bloque k.
PtLecEx(k): paquete de peticin de lectura del bloque k y de peticin de acceso exclusivo al bloque k.
RpBloque(k): paquete de respuesta con el bloque k.Se va a suponer que no existe en el sistema paquete de peticin de acceso exclusivo a un bloque sin
lectura (no existe PtEx).
ESTADOINICIAL
EVENTO ACCIN ESTADOSIGUIENTE
N1) Invlido
N2) Invlido
N3) Invlido
P1 lee k 1.- N1 (el controlador de cache de N1) genera y deposita enel bus una peticin de lectura del bloque k (PtLec(k)) porqueno lo tiene en su cach vlido
2.-MP (el controlador de memoria de MP), al observar
PtLec(k) en el bus, genera la respuesta con el bloque(RpBloque(k)).
N1) Exclusivo
N2) Invlido
N3) Invlido
8/10/2019 documento-120.pdf
28/49
2 / 6 Arquitectura de Computadores
Grado en Ingeniera Informtica
3.- N1 (el controlador de cache de N1) recoge del bus larespuesta depositada por la memoria principal(RpBloque(k)), el bloque entra en la cache de N1 en estadoexclusivo ya que no hay copia en otra cache del bloque (esdecir, la salida de la OR cableada con entradas procedentes
de todas las caches es 0).N1) Exclusivo
N2) Invlido
N3) Invlido
P2 lee k 1.- N2 genera y deposita en el bus una PtLec(k) porque notiene k en su cach en estado vlido
2.- N1 observa PtLec(k) en el bus y, como tiene el bloque enestado exclusivo, lo pasa a compartido (la copia que tiene yano es la nica vlida en caches). MP, al observar PtLec(k) enel bus, genera la respuesta con el bloque (RpBloque(k)).
3.- N2 recoge RpBloque(k) que ha depositado la memoria, elbloque entra en estado compartido en la cache de N2 (lasalida de la OR cableada ser 1).
N1) Compartido
N2) Compartido
N3) Invlido
N1) Compartido
N2) Compartido
N3) Invlido
P1 escribeen k
1.- N1 genera peticin de lectura con acceso exclusivo delbloque k (PtLecEx(k)) (suponemos que no hay peticin deacceso exclusivo sin lectura, no hay PtEx). N1 modifica lacopia de k que tiene en su cache y lo pasa a estadomodificado.
2.- N2 observa PtLecEx(k) y, como la peticin incluye accesoexclusivo (Ex) a un bloque que tiene en su cache en estadocompartido, pasa su copia a estado invlido. MP generaRpBloque(k) porque observa en el bus una peticin de k conlectura (Lec), pero esta respuesta no se va a recoger del bus.N1 no recoge RpBloque(k) depositada por la memoriaporque tiene el bloque vlido.
N1) Modificado
N2) Invlido
N3) Invlido
N1) ModificadoN2) Invlido
N3) Invlido
P2 escribeen k
1.- N2 genera peticin de lectura con acceso exclusivo de k(PtLecEx(k))
2.- N1 observa PtLecEx(k) y, como tiene el bloque en estadomodificado (es la nica copia vlida en todo el sistema),inhibe la respuesta de MP y genera respuesta con el bloqueRpBloque (k), y adems, como el paquete pide accesoexclusivo a k (Ex), invalida su copia del bloque k.
3.- N2 recoge RpBloque(k), introduce k en su cache, lomodifica y lo pone en estado modificado
N1) InvlidoN2) Modificado
N3) Invlido
N1) Invlido
N2) ModificadoN3) Invlido
P3 escribe
en k
1.- N3 genera peticin de lectura con acceso exclusivo de k
PtLecEx(k)
2.- N2 observa PtLecEx(k) y, como tiene el bloque en estadomodificado, inhibe la respuesta de MP y genera respuestacon el bloque RpBloque (k), y adems, como el paquete pideacceso exclusivo a k (Ex), invalida su copia de k.
3.- N3 recoge RpBloque(k), introduce el k en su cache, lomodifica y lo pone en estado modificado
N1) Invlido
N2) InvlidoN3) Modificado
Ejercicio 2.
.
8/10/2019 documento-120.pdf
29/49
Prof. responsables: M. Anguita, J. Ortega 3 / 6
Ejercicios del tema 3
Ejercicio 3..
Ejercicio 4.
Supongamos que se va a ejecutar en paralelo el siguiente cdigo (inicialmentexe yson 0):
P1
x=1;x=2;print y ;
P2
y=1;y=2;print x ;
Qu resultados se pueden imprimir si (considere que el compilador no altera el cdigo):
(a)
Se ejecutan P1 y P2 en un multiprocesador con consistencia secuencial.(b)
Se ejecutan en un multiprocesador basado en un bus que garantiza todos los rdenes excepto elorden WR. Esto es debido a que los procesadores tienen buffer de escritura, permitiendo elprocesador que las lecturas en el cdigo que ejecuta adelanten a las escrituras que tiene su buffer.Obsrvese que hay varios posibles resultados.
Solucin
El compilador no altera ningn orden garantizado ya que se supone, segn el enunciado, que no altera elcdigo.
(a)Si P1 es el primero que imprime puede imprimir 0, 1o 2, pero P2 podr imprimir slo 2. Esto es as porque semantiene orden secuencial (el hardware parece ejecutar losaccesos a memoria del cdigo que ejecuta un procesador enel orden en el que estn en dicho cdigo) y, por tanto, cuando P1 lee y (instruccin 1.3 en el cdigo, estainstruccin lee y para imprimir su contenido), ha asignado ya a x un 2 (punto 1.2 en el cdigo) ya queesta asignacin est antes en el cdigo que la lectura de y.
Si P2 es el primero que imprime podr imprimir 0, 1 o 2, pero entonces P1 slo puede imprimir 2. Esto
es as porque se mantiene orden secuencial y, por tanto, cuando P2 lee x (punto 2.3 en el cdigo), haasignado ya a y un 2 (punto 2.2 en el cdigo) ya que esta asignacin est antes en el cdigo que la lecturade xy se mantiene orden secuencial en los accesos a memoria, es decir, los accesos parecen completarseen el orden en el que se encuentran en el cdigo.
Se puede obtener como resultado de la ejecucin las combinaciones que hay en cada una de las lneas:P1 P20 2 (en este caso P1 imprime 0 y P2 imprime 2)1 22 22 0
2 1(b) Si no se mantiene el orden WR adems de los resultados anteriores, los dos procesos pueden
imprimir:P1 P21 1 (en este caso P1 imprime 1 y P2 imprime 1)0 10 21 02 00 0
Se pueden imprimir tambin las combinaciones anteriores porque no se asegura que cuando un procesadorejecute la lectura de la variable que imprime print (puntos 1.3 y 2.3 en los cdigos) haya ejecutado las
P1
(1.1) x=1;(1.2) x=2;(1.3) print y ;
P2
(2.1) y=1;(2.2) y=2;(2.3) print x ;
8/10/2019 documento-120.pdf
30/49
4 / 6 Arquitectura de Computadores
Grado en Ingeniera Informtica
instrucciones anteriores que escriben en x(P1 en los puntos 1.1 y 1.2 del cdigo) o en y(P2 en los puntos2.1 y 2.2). Esto es as porque no se garantiza el orden W->R y, por tanto, una lectura puede adelantar aescrituras que estn antes en el cdigo secuencial. P1 puede leer y (1.3) antes de escribir en x 2 (1.2) oincluso antes de escribir en x1 (1.1). Igualmente P2 puede leer x(2.3) antes de escribir en y2 (2.2) o antesde escribir en y1 (2.1).
Teniendo esto en cuenta P1 puede imprimir 1 o 2 o 0, y P2 1 o 2 o 0. Todas las combinaciones son posibles.
Ejercicio 5.
Ejercicio 6..
Ejercicio 7.
.
Ejercicio 8..
Ejercicio 9..
Ejercicio 10.
Se quiere paralelizar el siguiente ciclo de forma que la asignacin de iteraciones a losprocesadores disponibles se realice en tiempo de ejecucin (dinmicamente):For (i=0; iR, que las primitivas atmicas garantizan que sus accesos a memoria se realizanantes que los accesos posteriores y que el compilador no altera el cdigo.
(a) Paralelizar el ciclo para su ejecucin en un multiprocesador que implementa la primitiva Fetch&Orpara garantizar exclusin mutua.
(b) Paralelizar el anterior ciclo en un multiprocesador que adems tiene la primitiva Fetch&Add.
Solucin
Se debe tener en cuenta que el nico orden que no garantiza el hardware es el orden W->R.
(a) Paralelizar el ciclo para su ejecucin en un multiprocesador que implementa la primitiva Fetch&Orparagarantizar exclusin mutua.
8/10/2019 documento-120.pdf
31/49
Prof. responsables: M. Anguita, J. Ortega 5 / 6
Ejercicios del tema 3
for (i=0;i
8/10/2019 documento-120.pdf
32/49
6 / 6 Arquitectura de Computadores
Grado en Ingeniera Informtica
- : "+Q" (inc), "+m" (lock->slock) /*%0 es inc, %1 es lock->slock */- /*Q asigna cualquier registro al que se pueda acceder con rh: a, b, c y d; ej. ah, bh */- :- : "memory", "cc");-}-
-static __always_inline void __ticket_spin_unlock(raw_spinlock_t *lock)-{- asm volatile( incb %0" /*%0 es lock->slock */- : "+m" (lock->slock)- :- : "memory", "cc");
-}
Conteste a las siguientes preguntas:
(a)
Utiliza una implementacin de cerrojo con etiquetas Cul es el contador de adquisicin y cul es elcontador de liberacin?
(b) Describa qu hace xaddw %w0, %1 opera con el contador de adquisicin, con el de liberacin o con
los dos? qu operaciones hace con ellos?(c) Describa qu hace cmpb %h0, %b0 opera con el contador de adquisicin, con el de liberacin o con
los dos? qu operaciones hace con ellos?(d)
Por qu cree que se usa el prefijo lockdelante de la instruccin xaddw?
NOTAS: (1) Puede consultar las instrucciones en el manual de Intel con el repertorio de instrucciones(Volumen 2 o volmenes 2A, 2B y 2C) que puede encontrar aquhttp://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html.
(2) Si no recuerda la interfaz entre C/C++ y ensamblador en gcc (se ha presentado en Estructura deComputadores), consulte el manual de gcc aqu http://gcc.gnu.org/onlinedocs/gcc-4.6.2/gcc/Extended-Asm.html#Extended-Asm(http://gcc.gnu.org/onlinedocs/)
Solucin
(b)
lock->slock contiene el contador de liberacin en los bits de 0 a 7 liberacin (lock->slock[7...0]) y el de adquisicin en los bits de 8 a 15 (lock->slock[15...8]).
(c)
xaddw %w0, %1 almacena en los 16 bits menos significativos del registro al que se ha asigna inc(%0) los 16 bits (sufijo w) menos significativos de lock->slock (%1) y asigna a lock->slock(contador de adquisicin y contador de liberacin) el resultado de sumarlo con inc. Comoconsecuencia: (1) incrementa en uno el contador de adquisicin (lock->slock[15...8]) dado queinctiene un 1 en el bit 8 (inccontiene 0x0100) y (2)almacena en inc[15...8] (%h0) el valor de estecontador antes de la modificacin y en inc[7...0] (%b0) el valor del contador de liberacin (lock->slock[7...0]).
(d)
cmpb %h0, %b0 compara el valor actual del contador de liberacin inc[7...0] (%b0) y el deadquisicin inc[15...8] (%h0); es decir, resta ambos contadores modificando slo el registro deestado. En las instrucciones posteriores se usa el resultado de la comparacin (los bits de estadoresultantes de la comparacin). Si son iguales ambos contadores (bit z del registro de estado a 1),abandona la funcin lock del cerrojo, y si son distintos actualiza el valor del contador de liberacincargando lo que hay en lock->slock[7...0] en inc[7...0](%b0)
(e)
Se requiere el prefijo lockpara que la lectura y escritura en memoria que realiza la instruccin xaddwse hagan de forma atmica. Si xaddwno fuese atmica dos flujos de control podran leer el mismo valordel contador de adquisicin y, como consecuencia, ms de un flujo podra entrar a la vez en una seccincrtica.
8/10/2019 documento-120.pdf
33/49
2curso/2cuatr.
Gradoen
Ing.Informtica
ArquitecturadeComputadores.EjerciciosyCuestiones
Tema
4.
Arquitecturas
con
Paralelismo
a
nivel
de
Instruccin
(ILP)Materialelaboradoporlosprofesoresresponsablesdelaasignatura:JulioOrtega,ManciaAnguita
LicenciaCreativeCommons
1 Ejercicios
Ejercicio
1. Paraelfragmentodecdigosiguiente:1. l w r 1, 0x1ac ; r 1 M( 0x1ac)
2. l w r 2, 0xc1f ; r 2 M( 0xc1f )
3. add r 3, r 0, r 0 ; r 3 r 0+r 0
4. mul r 4, r 2, r 1 ; r 4 r2*r1
5. add r 3, r 3, r 4 ; r 3 r 3+r 4
6. add r 5, r 0, 0x1ac ; r 5 r0+0x1ac
7. add r 6, r 0, 0xc1f ; r 6 r 0+0xc1f
8. sub r 5, r 5, #4 ; r 5 r 5 - 4
9. sub r 6, r 6, #4 ; r 6 r 6 - 4
10. sw ( r 5) , r 3 ; M( r 5) r 3
11. sw ( r 6) , r 4 ; M( r 6) r 4
ysuponiendoquesepuedencaptar,decodificar,yemitircuatroinstruccionesporciclo,indiqueelordenenqueseemitirnlasinstruccionesparacadaunodelossiguientescasos:
a)Unaventanadeinstruccionescentralizadaconemisinordenada
b)Unaventanadeinstruccionescentralizadaconemisindesordenada
c)Unaestacindereservadetreslneasparacadaunidadfuncional,conenvoordenado.
Nota:considerequehayunaunidadfuncionalparalacarga(2ciclos),otraparaelalmacenamiento(1ciclo),tresparalasuma/resta(1ciclo),yunaparalamultiplicacin(4ciclos).Tambinpuedeconsiderarque,enlaprctica, no hay lmite para el nmero de instrucciones que pueden almacenarse en la ventana deinstruccionesoenelbufferdeinstrucciones.
Solucin
Acontinuacinsemuestranlaevolucintemporaldelasinstruccionesensusdistintasetapasparacadaunadelasalternativasquesepiden.Enesasfigurassesuponequetrasladecodificacindeunainstruccin,stapuedepasaraejecutarsesinconsumirciclosdeemisinsilosoperandosylaunidadfuncionalquenecesitaestn disponibles. Por esta razn, no se indicarn explcitamente los ciclos dedicados a la emisin en loscasos(a)y(b),yalenvoenelcaso(c)
a)Emisinordenadaconventanacentralizada
Comosemuestralatablacorrespondiente,lasinstruccionesseempiezanaejecutarenordenrespetandolasdependenciasdedatosoestructuralesqueexistan.Porejemplolasegundainstruccindeaccesoamemoria
lw
debe
esperar
que
termine
la
instruccin
lw
anterior
porque
solo
hay
una
unidad
de
carga
de
memoria.
La
8/10/2019 documento-120.pdf
34/49
2/17 ArquitecturadeComputadores
GradoenIngenieraInformtica.ETSIIT.UniversidaddeGranada
emisindelainstruccinadd r 3, r 3, r 4 debe esperar a que termine la ejecucin de la instruccin demultiplicacinquelaprecede.
Lainstruccinadd r 3, r 0, r 0 debe esperar a que se hayan emitido las instrucciones que la preceden apesardequenodependedeellasypodrahaberseemitidoenelciclo3,silaemisinfuesedesordenada.
Tambin debe comprobarse que no se emiten ms de cuatro instrucciones por ciclo. En este caso, comomucho,seemitentresinstrucciones,enelciclo11.
INSTRUCCIN 1 2 3 4 5 6 7 8 9 10 11 12 13 14
lw r1, 0x1ac IF ID EX EX
lw r2, 0xc1f IF ID EX EX
add r3, r0, r0 IF ID EX
mul r4, r2, r1 IF ID EX EX EX EX
add r3, r3, r4 IF ID EX
add r5, r0, 0x1ac IF
ID
EX
add r6, r0, 0xc1f IF ID EX
sub r5, r5, #4 IF ID EX
sub r6, r6, #4 IF ID EX
sw (r5), r3 IF ID EX
sw (r6), r4 IF ID EX
b)Emisindesordenadaconventanacentralizada
En este caso, hay que respetar las dependencias de datos y las estructurales. En cuanto las instruccionestenganunaunidaddisponibley losdatosquenecesitansepuedenemitir,siemprequenoseanmenosde
cuatrointrucciones
por
ciclo
las
que
se
emitan.
En
este
caso,
como
mucho
se
emiten
tres
instrucciones
en
losciclos4y5
INSTRUCCIN 1 2 3 4 5 6 7 8 9 10 11 12
lw r1, 0x1ac IF ID EX EX
lw r2, 0xc1f IF ID EX EX
add r3, r0, r0 IF ID EX
mul r4, r2, r1 IF ID EX EX EX EX
add r3, r3, r4 IF ID EX
add r5, r0, 0x1acIF
ID
EX
add r6, r0, 0xc1f IF ID EX
sub r5, r5, #4 IF ID EX
sub r6, r6, #4 IF ID EX
sw (r5), r3 IF ID EX
sw (r6), r4 IF ID EX
c)Estacindereservacontreslneasparacadaunidadfuncional,yenvoordenado.
Enestaalternativa,sehasupuestoquelasinstruccionesdecodificadasseemitenaunaestacindereservadesdelaqueseaccedealaunidadfuncionalcorrespondienteenviandolasinstruccionesdeformaordenada
(poreso
las
dos
instrucciones
sw
se
ejecutan
ordenadamente).
La
asignacin
de
instrucciones
de
suma
o
restaa las tresestacionesdereservaqueexistenparasuma/restasehahechode formaalternativapero
8/10/2019 documento-120.pdf
35/49
Prof.responsables:J.Ortega,M.Anguita 3/17
Ejerciciosdeltema4
tratandodeminimizartiempos.Esdecir,sehaasignadoaunaestacindereservaquenotuvierasuunidadfuncionalcorrespondienteparaobtenerlostiemposmsfavorables.
ESTACIN DERESERVA
INSTRUCCIN 1 23 4 5 6 7 8 9 10 11 12 13
LW lw r1, 0x1ac IF ID EXLW lw r2, 0xc1f IF ID EXADD(1) add r3, r0, r0 IF ID EXMULT(1) mul r4, r2, r1 IF ID EXADD(2) add r3, r3, r4 IF ID EXADD(3) add r5, r0, 0x1ac IF ID EXADD(1) add r6, r0, 0xc1f IF ID EXADD(3) sub r5, r5, #4 IF ID EXADD(1) sub r6, r6, #4 IF ID EXSW sw (r5), r3 IF ID EX
SW sw (r6), r4 IF ID EX
Ejercicio2. Considerequeelfragmento decdigosiguiente:1. l w r 3, 0x10a ; r 3 M( 0x10a)
2. addi r 2, r 0, #128 ; r 2 r 0+128
3. add r 1, r 0, 0x0a ; r 1 r 0+0x0a
4. l w r4, 0( r 1) ; r 4 M( r 1)
5. l w r5, - 8( r1) ; r5 M( r 1- 8)
6. mul t r 6, r 5, r 3 ; r 6 r5*r37. add r 5, r 6, r 3 ; r 5 r 6+r 3
8. add r 6, r 4, r 3 ; r 6 r 4+r 3
9. sw 0( r 1) , r 6 ; M( r 1) r 5
10. sw - 8( r 1) , r 5 ; M( r 1- 8) r 5
11. sub r 2, r 2, #16 ; r 2 r 2- 16
se ejecuta en un procesador superescalar que es capaz de captar 4 instrucciones/ciclo, de decodificar 2instrucciones/ciclo;deemitirutilizandounaventanade instruccionescentralizada2 instrucciones/ciclo;deescribir hasta 2 resultados/ciclo en los registros correspondientes (registros de reorden, o registros de laarquitecturasegnelcaso),ycompletar(oretirar)hasta3instrucciones/ciclo.
Indiqueel
nmero
de
ciclos
que
tardara
en
ejecutarse
el
programa
suponiendo
finalizacin
ordenada
y:
a)Emisinordenada
b)Emisindesordenada
Nota:Considerequetieneunaunidad funcionaldecarga (2ciclos),unadealmacenamiento (1ciclo),tresunidadesdesuma/resta(1ciclo),yunademultiplicacin(6ciclos),yquenohaylimitacionesparaelnmerode lneas de la cola de instrucciones, ventana de instrucciones, buffer de reorden, puertos delectura/escrituraetc.)
Solucin
a)
Enlaemisinordenadalosinstantesenlosquelasinstruccionesempiezanaejecutarse(etapaEX)deben
estarordenadosdemenoramayor,adiferenciadeloqueocurreenlaemisindesordenada.Sesuponeque
8/10/2019 documento-120.pdf
36/49
4/17 ArquitecturadeComputadores
GradoenIngenieraInformtica.ETSIIT.UniversidaddeGranada
elprocesadorutilizaunbufferdereordenamiento (ROB)paraque la finalizacindelprocesamientode las
instrucciones sea ordenada. Por ello, las etapas WB de las instrucciones (momento en que se retiran las
instruccionesdelROByseescribenen losregistrosde laarquitectura)debenestarordenadas(tantoenel
caso de emisin ordenada como desordenada). La etapa marcada como ROB es la que corresponde a la
escrituradelosresultadosenelROB(sehasupuestoquelasinstruccionesdeescrituraenmemoriatambin
consumenunciclodeescrituraenelROByunciclodeescrituraWBenelbancoderegistros,aunqueestos
ciclossepodranevitarparaestasinstrucciones).
Tambin tiene que comprobarse que no se decodifican, emiten, ni escriben en el ROB ms de dos
instruccionesporciclo,niseretiranmsdetresinstruccionesporciclo.
INSTRUCCIN 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
lw r3, 0x10a IF ID EX ROB WB
addi r2, r0, #128 IF ID EX ROB WB
add r1, r0, 0x0a IF ID EX ROB WB
lw r4, 0(r1) IF
ID
EX
ROB WB
lw r5, 8(r1) IF ID EX ROB WB
mult r6, r5, r3 IF ID EX ROB WB
add r5, r6, r3 IF ID EX ROB WB
add r6, r4, r3 IF ID EX ROB WB
sw 0(r1), r6 IF ID EX ROB WB
sw 8(r1), r5 IF ID EX ROB WB
sub r2, r2, #16 IF ID EX ROB WB
b) Enelcasodeemisindesordenada,latrazadeejecucindelasinstruccioneseslasiguiente:
INSTRUCCIN 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
lw r3, 0x10a IF ID EX ROB WB
addi r2, r0, #128 IF ID EX ROB WB
add r1, r0, 0x0a IF ID EX ROB WB
lw r4, 0(r1) IF ID EX ROB WB
lw r5, 8(r1) IF ID EX ROB WB
mult r6, r5, r3 IF ID EX ROB WB
add r5, r6, r3 IF ID EX ROB WB
add r6, r4, r3 IF ID EX ROB WB
sw 0(r1), r6 IF ID EX ROB WB
sw 8(r1), r5 IF ID EX ROB WB
sub r2, r2, #16 IF ID EX ROB WB
Tambinenestecasohayque tenerencuentaquenosepuedendecodificar,emitir,ni escribirenelROBmsdedosinstruccionesporciclo(obsrvesequelainstruccinswr2,r2,#16debeesperaruncicloparasuetapaROBporestarazn),nisepuedenretirarmsdetresinstruccionesporciclo.
Ejercicio
3.
En el problema anterior, (a) indique qu mejoras realizara en el procesador para reducir el
tiempo
de
ejecucin
en
la
mejor
de
las
opciones
sin
cambiar
el
diseo
de
las
unidades
funcionales(multiplicador,sumador,etc.)ysincambiareltipodememoriasni la interfazentreprocesadorymemoria
8/10/2019 documento-120.pdf
37/49
Prof.responsables:J.Ortega,M.Anguita 5/17
Ejerciciosdeltema4
(no vara el nmero de instrucciones captadas por ciclo. (b) Qu pasara si se reduce el tiempo demultiplicacinalamitad?.
Solucin
(a) Enprimerlugar,seconsideraquesedecodificanelmismonmerodeinstruccionesquesecaptan,ya
que no existen limitaciones impuestas por las instrucciones al ritmo de decodificacin (ste viene
determinado por las posibilidades de los circuitos de descodificacin y la capacidad para almacenar las
instruccionesdecodificadashastaqueseemitan).Tambinseconsideraquenoexistenlimitacionesparael
nmerodeinstruccionesporcicloqueseemiten,escribenelROB,yseretiran.Porltimo,seconsideranque
estn disponibles todas las unidades funcionales que se necesiten para que no haya colisiones (riesgos
estructurales).
INSTRUCCIN 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
lw r3, 0x10a IF ID EX ROB WB
addi r2, r0, #128 IF ID EX ROB WB
add r1, r0, 0x0a IF ID EX ROB WB
lw r4, 0(r1) IF ID EX ROB WB
lw r5, 8(r1) IF ID EX ROB WB
mult r6, r5, r3 IF ID EX ROB WB
add r5, r6, r3 IF ID EX ROB WB
add r6, r4, r3 IF ID EX ROB WB
sw 0(r1), r6 IF ID EX ROB WB
sw 8(r1), r5 IF ID EX ROB WB
Teniendoencuentalascaractersticasdelatraza,siseredujeseeltiempodelamultiplicacinalamitad
(esdecir
tres
ciclos)
el
tiempo
de
ejecucin
de
dicha
traza
se
reducira
tambin
en
esos
mismos
tres
ciclos
ya
quetodaslasinstruccionesquesiguenalamultiplicacinseencuentranesperandoaquetermineestaparapoderproseguir.Esdecir,laoperacindemultiplicacineselcuellodebotellaenestecaso.
INSTRUCCIN 1 2 3 4 5 6 7 8 9 10 11 12
lw r3, 0x10a IF ID EX ROB WB
addi r2, r0, #128 IF ID EX ROB WB
add r1, r0, 0x0a IF ID EX ROB WB
lw r4, 0(r1) IF ID EX ROB WB
lw r5, 8(r1) IF ID EX ROB WB
mult r6, r5, r3 IF ID EX ROB WB
add r5, r6, r3 IF ID EX ROB WB
add r6, r4, r3 IF ID EX ROB WB
sw 0(r1), r6 IF ID EX ROB WB
sw 8(r1), r5 IF ID EX ROB WB
sub r2, r2, #16 IF ID EX ROB WB
Porlotantosetendran12ciclos.Sisetieneencuentaquesetienen11instrucciones,queeltiempomnimo
que tarda la primera instruccin en salir son 6 ciclos (lo tomamos como tiempo de latencia de inicio del
cauce),yque
el
tiempo
total
de
ejecucin
en
este
caso
es
de
12
ciclos,
se
puede
escribir:
8/10/2019 documento-120.pdf
38/49
6/17 ArquitecturadeComputadores
GradoenIngenieraInformtica.ETSIIT.UniversidaddeGranada
CPI1116CPI1TLI12 nnT
Y,sisedespeja,setienequeelprocesadorsuperescalarpresentaunamediade0.6ciclosporinstruccin,o
loquees lomismo,ejecuta1.67 instruccionesporciclo.Tieneuncomportamientosuperescalar,peroest
muylejosdelastresinstruccionesporcicloquepuedenterminarcomomximo.
Ejercicio4. Enelcasodescritoenelproblema3,indiquecmoevolucionaraelbufferdereorden,utilizadoparaimplementarfinalizacinordenada,enlamejordelasopciones.
Solucin
La Tabla que se proporciona a continuacin muestra la evolucin del buffer de reordenamiento (ROB)
marcandoennegritaloscambiosqueseproducenencadaciclo.
Enelciclo2sedecodificanlasinstrucciones(1)(4)yseintroducenenelROB.
Enel
ciclo
3se
decodifican
las
instrucciones
(5)
(8)
yse
introducen
en
el
ROB.
En el ciclo 4 se decodifican las instrucciones (9) (11) y se introducen en el ROB.
SimultneamentesealmacenaenelROB los resultadosde las inst