问题标签 [prefix-sum]

我正在寻找使用 CUDA 或 OpenCL 的前缀和/扫描算法的全局内存实现。所有的实现都是使用本地内存完成的。谁能帮我解决算法以及我应该如何进行？

我和我的朋友正在做一个简单的 Python 项目。实际上，我们正在以自己的方式实现前缀并行求和算法。

我们正在创建和处理一个格式非常奇怪的二叉树。我们希望将此格式转换为 Tree 打印库/软件（如 ete2）所接受的格式。

因此，树的每一层都以这种方式推送到列表中

在我们的格式中，每个内部列表（树的级别）都有偶数个节点或叶子。

例如，假设我们有这个输入：[1, 2, 3, 4, 5]. 这将产生以下输出列表：[[1, 2, 3, 4], [3, 7], [10, 5], [15]]

上述输出示例的问题是，有时叶子不在最后一级，但它们包含在上一级列表中。这使得很难处理列表列表并将节点与叶子区分开来并将它们安排在正确的位置。

我们希望将其可视化如下：

http://i.imgur.com/BKrqNZi.png

其中括号中的数字是节点，其他数字是叶子。

为了生成这个输出树，我们想使用一个 Tree 绘图库。他们中的大多数人都期望这种格式：[root, [left], [right]]

因此，在我们的示例中，我们的格式应该是这样的：

因为我们目前无法重写代码的整个逻辑，所以我们正在寻找一种巧妙的方法将我们奇怪的格式转换为那个格式。

欢迎任何想法。非常感谢您提前。

我想在 c# 中编写一个并行前缀总和。我使用了这个算法：

我在 c# 中的最终代码是：

赖特输出应该是：[4,7,15,17,26,27,30,35,41,44]
但我的输出代码是：[4,7,8,2,9,1,3,5, 6,3]
有人知道我的代码有什么问题吗？
编辑：
我发现每个处理器都在本地看到数组 A。现在的问题是如何在全局范围内定义数组 A 以使所有处理器都看到一个数组？

我正在使用 openmp 来并行化我的代码。我有一个原始数组：

和一个标记数组：

使用数组 M 我可以在这个打包数组中压缩我的原始数组：

我想使用多线程方法解决这个问题。C++ 的库“推力”解决了这个问题，但我无法为 Fortran 找到类似的工具。是否有一个库，比如 C++ 的“推力”，我可以用来执行流压缩？或者，是否有一种我可以使用 fortran 和 openmp 自己编写的算法来解决这个问题？

是否有任何数据结构能够返回数组的前缀和 [1]、更新元素以及向数组中插入/删除元素，所有这些都在 O(log n) 中？

[1] “前缀总和”是从第一个元素到给定索引的所有元素的总和

例如，给定非负整数数组，8 1 10 7前三个元素的前缀和为19( 8++ 1) 10。将第一个元素更新为7，作为第二个元素插入3并删除第三个元素给出7 3 10 7. 同样，前三个元素的前缀总和将是20.

对于前缀和和更新，有Fenwick 树。但我不知道如何用它处理 O(log n) 中的添加/删除。

另一方面，有几种二叉搜索树，例如红黑树，它们都以对数时间处理更新/插入/删除。但我不知道如何维护给定的排序并在 O(log n) 中进行前缀求和。

将并行算法分配给前缀和问题时遇到一些问题。我正在使用 openMP 进行并行实现。我在c中有如下代码。

结果显示：

请指教。谢谢。

我在 GPU Gems 3, Chapter 39: Parallel Prefix Sum (Scan) with CUDA一书中编写了一段代码来调用内核。

然而，我得到的结果是一堆负数而不是前缀扫描。

我的内核调用是错误的还是 GPU Gems 3 书中的代码有问题？

这是我的代码：

我有一个关于数字序列的作业。给定从1到MAX的n 个元素数组。我们可以选择任何数字成为开始。我们可以将start乘以2，或者将其除以 2，但如果 start 已经是奇数，我们就不能将它除。任务是我们必须最小化数组中每个数字的差异总和。 例如 arr[]={2,4,7,32,16} 输出为 1，因为我们可以选择 1 作为开始。对于每个元素，我们必须使这个数字更大并且更接近元素。 我们遍历数组。 对于 n=0；元素是 2。所以我们将start乘以2，1 次start=2





所以差是2-2=0；
对于 n=1；元素是 4。所以我们将start乘以2，1 次start=4，所以差是 4-4=0；
对于 n=2；元素是 7。所以我们将start乘以2，1 次start=8，所以差值是 8-7=1；
对于 n=3；元素是 32。所以我们将start乘以2，2 次start=32所以差是 32-32=0；
对于 n=4；元素是16。所以我们将start除以2，1次start=16，所以差是16-16=0；所以总差异=0+0+1+0=1；

如果我们选择 start=3 那么它就变成
For n=1; 元素是 4。所以我们乘以startby 2, 1 time start=6所以差是 6-4=2;
对于 n=2；元素是 7。所以我们将start乘以2，1 次start=12，所以差值是 12-7=5；
对于 n=3；元素是 32。所以我们将start乘以2，2 次start=48所以差是 48-32=16；
对于 n=4；元素是16。所以我们把start除以2，1次start=24，所以差是24-16=8；所以总差异=2+5+16+8=31；

我们可以看到，对于start=1 ，通过将每个数字从1强制强制为MAX，输出比所有数字都最小。

为了解决这个问题，我有了主意。

1. 首先，我们选择从1到MAX的所有奇数。
   
2. 然后我暴力破解每个元素的所有可能开始以获得最小值。

这是帕斯卡代码

它适用于小MAX，但解决方案的提示说该解决方案使用前缀和，O（MAX / 2）。虽然我的解决方案是 O( MAX /2*N)。我不知道在哪里插入前缀总和。我们怎么能做到这一点？提前致谢！

大多数并行缩减算法使用共享（本地）内存。

英伟达、AMD、英特尔等。

但是，如果设备没有共享（本地）内存。

我该怎么做？

如果我使用相同的算法但在全局内存上存储临时值，它会正常工作吗？

我正在寻找 OpenCL 中 scan(prefixsum) 的快速实现。我发现最好的东西是在 Nvidia SDK 中，但它很旧（2010 年）。有谁知道 OpenCL 中 Scan 的任何其他实现？