Gráficas de Coste, Eficiencia y Escalabilidad en Computación Paralela: Conceptos Clave

Matemáticas2,74 KB

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".

Descargar

PDF Word HTML