La ley de Amdahl

La ley de Amdahl se puede utilizar para determinar la cantidad de computo que puede ser acelerado mediante la ejecución en paralelo. La ley de Amdahl debe su nombre a Gene Amdahl quien presentó la ley en 1967.

Un programa ( o algoritmo ) se puede dividir en dos partes :
Una parte que no se puede implementar en paralelo
Una parte que puede ser implementada en paralelo
Imagine un programa que procesa los archivos desde el disco. Una pequeña parte de ese programa puede escanear el directorio y crear una lista de archivos en la memoria interna . Después de eso, cada archivo se pasa a un hilo separado para su procesamiento. La parte que analiza el directorio y crea la lista de archivos no puede ejecutarse en paralelo , pero el procesamiento de los archivos si.

El tiempo total necesario para ejecutar el programa en serie ( no en paralelo) se llama T. El tiempo T incluye el tiempo de ambas partes no paralelizables y paralelizables . La parte no paralelizable se llama B. La parte paralelizable se conoce como T - B. La siguiente lista resume estas definiciones :

T = Tiempo total de ejecución en serie
B = tiempo total de parte no paralelizable
T - B = tiempo total de parte paralelizable ( cuando se ejecuta en serie , no en paralelo)
A partir de este se desprende que :

T = B + (T-B)                                                               

Puede parecer un poco extraño al principio que la partes que se pueden ejecutar en paralelo del programa no tengan su propio símbolo en la ecuación. Sin embargo, dado que la parte paralelizable de la ecuación se puede expresar utilizando total T Tiempo y B , la ecuación se ha reducido conceptualmente, lo que significa que contiene menos variables  diferentes de este forma.

Es la parte T - B , que puede ser acelerada mediante la ejecución en paralelo. 

Cuánto se puede acelerar depende del número de hilos o CPUs que se usen para ejecutarlo. El número de hilos o CPUs se llama N. La razon de velocidad con la que puede ejecutarse se representa asi:

(T - B) / N

Según la ley de Amdahl , el tiempo de ejecución total del programa cuando se ejecuta en paralelo utilizando N hilos o CPUs es:

T(N) = B + (T - B) / N

T ( N ) significa la ejecución total, con un factor de paralelización N. Por lo tanto , T se podría escribir 

T ( 1 ) , es decir, el tiempo de ejecución total, con un factor de paralelización de 1. Utilizando T ( 1 ) en lugar de T , Ley de Amdahl se ve asi:

T(N) = B + ( T(1) - B ) / N

Significa lo mismo.

Un Ejemplo de cálculo

Para entender mejor la ley de Amdahl , vamos a hacer un ejemplo de cálculo . El tiempo total para ejecutar un programa se establece en 1. La parte no paralelizable de los programas es 40 %, que a cabo de un tiempo total de 1 es igual a 0,4 . La parte paralelizable es por lo tanto igual a 1 - 0,4 = 0,6 .

El tiempo de ejecución del programa, con un factor de paralelización de 2 ( 2 hilos o CPUs que ejecutran la parte paralelizable , así que N es 2 ) sería:

T(2) = 0.4 + ( 1 - 0.4 ) / 2
     = 0.4 + 0.6 / 2
     = 0.4 + 0.3
     = 0.7

Haciendo el mismo cálculo con un factor de paralelización de 5 en lugar de 2 se vería así :

T(5) = 0.4 + ( 1 - 0.4 ) / 5
     = 0.4 + 0.6 / 5
     = 0.4 + 0.12
     = 0.52

Referencias:

http://tutorials.jenkov.com/java-concurrency/amdahls-law.html