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
| Página siguiente |