Análisis de rendimiento (página 2)

Partes: 1, 2

Limitaciones de la Ley de Amdahl
En el pasado se creia que fue un limite fatal al futuro de paralelismo. Sin embargo,
su demostración tiene que ver con los pasos de un algorítmo específico y no toma en consideración que otro algorítmo con mas paralelismo podria existir.
trata el tamaño de problema como una constante, pero en la práctica la proporción secuencial de un programa decrece con el tamaño,

Otras Limitaciones
Ignora ?(n,p)
Sobre estima el speedup que se puede lograr

El Efecto Amdahl
En la práctica, el tiempo de comunicación ?(n,p) tiene complexidad menor que ?(n)/p (i.e., el tiempo para la parte paralela)
Cuando n crece, ?(n)/p domina a ?(n,p)
Cuando n crece,
La proporción secuencial decrece
Speedup crece

Illustration of Amdahl Effect
(Gp:) n = 100

(Gp:) n = 1,000

(Gp:) n = 10,000

Speedup
Processors

Resumen de la Ley de Amdahl
Trata tamaño como constante
Demuestra como el tiempo de ejecutación decrece cuando el número de procesadores crece
Profesionales en computación paralela no creean que la ley de Amdahl limita el futuro de computación paralela, como originalmente creian.

La Métrica Isoeficiencia
Un sistema paralelo se define como un programa paralelo que se está ejecutando en una computadora paralela
La escalabilidad de un sistema paralelo es una medida de su habilidad para mejorar rendimiento cuando se aumenta el número de procesadores es
Un sistema escalable mantiene su eficiencia cuando se aumenta la cantidad de procesadores
Isoeficiencia:Una manera para medir escalabilidad

Para Derivar la Relación de Isoeficiencia
Determinar los gastos generales
Substituir gastos generales en la ecuación de speedup
Sustituir T(n,1) = ?(n) + ?(n). Presumir eficiencia constante.
Relación de Isoeficiencia

Para Derivar la Relación de Isoeficiencia (cont)
Para mantener el mismo nivel de eficiencia cuando crece la cantidad de procesadores, hay que aumentar n para que se cumpla

La Función de Escalabilidad
Supongamos que la relación de isoeficiencia es n ? f(p)
Sea M(n) la cantidad de memoria que se requiere para un problema de tamaño n
M(f(p))/p indica como el uso de memoria por procesador tiene que crecer para mantener la misma eficiencia
M(f(p))/p se llama la función de escalabilidad

El Significado de la Función de Escalabilidad
Para mantener la eficiencia cuando crece p, tenemos que aumentar n
El tamaño de problema máximo está limitado por la cantidad de memoria disponible, que es lineal en p
La función de escalabilidad muestra como el uso de memoria por procesador tiene que crecer para mantener eficiencia
Si la función de escalabilidad es constante, el sistema paralelo es perfectamente escalable

Ejemplo : El Algoritmo de Floyd
Complexidad Secuencial: ?(n3)
Complexidad Paralela: ?(n3/p)
Tiempo de comunicaciones: ?(n2log p)
Gastos Paralelismo: T0(n,p) = ?(pn2log p)

compute_shortest_paths
void compute_shortest_paths (int id, int p, dtype **a, int n)
{
int i, j, k;
int offset; /* Local index of broadcast row */
int root; /* Process controlling row to be bcast */
int *tmp; /* Holds the broadcast row */
tmp = (dtype *) malloc (n * sizeof(dtype));
for (k = 0; k < n; k++)
{ root = BLOCK_OWNER(k, p, n);
if (root == id)
{ offset = k – BLOCK_LOW(id, p, n);
for (j = 0; j < n; j++)
tmp[j] = a[offset][j];
}
MPI_Bcast (tmp, n, MPI_TYPE, root, MPI_COMM_WORLD);
for (i = 0; i < BLOCK_SIZE(id, p, n); i++)
for (j = 0; j < n; j++)
a[i][j] = MIN(a[i][j], a[i][k] + tmp[j]);
}
free (tmp);
}

El Algoritmo de Floyd (cont)
Relación de Isoeficiencian3 ? C(p n2 log p) ? n ? C p log p
M(n) = n2

El sistema no tiene buena escabilidad