Lección 20: Reducción paralela: suma basada en árbol

Una reducción colapsa un arreglo entero en un único valor — por ejemplo, la suma de todos los elementos. En una CPU esto se hace en un bucle secuencial: un acumulador que recorre los n elementos en n pasos. Pero eso desperdicia la GPU: un hilo trabaja mientras miles quedan inactivos. La solución par

Imagina a 8 personas que deben sumar 8 números. En lugar de que una sola los sume todos, cada par suma al mismo tiempo: 8 se vuelven 4, luego 2, luego un solo resultado. Tres rondas en lugar de siete — ese es el poder del árbol.

reducción (reduction): Colapsar un arreglo en un único valor mediante una operación asociativa (suma, máximo, etc.). En una GPU se hace en forma de árbol.
reducción en árbol (tree reduction): En cada paso la mitad de los hilos suman pares; la profundidad es de log2(n) pasos en lugar de n.
stride: La distancia entre los dos elementos que se suman en un paso dado. Empieza grande y se reduce a la mitad en cada paso hasta llegar a 1.
sincronización entre pasos: __syncthreads() después de cada paso garantiza que todas las escrituras terminaron antes de que el siguiente paso las lea — sin ella hay una condición de carrera.