问题标签 [prefix-sum]

有谁知道 cub::scan 支持的最大大小是多少？我得到了超过 5 亿输入大小的核心转储。我想确保我没有做错什么...

这是我的代码：

我需要通过树减少来了解前缀总和，并为此在 C 中编写 MPI 代码。我已经通过递归加倍或扫描知道前缀和，并且有一些 MPI 编程背景。这是我应该了解的树减少的结构：

任何人都可以建议一些通过树减少来学习前缀总和的好材料，或者在这里解释一下？我用谷歌搜索了它，但找不到一个有明确解释的好笔记！

我重写了从 Java 到 Swift 解决 GenomicRangeQuery 任务的代码。Jave 中的代码获得 100/100 分，但 Swift 中的代码未通过所有性能测试。我试图理解为什么，因为代码中的逻辑是相同的。我想知道为什么 Swift 代码执行这么长时间。我是否在我不知道的快速代码中使用了一些非常慢的部分。请查看从此处复制的 Java 代码。

在这里将相同的代码重写为 Swift 2.1

有人知道为什么当 Java 代码通过所有测试时，这段 Swift 代码无法通过所有性能测试吗？我想我在 Swift 中遇到了一些敏感的瓶颈，但我不知道在哪里。

如果有人不知道 codility，这是任务的链接。

我一直在尝试运行计算着色器 - 前缀和演示提供于：

https://github.com/openglsuperbible/sb7code/blob/master/src/prefixsum/prefixsum.cpp

我使用了确切的代码：

这是着色器：

问题是输出写入 4 个位置中的 1 个：

这是输入：

有没有什么优雅的方法来处理计算着色器中的数组边距？（考虑到您应该在着色器中硬编码工作组的维度）

考虑以下着色器代码，如果使用 glDispatchCompute(1,1,1) 调用计算 2048 数组的前缀和：

但是如果我想计算一个包含 3000 个元素的数组的前缀总和呢？

我试图通过查看 Codility 的前缀和课程中提供的示例来掌握前缀和概念背后的想法（蘑菇选择器问题）

我的理解是，整个概念基于一个简单的属性，其中要找到数组 A 的两个位置 A(pos_left, pos_right) 之间的所有元素的总和，使用第二个数组 P，其中所有元素连续求和，搜索的位置总和计算为
value(P(pos_right + 1)) - value(P(pos_left))。

问题
非空向量表示的每个地方都有一条蘑菇街。给定拾取器的初始位置及其移动范围，寻找可能收集的最大蘑菇数量。

看这个例子，我不明白循环构造背后的逻辑。任何人都可以澄清这个算法的机制吗？

其次，我发现这个例子中的 positoin 索引非常混乱和麻烦。在开头用零“移位”带有前缀和的向量是常见的做法吗？（在 python 中，向量中的元素计数是从 0 开始的，这一事实已经引起了一些混乱）。

解决方案

我已经为一个小数组运行了一些示例A= [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]，选择了位置 k=5 和范围 m = 3。我不明白创建要通过两个循环检查的范围的逻辑。

我得到以下循环参数

范围各不相同。为什么？

调试版本

我正在尝试实现三相并行扫描，如 Programming Massively Parallel Processors 3rd edition 的第 8 章所述（有任何代码行，但只有指令）。该算法只允许使用 1 个块中的最大线程数，并且它受到共享内存大小的限制，因为所有元素都必须适合共享内存

经过一些调试，当我使用大量元素（例如 8192 和 1 个以上的线程）时，我在阶段 3 的求和过程中遇到了一个问题（参见下面的代码）。

算法的图形概念如下：

在下面你可以看到内核代码：

如果我在块中使用一个线程和 8192 个元素，它可以完美运行，但如果我使用超过一个线程，则 XY[5793] （或 X[5793] 完成并存储结果时）的结果是错误的。它有 4096 个元素和一个或多个线程，最多 1024 个线程。如果我使用 int 而不是浮点数，它甚至适用于具有一个或多个线程的 8192 个元素。

我也尝试在 MATLAB 中进行验证，这些是输出比较：

• X[5973] = 1678811 5 ---- MATLAB
• X[5973] = 1678811 4 ---- CPU
• X[5973] = 1678811 6 ---- GPU

正如我们所看到的，CPU 结果也与 MATLAB 不同，所以在这些结果之后，我认为问题出在浮点加法上，但我告诉你，我用有序的“x.00”浮点数填充了输入数组（例如 {1.00, 2.00, 3.00, 4.00 ..... 8192.00}）。

另一个问题是关于性能的，主机代码总是比内核代码快，有这些配置参数和这些输入，是否正常？

如果您需要完整的源代码，可以在这里找到

在并行编程和 GPU 的上下文中，我们有一个称为数组的Prefix-Sum数组。在动态映射中，每个线程对 Prefix-Sum 执行二进制搜索以找到相应的 Work-Item。

这对我来说是一个问题，线程如何知道将搜索哪个工作项或工作单元？

鉴于以下伪代码，我想知道在尝试确定时间复杂度时我的思考过程是否正确。

该算法将循环 n 次，并且由于最后一次迭代将需要最多的计算量（n 次计算），因此该算法将总共进行n^2 + f(n)计算。其中是次数或更少f(n)的多项式。因此这个算法是二次的。n^2 O(n^2)

我无法理解幼稚前缀总和的 cuda 代码。

这是来自https://developer.nvidia.com/gpugems/GPUGems3/gpugems3_ch39.html的代码 在示例 39-1（天真扫描）中，我们有这样的代码：

我的问题是

1. 为什么我们需要创建一个共享内存临时？
2. 为什么我们需要“pout”和“pin”变量？他们在做什么？既然我们这里只用了一个block，最多1024个线程，那我们能不能只用threadId.x来指定block中的元素呢？
3. 在CUDA中，我们是不是用一个线程做一个加法操作？是不是这样，如果我使用 for 循环（给定一个线程用于数组中的一个元素，循环 OpenMP 中的线程或处理器），一个线程可以在一次迭代中完成什么？
4. 我之前的两个问题可能看起来很幼稚......我认为关键是我不明白上述实现与伪代码之间的关系如下：

for d = 1 to log2 n do for all k in parallel do if k >= 2^d then x[k] = x[k – 2^(d-1)] + x[k]

这是我第一次使用CUDA，如果有人能回答我的问题，我将不胜感激......