← Volver a los ejercicios

Trabajo y profundidad: sumar ocho enteros en dos órdenes

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.

1. Cuántas sumas hay que hacer

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.

¿Cuántas sumas se hacen en total?

2. Los dos órdenes, paso a paso

paso 0 de 0
sumas hechas: 0 cadena más larga: 0

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.

3. La profundidad de cada orden

La profundidad supone paralelismo ilimitado: todo lo que no dependa de nada más se hace al tiempo.

¿Cuánto vale D en el orden secuencial?
¿Cuánto vale D en el orden en árbol?

4. Las reglas de composición

W(f(e1, e2)) = W(e1) + W(e2) + W(f)
D(f(e1, e2)) = D(e1) + D(e2) + D(f)
W(parallel(e1, e2)) = W(e1) + W(e2) + c1
D(parallel(e1, e2)) = max(D(e1), D(e2)) + c2

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.

5. Qué cambia al poner más núcleos

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.

6. Para resolver por su cuenta

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.