并行算法计算前缀和

Question

我在实现并行计算前缀总和的算法时遇到问题。尽管此算法有3个步骤，但由于没有给出伪代码，因此我无法编写代码。

我遍历了网络上的各种内容以及堆栈溢出的内容，但是我没有得到Wiki上给出的算法的确切实现。Wiki提及以下内容：

前缀总和可以通过以下步骤并行计算：

1. 计算连续项对的总和，其中该对的第一个项具有偶数索引：z0 = x0 + x1，z1 = x2 + x3，依此类推。
2. 递归计算序列z0，z1，z2，...的前缀和w0，w1，w2，...
3. 将序列w0，w1，w2 ...的每个项扩展为总前缀总和的两个项：y0 = x0，y1 = w0，y2 = w0 + x2，y3 = w1，依此类推。在第一个值之后，每个连续数yi是从w序列的一半位置复制的，或者是x序列中一个值的前一个值

有人可以建议一个伪代码实现让我检查并实现吗？

Answer 1

我相信所提供的答案是不够了解的算法，所以我提供了更全面的伪代码这里的实际答案：/sf/answers/901195921/基于并行前缀求和（扫描），具有CUDA是根据以下内容描述最佳并行算法的完整文章：

Blelloch，Guy E.，1990年。“前缀求和及其应用”。卡内基梅隆大学计算机科学学院，技术报告CMU-CS-90-190。