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 |