La suma de prefijos parece secuencial: cada posición necesita la anterior.
Aquí se recorre en dos pasadas, como en scan.cpp; la primera la hace la
página, los desplazamientos los escoge usted, y la segunda arranca de lo que haya escogido.
1. Los valores
ahora: suma
Tres bloques de cuatro, uno por hilo. Con máximo, cada posición guarda el
mayor valor visto hasta ahí: es el saldo máximo acumulado de los ejercicios de la sesión.
2. Primera pasada
3. Los desplazamientos
Con qué acumulado arranca cada bloque en la segunda pasada, para la
operación suma.
Bloque 1
Bloque 2
Bloque 3
4. Segunda pasada
La fila de abajo es el recorrido de corrido, con un solo hilo. Si
escogió algún desplazamiento, la segunda pasada usa los suyos; si no, los correctos.
5. Qué sucede al medirlo
20 millones de elementos y 4 hilos, con una operación costosa
por elemento: secuencial 2.731 ms, dos pasadas 1.636 ms. La versión paralela recorre los
datos dos veces y aun así gana.
Si peso(x) fuera una suma pelada, sin la
operación costosa por elemento, ¿quién gana?