next up previous contents
Next: 2.3.4 Estándares de programación Up: 2.3.3 Consideraciones de utilización Previous: 2.3.3.3 Consideraciones generales   Índice General

2.3.3.4 La Ley de Amdahl

Eugene Amdahl analizó este problema y en 1967 propuso lo que se conoce como la Ley de Amdahl [8], que indica la mejora de rendimiento que se puede esperar incrementando los elementos de procesamiento. La Ley de Amdahl toma en cuenta la parte ``secuencial'' del proceso, es decir, aquella que independientemente de cuántos elementos de procesamiento tengamos, puede ser realizada por uno solo de ellos; y el resto del cálculo no podrá continuar hasta que se haya completado la parte secuencial.

La Ley de Amdahl propone normalizar el tiempo que toma realizar la operación en un solo procesador al valor de 1. La fracción del cálculo que sólo se puede realizar secuencialmente será F, entonces la fracción paralelizable es $(1-F)$. Con estos datos, el incremento de velocidad máximo que puede obtenerse con P elementos de procesamiento está dado por la fórmula:


\begin{displaymath}
\frac{1}{F+\frac{(1-F)}{P}}
\end{displaymath}

Como un ejemplo, si nuestra aplicación no tiene sección secuencial (es decir, $F=0$ y $(1-F)=1$), entonces el incremento de velocidad máximo estará dado exactamente por el número de elementos de procesamiento:


\begin{displaymath}
\frac{1}{\frac{1}{P}}=P
\end{displaymath}

Por otro lado, si el 50% del código es secuencial (es decir, $F=0.5$ y $(1-F)=0.5$), la ecuación queda:


\begin{displaymath}
\frac{1}{0.5+\frac{(0.5)}{P}}=\frac{P}{0.5P}+\frac{0.5}{P}
\end{displaymath}

Suponiendo un número infinito de procesadores, esta ecuación da como resultado 2. Si el 50% del código es secuencial, por más procesadores que se agreguen el rendimiento nunca será más de 2 veces mayor que una implementación uniprocesador.

En general el incremento de velocidad máximo si el número de procesadores tiende a infinito será de $1/F$. Si tenemos 10% de código secuencial, aumentar el número de procesadores no llevará un incremento de rendimiento mayor a 10 ($1/0.1$). Similarmente, 90% de código secuencial significa que el rendimiento no podrá crecer más allá de un factor de 1.111 ($1/0.9$).

Realizando una gráfica de número de procesadores contra incremento de rendimiento máximo, se observa que la gráfica es logarítmica, aproximándose al valor máximo determinado anteriormente, sin llegar a alcanzarlo nunca. Ya se determinó el factor de incremento máximo, sin embargo estas gráficas pueden ser una herramienta útil para decidir cuantos elementos de procesamiento se deben dedicar al problema. Dentro de los límites del incremento máximo ya mencionado, para cada valor de $F$ la curva es diferente. Para algunos valores de $F$ la curva se aproxima a la asíntota muy rápidamente según el número de elementos de procesamiento, en este caso puede no ser muy útil agregar más elementos. Para otros valores de $F$, la curva es menos pronunciada, acercándose más lentamente a la asíntota, y el incremento de rendimiento con más procesadores puede ser substancial hasta el límite propuesto por la Ley de Amdahl.

La figura (1.3) muestra gráficas de la fórmula de la Ley de Amdahl, para algunos valores de $F$ entre 0.1 y 1, mostrando la relación entre el número de procesadores y el rendimiento que se puede obtener.

Figura: Gráfica Ley de Amdahl

Así pues, la Ley de Amdahl deja de manifiesto un concepto esencial para la planeación y utilización de cualquier tipo de máquina paralela: el incremento en velocidad que podemos obtener está limitado por el algoritmo que emplee nuestra aplicación, y no por el número de procesadores. Como un ejemplo, de la gráfica (1.3) podemos observar que un algoritmo con 50% de código secuencial no podrá tener un incremento de velocidad mayor a 2 independientemente del número de procesadores; si se logra reducir el código secuencial a 40%, se obtiene un incremento de velocidad de 2 utilizando únicamente 6 elementos de procesamiento. Si el problema lo permite, Se debe buscar implementar algoritmos que tengan la menor cantidad de código secuencial, pues como se aprecia en las curvas, este factor tiene mucha más importancia que el número de procesadores a utilizar.


next up previous contents
Next: 2.3.4 Estándares de programación Up: 2.3.3 Consideraciones de utilización Previous: 2.3.3.3 Consideraciones generales   Índice General
2002-05-15