← Volver a los ejercicios

Trabajo y profundidad en escala: el mismo W con otra D

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.

1. Los niveles del árbol

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ó.

2. El mismo trabajo en escala

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.

3. Qué gana el árbol cuando n crece

4. Con un número fijo de núcleos el tope no se alcanza

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.

5. segmentRec con un umbral


    

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.

D = log2(n / limite) + (limite - 1)

El trabajo es 1023 sumas en toda la tabla, porque cada elemento entra una sola vez.

6. Para resolver por su cuenta

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.