Урок 20: Параллельная редукция: суммирование на основе дерева

Редукция сворачивает целый массив в одно значение — например, сумму всех элементов. На CPU это делается в последовательном цикле: один аккумулятор проходит по n элементам за n шагов. Но это расточительно для GPU: работает один поток, а тысячи других простаивают. Параллельное решение — древовидная ре

Представьте 8 человек, которые должны сложить 8 чисел. Вместо того чтобы один человек складывал их все в одиночку, каждая пара складывает одновременно: 8 превращаются в 4, затем в 2, затем в один результат. Три раунда вместо семи — в этом сила дерева.

редукция (reduction): Свёртка массива в одно значение с помощью ассоциативной операции (сумма, максимум и т. д.). На GPU выполняется в виде дерева.
древовидная редукция (tree reduction): На каждом шаге половина потоков складывает пары; глубина составляет log2(n) шагов вместо n.
stride: Расстояние между двумя элементами, складываемыми на данном шаге. Начинается большим и уменьшается вдвое на каждом шаге до 1.
синхронизация между шагами: __syncthreads() после каждого шага гарантирует, что все записи завершены до того, как следующий шаг их прочитает — без него возникает состояние гонки.