Сокращение, сканирование и сортировка в Thrust

Редукции, сканирование и сортировку непросто быстро написать вручную. Thrust предоставляет оптимизированные реализации одним вызовом функции. 🎁

thrust::reduce объединяет все элементы в один результат, например суммирует массив, причём вся работа параллельно выполняется внутри.

По умолчанию reduce выполняет сложение, но Вы можете передать начальное значение и бинарный оператор, чтобы вычислить произведение, максимум или любую другую ассоциативную операцию.

Сканирование, или префиксная сумма, выдаёт на каждой позиции текущую накопленную сумму. Это основа уплотнения, сортировки и распределения в потоках.

inclusive_scan включает текущий элемент в сумму, а exclusive_scan — нет. Правильный выбор позволяет избежать ошибки на единицу.

Префиксная сумма выглядит последовательной, однако Thrust выполняет её параллельно с помощью продуманного древовидного алгоритма, который Вам не приходится писать самостоятельно.

thrust::sort сортирует device_vector на месте с помощью быстрой поразрядной или сортировки слиянием на GPU, что для больших объёмов данных намного быстрее сортировки на CPU.

sort_by_key сортирует один массив и переставляет второй массив значений в соответствии с ним. Это идеально подходит для сохранения соответствия записей их ключам.

В реальных конвейерах эти операции объединяют в цепочки: сначала transform, затем reduce или сначала сортировка, затем сканирование. Каждый шаг — один оптимизированный вызов, поэтому Вы можете сосредоточиться на логике.

transform_reduce за один проход выполняет отображение и суммирование, вычисляя, например, скалярное произведение или сумму квадратов без временного массива.

Эти примитивы тщательно оптимизированы компанией NVIDIA. Обычно сначала стоит использовать их: это эффективнее собственного ядра и экономит часы работы.

Вы свернули данные с помощью reduce, построили накопленные суммы с помощью scan, отсортировали массивы с помощью sort и объединили шаги с помощью transform_reduce. 🏁