Gráficas de Coste, Eficiencia y Escalabilidad en Computación Paralela: Conceptos Clave
Gráfica de Coste C(n,p) vs. T(n)
Si te dan una gráfica con dos rectas que parten del origen con distinta pendiente (o dos rectas paralelas en escala logarítmica) y te preguntan si es de coste óptimo, la respuesta es SÍ, es de coste óptimo porque C(n,p) es proporcional a T(n), es decir, C(n,p) = cte · T(n).
Si para un n fijo la gráfica de C(n,p) respecto a p es una línea horizontal constante, también es óptimo porque al aumentar p el tiempo paralelo disminuye proporcionalmente: T(n,p) = T(n)/p.
Gráfica de la Eficiencia Escalada
- Si la curva cae y tiende a 0 al aumentar p: NO es escalable.
- Si en la gráfica la curva baja de 0, no es escalable, porque tiende a valores menores que 0, lo cual no puede darse en la práctica, ya que la eficiencia nunca puede ser negativa.
- Si es una línea recta en 0,5 o en cualquier constante, significa que E(n,p) = 0,5 es constante.
Si me piden deducir T(n,p) sabiendo que T(n) = n² · tc, despejo E = T(n) / (p · T(n,p)) = 0,5.
Extrapolación
Si la gráfica llega hasta p = 128 y preguntan por p = 1024, hay que indicar que con seguridad no se puede extrapolar nada, porque el intervalo de observación no incluye 1024.
Gráfica de Speedup y Ley de Amdahl
Si la curva de speedup es una diagonal perfecta donde S(n,p) = p, entonces la parte secuencial α(n) = 0 (todo el código es paralelizable y E = 1).
Bisección Recursiva Coordinada (BRC)
- Mayor ventaja: su simplicidad (poco coste).
- Mayor inconveniente: mantiene (no elimina ni optimiza) las comunicaciones.
Nota: si te dan un grafo pequeño y simétrico y preguntan si para 2 procesadores es mejor BRC o Bisección Recursiva No Balanceada, responde indistintamente, porque el corte de menor coste coincide exactamente con la mitad.
Relación Superficie-Volumen (RSV) igual a 0
Implica que las comunicaciones desaparecen (se eliminan) y, por tanto, el agrupamiento es óptimo. Además, recuerda que la inversa de la granularidad G(n,p) = t_cal / t_com se llama Relación Superficie-Volumen.
Fracción Paralela (PF) muy baja
Es adecuada para procesadores con pocos cores.
Ojo: si preguntan si con muchos cores tendrá peor rendimiento efectivo que con 2 cores, es FALSO: nunca es peor. En el límite, cuando PF = 0, se igualan, pero las curvas teóricas nunca se cruzan.
Principio de Escalabilidad
"Para que un algoritmo sea escalable, la eficiencia tiene que ser constante".