LEYES
Ley de Amdahl
Ley de Gustafson
Modelo de Sun-Ni
1
GRADO DE PARALELISMO (DOP)
Suposición: un sólo programa en ejecución.
El DOP puede exceder el número de procesadores disponibles -> algunas bifurcaciones tienen que ejecutarse en trozos secuencialmente.
n=número de procesadores homogéneos
m=paralelismo máximo
Idealmente, n>>m
k=procesadores disponibles
?=Capacidad de computación de un procesador, en MIPS, MFLOPS, …
DOP = i => hay i procesadores ocupados
2
DOP: Es el número de procesos paralelos en los que se puede dividir un programa en un instante dado.
EJEMPLO: PERFIL DE PARALELISMO
3
Imagen de Hwang, 1993
PARALELISMO MEDIO
4
Cantidad de trabajo (instrucciones):
Paralelismo medio:
EJEMPLO:
Ld r1, A
Ld r2, B
Ld r7, C
Add r4, r1, r1
Mul r8, r7, r7
Addi r3, r2, 1
Sto D, r4
Sub r5, r4, r8
Ld r6, E
Addi r6, r6, 3
Add r6, r6, r5
Sto F, r6
5
Consideremos una arquitectura con 3 procesadores donde los accesos a memoria necesitan para ejecutarse 2 ciclos y las operaciones en punto flotante 5.
Calcular el perfil de paralelismo y el DOP medio del siguiente programa:
SOLUCIÓN:
Ld r1, A
Ld r2, B
Ld r7, C
Add r4, r1, r1
Mul r8, r7, r7
Addi r3, r2, 1
Sto D, r4
Sub r5, r4, r8
Ld r6, E
Addi r6, r6, 3
Add r6, r6, r5
Sto F, r6
6
Una posible ejecución del programa sería la siguiente:
SOLUCIÓN:
7
Con lo que se obtiene el siguiente perfil de paralelismo y es posible calcular el paralelismo medio:
SOLUCIÓN:
8
Si la máquina anterior tiene una capacidad de cálculo de 8 MFLOPS, ¿cual es la cantidad de trabajo total generada por el programa anterior?
SOLUCIÓN:
9
Si la máquina anterior tiene una capacidad de cálculo de 8 MFLOPS, ¿cual es la cantidad de trabajo total generada por el programa anterior?
SPEEDUP ASINTÓTICO
10
Tiempo de ejecución
Speedup asintótico
Página siguiente |