Aula 20: Redução Paralela: soma baseada em árvore

Uma redução reduz um array inteiro a um único valor — por exemplo, a soma de todos os elementos. Na CPU você faz isso em um loop sequencial: um acumulador percorrendo os n elementos em n passos. Mas isso desperdiça a GPU: uma thread trabalha enquanto milhares ficam ociosas. A solução paralela é uma

Imagine 8 pessoas que precisam somar 8 números. Em vez de uma pessoa somar tudo sozinha, cada dupla soma ao mesmo tempo: 8 viram 4, depois 2, depois um resultado. Três rodadas em vez de sete — esse é o poder da árvore.

redução (reduction): Reduzir um array a um único valor usando uma operação associativa (soma, máximo, etc.). Na GPU isso é feito em forma de árvore.
redução em árvore (tree reduction): A cada passo metade das threads soma pares; a profundidade é log2(n) passos em vez de n.
stride: A distância entre os dois elementos somados em um passo dado. Começa grande e cai pela metade a cada passo até chegar a 1.
sincronização entre passos: __syncthreads() depois de cada passo garante que todas as escritas terminaram antes que o próximo passo as leia — sem isso, há uma condição de corrida.