问题标签 [prefix-sum]

我正在玩一些 Data Parallel Haskell 代码，发现自己需要一个前缀 sum。但是，我在dph 包中没有看到任何用于前缀总和的基本运算符。

我推出了自己的，但是，由于我是 dph 的新手，我不确定它是否正确地利用了并行化：

首先，这里是算法的链接：

GPU Gems 3，第 39 章：使用 CUDA 的并行前缀和（扫描）。

为了避免存储库冲突，每个 NUM_BANKS（即，对于可计算性 2.x 的设备为 32 个）元素向共享内存阵列添加填充。这是通过（如图 39-5 所示）完成的：

我不明白 ai/NUM_BANKS 如何等同于宏：

不等于

任何帮助表示赞赏。谢谢

我在实现并行计算前缀和的算法时遇到问题。即使这个算法有 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 序列中的一个值

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

我需要实现一个前缀和算法，并且需要它尽可能快。
前任：

应该给：

有没有办法使用 SSE SIMD CPU 指令来做到这一点？

我的第一个想法是递归地对每一对并行求和，直到所有总和都计算如下！

为了让算法更清晰一点，z不是最终输出，而是用于计算输出。

我有这个数组 [1 2 3 4 5 6 7 8 9]，我正在对其执行扫描操作。

我有 3 个 mpi 任务，每个任务都有 3 个元素，然后每个任务计算其扫描并将结果返回给主任务

现在任务 0 得到所有结果 [1 3 6] [4 9 15] [7 15 24]

我如何结合这些结果来产生最终的扫描输出？

数组的最终扫描输出为 [1 3 6 10 15 21 28 36 45]

谁能帮帮我？

我有一个内核，它进行一些比较并决定两个对象是否碰撞。我想将碰撞对象的 id 存储到输出缓冲区。我不想在输出缓冲区中有间隙。我想将每次碰撞记录到输出缓冲区中的唯一索引。

所以我在共享内存（局部总和）和全局内存（全局总和）中创建了一个原子变量。下面的代码显示了在发现冲突时共享变量的递增。我现在在全局内存中增加原子变量没有问题。

我的问题是，当许多线程尝试增加原子变量时，它们会被序列化。在写前缀和之类的东西之前，我想问一下是否有办法有效地完成这项工作。

由于这一行，我的内核的运行时间从 13 毫秒增加到 44 毫秒。

我找到了一个前缀和示例代码，但它的引用链接失败，因为 NVIDIA 的讨论板已关闭。 https://stackoverflow.com/a/3836944/596547

编辑：我也在上面添加了我的代码的结尾。事实上，我确实有等级制度。为了查看每个代码行的影响，我设置了每个对象相互碰撞的场景、极端情况以及几乎没有对象碰撞的另一种极端情况。

最后，我将共享原子变量添加到全局变量 (gColCnt) 中，以告知外部碰撞次数并找到正确的索引值。我想我必须以任何方式在这里使用 atomicAdd 。

我有一个随机整数数组。例如[132, 2, 31, 49, 15, 6, 70, 18 ... , 99, 1001]. 例如，我想生成所有大于 100 的数字的数组并获取该数组的大小。

有两种方法：

1. PyOpenCL 的新功能copy_if。它基于 GenericScanKernel并且如果我们更深入地了解Prefix Sums。
2. 使用Atomics的纯 OpenCL 解决方案

copy_if总是正常工作吗？如我所见copy_if，不使用原子。使用时可能会遇到麻烦copy_if吗？

copy_if与原子方式相比，性能如何？

你会选择什么，为什么？

所以我的任务是编写汇编代码，对一组数字执行前缀求和。

给出的例子是2 4 6 -1并且返回需要是12 10 6。-1充当塞子。

所以基本上我的代码打印出来6 10 12了，我需要找到一种方法来反转这个输出。有任何想法吗？

在我的并行算法书中，PRAM 模型有以下伪代码：

但是...PRAM 指定所有处理器必须对不同的数据执行相同的指令。

所以这个程序只能在 CREW PRAM 模型上执行？

或可在 EREW 模型上执行，则具有奇数 ID 的处理器将执行

当具有偶数 id 的处理器执行（例如）NOP 指令时？

我有一个根本不支持本地内存的 Mali GPU。每次我运行由本地内存组成的代码时，它都会给我一些来自设备的错误。所以，我想将我的代码转移到只使用全局内存的版本。我在想是否可以仅在 GPU 上使用全局内存运行前缀总和/并行减少算法。

EDITED：我正在调试错误并发现一个奇怪的事情是一个特定的行给出了错误。我有这样的电子线：

lid 是本地 id，我使用 qork groups 大小为 32。我发现突出显示的行是错误的原因。我尝试使用固定值，发现不能lm_sum在语句的右侧使用。如果我这样做，那会给我一个错误。例如，这一行也给了我错误： int temp= lm_sum[0][0]

知道发生了什么吗？

错误：