ProblemasTema1resueltos

Ejercicios y cuestiones -Tema 1

Prof.ª. Maribel García

EJERCICIOS RESUELTOS.
1. Un programa tarda 40 s en ejecutarse en un multiprocesador. Durante un
20% de ese tiempo se ha ejecutado en cuatro procesadores; 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 ejecuciónen cada momento, y despreciamos sobrecarga). ¿Cuánto tiempo
tardaría en ejecutarse el programa en un único procesador?. ¿Cuál es la
ganancia en velocidad obtenida con respecto al tiempo de ejecución secuencial?.
¿Y la eficiencia?
SOLUCIÓN
Datos del ejercicio:
En el siguiente gráfico se representa los datos del ejercicio. Estos datos se
refieren a la fracción del tiempo de ejecución paralelo quesupone: el código no
paralelizable, el código paralelizable en 3 procesadores y el código paralelizable
en 4 procesadores. Al distribuirse la carga de trabajo por igual entre los
procesadores utilizados en cada instante, los trozos asignados a 3 procesadores
suponen el mismo tiempo (por eso se han dibujado en el gráfico de igual
tamaño) e igualmente los trozos asignados a 4 procesadores suponen elmismo
tiempo.
Procesadores

4
3

4

1
20%

3

3

2

2

1

1

60%
TP

20%

Tiempo
paralelo

¿Tiempo de ejecución secuencial, TS?:

1

2

3

1

2

3

4

¿TS ?

T S =0,2×T P 3×0,6×T P 4×0,2×T P = 0,21,80,8 ×T P =2,8×T P =2,8×40 s=112 s

¿Ganancia en velocidad, S(p)?:

S  4 =

T S 2,8×T P
=
=2,8
TP
TP

¿Eficiencia, E(p)?:

E  4 =

S  p  S  4  2,8
=
=
=0,7
p
4
4------------------------------------------------------------------------------------------------------------------2.- Un programa tarda 20 s en ejecutarse en un procesador P1, y requiere 30
s en otro procesador P2. Si se dispone de los dos procesadores para la ejecución
del programa (despreciamos sobrecarga):
a) ¿Qué tiempo tarda en ejecutarse el programa si la carga de trabajo se
distribuye por igual entre losprocesadores P1 y P2?

1

Ejercicios y cuestiones -Tema 1

Prof.ª. Maribel García

b) ¿Qué distribución de carga entre los dos procesadores P1 y P2 permite el
menor tiempo de ejecución utilizando los dos procesadores en paralelo ?. ¿Cuál
es este tiempo?
SOLUCIÓN
Datos del ejercicio:
TP1=20 s
TP2=30 s
(a) ¿Tiempo de ejecución paralelo distribuyendo la carga por igual, TP?:
TPP1 (1/2) = 20s/2 = 10 s y TPP2(1/2) = 30s/2 = 15 s
TPP1,P2 = máximo(20s/2, 30s/2) = 15 s
En el entorno de trabajo heterogéneo que conforma P1 y P2, si la carga de
trabajo se distribuye por igual entre los procesadores, el tiempo de ejecución en
paralelo lo determinará el procesador que acabe más tarde de ejecutar su mitad.
La distribución de carga de trabajo no se ha hecho de forma que los
procesadores empicen y terminen a lavez (no se ha equilibrado).
(b) ¿Distribución con menor tiempo y tiempo de ejecución paralelo en ese
caso, TP?:
El mejor caso se obtiene si se puede distribuir la carga de forma que los dos
procesadores empiecen y terminen a la vez:
TPP1 (x) = TPP2 (1-x) => 20s × x = 30s × (1- x) => 2 × x = 3 × (1- x) => 5 ×
x = 3 => x = 3/5
3/5 para P1 y 2/5 para P2
TPP1 (3/5) = 20s × 3/5 = 12s------------------------------------------------------------------------------------------------------------------3.- ¿Cuál es la fracción de código 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)?SOLUCIÓN
Datos del programa:
Procesadores

8

8
7
6
5
4
3
2
1

1
50ns

TP

Tiempo
paralelo

50ns

¿Fracción de código paralelizable del programa secuencial, fP?:
TS
1

50ns

2

3

4

5

50ns

6

7

8

fP

f p=

8×50 ns
8×50 ns
8
=
=
TS
50 ns8×50 ns 9

-------------------------------------------------------------------------------------------------------------------

2

Ejercicios y cuestiones -Tema 1...