algorithm - 使用前缀和 - 并行或顺序

Question

我一直在想什么时候使用并行前缀和而不是使用顺序累积。我正在使用的算法构造并行求和，但我在某处读到对于少量元素(通常少于 100 个元素)，最好使用顺序算法。这就带来了一个问题，即是否存在某个阈值，超过该阈值并行实现可能会比顺序实现产生一些 yield ？我正在使用 opencl 进行编码，并使用 Blelloch 1990 实现实现了并行前缀和。

Answer 1

这取决于，像往常一样。关于实现、设备和数据大小。

GPU Gems 3, chapter 39有一些漂亮的图表显示他们的特定实现何时有阈值。当然，他们并没有天真地实现该算法 - 它是使用共享内存、展开循环和缓存库冲突避免的优化版本。

实现后，您只需对其进行基准测试以找到阈值。