我一直想知道何时使用并行前缀总和而不是使用顺序构建。我正在使用的算法构造并行求和，但我在某处读到，对于少量元素（通常少于 100 个元素），最好使用顺序算法。这带来了一个问题，即是否存在某个阈值，超过该阈值并行实现可能会比顺序实现产生一些收益？我正在使用 opencl 进行编码，并使用 Blelloch 1990 实现实现了并行前缀和。
问问题
545 次
1 回答
1
像往常一样，这取决于。关于实现、设备和数据大小。
GPU Gems 3，第 39 章有一些漂亮的图表，显示了它们的特定实现何时具有阈值。当然，他们并没有天真地实现该算法——它是使用共享内存、展开循环和避免缓存组冲突的优化版本。
一旦你有了一个实现，你只需要对其进行基准测试以找到阈值。
于 2013-06-07T16:25:05.010 回答