Aula 21: Otimizando a Redução: sequential addressing

Na aula anterior construímos uma redução em árvore na shared memory: a cada passo metade das threads soma um par de valores, e assim a soma vai se reduzindo até um único valor. Mas a forma como escolhemos quais threads ficam ativas e quais índices elas tocam muda drasticamente o desempenho. Na versã

Imagine 8 crianças em fila que precisam somar números. No método ruim, você pede para a criança 0, 2, 4 e 6 trabalharem — uma trabalha, uma descansa, bagunçado. No método bom, você pede só para as 4 primeiras crianças, cada uma somando o número da criança à sua frente na segunda metade da fila. Mesma soma, mas um grupo organizado trabalha enquanto o outro descansa — sem bagunça.

endereçamento intercalado (interleaved addressing): Esquema de redução em que o stride cresce (s *= 2) e a thread ativa é 2*s*tid, então as ativas ficam espalhadas — causando divergência de warp e conflitos de bank.
endereçamento sequencial (sequential addressing): Esquema de redução com loop invertido (s >>= 1) em que toda thread com tid < s soma tile[tid] += tile[tid+s], então as ativas formam um bloco contíguo — sem divergência e sem conflitos.
conflito de bank (bank conflict): Quando threads do mesmo warp acedem ao mesmo bank da shared memory, os acessos se serializam em vez de correr em paralelo — prejudicando o desempenho.
threads ativas: As threads que realizam trabalho num dado passo da redução. No endereçamento sequencial elas formam um bloco contíguo 0..s-1; no intercalado ficam espalhadas.