← Volver a los ejercicios

Ley de Amdahl: el techo que pone la parte secuencial

Ningún programa se reparte completo. Si una fracción f es inherentemente secuencial y el resto se divide entre P núcleos sin pérdidas, el tiempo pasa de una unidad a f + (1 - f)/P y el speedup es su inverso. De esa cuenta sale una consecuencia incómoda: el primer término no depende de P, así que la curva se aplana en 1/f y ningún número de núcleos la cruza. La página calcula la tabla desde la fórmula y termina en la decisión que la fórmula obliga a tomar, con las cifras del programa de la sesión.

1. La cuenta, línea por línea

El tiempo de la versión secuencial se toma como unidad, de modo que f es a la vez una fracción y un tiempo. El paso a paso reparte esa unidad en lo que se queda igual y lo que se divide.

paso 0 de 0

La línea 3 es la única donde aparece P. Subir el número de núcleos encoge ese término y deja intacto el de la línea 2.

2. La tabla, calculada desde la fórmula

SP = 1 / (f + (1 - f)/P)    S∞ = 1/f
La celda del preset escogido está tapada. ¿Cuánto vale ese speedup?

Cada fila cambia la fracción secuencial y cada columna el número de núcleos. La última columna es el límite con todos los núcleos que se quieran.

3. El techo

4. Dos formas de subir el speedup

Hay dos maneras de mover la cuenta: cambiar P, que divide a 1 - f, o cambiar f, que mueve los dos términos a la vez. Las cifras de las dos están en la tabla de arriba.

5. Comprar núcleos o reescribir la parte serial

La suma paralela del arreglo de diez millones de elementos tardó 42 ms en su versión secuencial y 15 ms con cuatro hilos en la máquina de la sesión. Su parte serial es la suma que sigue a cada parallel, más partir el arreglo. Con el speedup medido y P = 4 se puede despejar qué fracción del programa es esa parte, y con ella decidir dónde conviene gastar el esfuerzo.

6. Para resolver por su cuenta

Un programa tarda 80 segundos y un perfilador reporta que 12 de esos segundos se van en leer el archivo de entrada, que se recorre en orden y no se reparte. Calcule f, el techo y el speedup con ocho núcleos. Después averigüe a cuánto habría que bajar el tiempo de lectura para que esos mismos ocho núcleos alcancen un speedup de 5.