с использованием префикса sum - параллельный или последовательный

Question

Мне было интересно, когда использовать параллельную префиксную сумму вместо использования последовательного наращивания. В алгоритме я использую конструкции параллельных сумм, но где-то я читал, что для небольшого числа элементов (как правило, менее 100 элементов) лучше использовать последовательный алгоритм. Это ставит вопрос о том, существует ли определенный порог, выше которого параллельная реализация может дать некоторый выигрыш по сравнению с последовательностью? Я использую opencl для кодирования и реализовал параллельную префиксную сумму с использованием реализации Blelloch 1990.

Answer 1

Это зависит, как обычно. О реализации, устройстве и размере данных.

GPU Gems 3, chapter 39 имеет некоторые красивые графики, которые показывают, когда их конкретные реализации имеют пороговые значения. Разумеется, они не реализовали алгоритм наивно - это оптимизированная версия, использующая разделяемую память, развернутые циклы и избежание конфликтов в кэше.

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