Sumar n enteros cuesta n - 1 sumas en cualquier orden, de modo que el trabajo no se mueve. Lo que se mueve es la profundidad: la cadena las pone una tras otra y el árbol las agrupa por niveles. De esa diferencia sale el speedup tope, W dividido por D, que cambia con n. El valor de n se escoge en la primera tarjeta y lo usan también el cuadro y la cuenta con núcleos.
La página reduce la lista
1, 2, ..., n sumando por parejas y cuenta lo que hizo: las
sumas de cada nivel y cuántos niveles necesitó.
La última fila es la lectura
general: el trabajo crece con n y la profundidad del árbol con
log2 n.
Cada fila se llena al calcular su tope. Cambie el valor de n arriba para pasar a la siguiente.
La profundidad supone tantos núcleos como haga
falta. Con P núcleos, un nivel de k sumas
independientes se hace en rondas de P, y un nivel no empieza
hasta que el anterior termina.
El umbral corta la recursión: por debajo de
limite el segmento se suma de corrido. Con un arreglo de 1024
elementos, el árbol de particiones tiene altura
log2(1024 / limite), y una hoja de limite
elementos agrega limite - 1 sumas encadenadas.
El trabajo es 1023 sumas en toda la tabla, porque cada elemento entra una sola vez.
Un arreglo tiene 220 elementos. Con la
cuenta de la tarjeta anterior, halle el umbral más grande, potencia de dos,
con el que el speedup tope todavía pase de 1000, y escriba las dos cifras
que lo sostienen. Después implemente segmentRecPar, mida el
tiempo con ese umbral y con el doble y el cuádruple, y diga si el orden de
los tiempos medidos coincide con el orden de los topes calculados.