3

我在实现并行计算前缀和的算法时遇到问题。即使这个算法有 3 个步骤，我也无法编写代码，因为没有给出伪代码。

我浏览了网络上的各种材料以及堆栈溢出，但我没有得到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 序列中的一个值

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

4

2 回答 2

5

I believe the provided answer is not enough to understand the algorithm, so I provided an actual answer with more comprehensive pseudocode here: https://stackoverflow.com/a/12874227/697862 based on Parallel Prefix Sum (Scan) with CUDA which is a complete article describing the optimum parallel algorithm according to:

Blelloch, Guy E. 1990. "Prefix Sums and Their Applications." Technical Report CMU-CS-90-190, School of Computer Science, Carnegie Mellon University.

于 2012-10-13T15:00:09.550 回答
1

你写的几乎是伪代码，但我希望这会有所帮助。

prefix_sum(List x):List
begin
   //This step is split in multiple tasks that are running in paralell
   //build z, be careful around the end
   w = prefix_sum(z)

   //This step should also be split in multiple tasks
   //build y, using w and x
   return y
end

编辑： y i是我们想要得到的总和，如果 i%2 == 1， y i = w i/2 ，否则 w i/2-1 + x。这里我们假设 w -1 =0

于 2012-04-08T11:01:37.800 回答