Dos números describen un programa paralelo. El trabajo
W cuenta todas las operaciones que hay que hacer, como si no
hubiera paralelismo, y es el costo secuencial. La profundidad D
mide la cadena más larga de operaciones que tienen que ir una después de
otra, suponiendo núcleos de sobra, y es el tiempo mínimo al que se puede
aspirar. Sumar ocho enteros los separa. El resultado es el mismo y las sumas
son las mismas; lo que cambia con el orden es la profundidad.
Hay que sumar los ocho enteros
1, 2, 3, 4, 5, 6, 7, 8, en cualquier orden, con una operación
que recibe dos valores y devuelve uno.
El contador de cada línea dice cuántas veces se evaluó, así que al final del recorrido se ve qué sumas entraron en cada orden. Las cuatro primeras del árbol se escriben una debajo de otra y ninguna usa el resultado de las otras tres.
La profundidad supone paralelismo ilimitado: todo lo que no dependa de nada más se hace al tiempo.
La única diferencia está en la última
línea: con parallel la profundidad pasa de suma a máximo. Las
constantes c1 y c2 son el costo de lanzar y
esperar, y en las preguntas que siguen no se cuentan.
Cada suma cuesta una unidad de tiempo y un nivel no
empieza hasta que el anterior termina. Con P núcleos, un nivel
de k sumas independientes se hace en rondas de
P.
Escriba la función que multiplica los elementos de
una lista de ocho enteros en el orden en árbol, usando
parallel para cada par de mitades. Calcule su
W y su D con las reglas de composición, tomando
el producto como una operación de costo 1 y sin contar
c1 ni c2. Después repita la cuenta para una lista
de 64 enteros y diga cuántas unidades de tiempo tarda en una máquina de dos
núcleos.