Metas
Predecir el rendimiento de programas paralelos
Entender los obstáculos que impiden mejor rendimiento
Bosquejo
Formula General para speedup
La Ley de Amdahl
La Ley de Gustafson-Barsis
La Métrica de Karp-Flatt
La Métrica de Isoeficiencia
Speedup
Speedup = ts /tp donde ts es el tiempo que se requiere para ejecutar el programa secuencialmente y tp es el tiempo que se requiere para ejecutar el programa en paralelo
Quinn denota speedup por ?(n,p) donde n es el tamaño del problema y p es el número de procesos
Speedup (cont)
?(n,p)=p
?(n,p)=p si el problema se particiona perfectamente en p procesos iguales y no hay ningun "overhead" debido a, por ejemplo, comunicaciones, coordenació de procesos, el costo de particionar, etc.
Los Componentes de Tiempo de Ejecutación
Computaciones que tienen que hacer secuencialmente: ?(n)
Computaciones que se pueden llevar a cabo en paralelo: ?(n)
Operaciones de comunicaciones: ??(n,p)
Expresión para Speedup
ts = ?(n) + ?(n)
tp = ?(n) + ?(n)/p + ??(n,p)
Por lo tanto,
?(n,p) = (?(n) + ?(n))/(?(n) + ?(n)/p + ??(n,p))
?(n)/p
Aumentar el número de procesadores reduce el tiempo computacional
?(n)/p
?(n,p)
El tiempo de comunicaciones crece con la cantidad de procesadores
?(n,p)
En algun momento el tiempo de comunicaciones será mayor que el tiempo computacional
?(n)/p + ?(n,p)
?(n)/p + ?(n,p)
Speedup
Eficiencia
Eficiencia = tS / (p*tp) donde p es el número de procesadores
Ya que tp = tS / p, tenemos que
0 = Eficiencia = 1
Quinn denota eficiencia por ?(n,p)
Notemos que ?(n,p)=?(n,p)/p
La Ley de Amdahl
?(n,p) = (?(n) + ?(n))/(?(n) + ?(n)/p + ??(n,p))
= (?(n) + ?(n))/(?(n) + ?(n)/p )
Si f es la porción de la computación que es inherentemente secuencial, es decir que f=?(n)/(?(n) + ?(n)), entonces
? = 1/(f+(1-f)/p)
Notemos que ? = 1/f
Página siguiente  |