问题标签 [reduction]

我正在努力使代码并行运行（CUDA）。简化后的代码是：

我遇到的问题是sum+=f因为它需要sum在线程之间共享。__shared__我在声明 sum ( ) 时尝试使用该参数__shared__ float sum，但这不起作用（它没有给我正确的结果）。我也听说过减少（并且知道如何在 OpenMP 上使用它），但不知道如何在此处应用它。

任何帮助将不胜感激。谢谢！

我想评估以下表达式：

使用β还原。

答案是：

但我不明白第二阶段：

从这里：(λx.y)((λz.zz)(λw.w))到这里(λx.y)((λw.w)(λw.w))

我们在那里做什么？根据我的理解，我需要使用α-等价规则。

我刚开始学习openMP，我有以下...

我已经发现（我认为）如果我想正确添加它们，我需要减少 co(k) 和 si(k)，但据我所知，你不能有一个像在减免条款内。我该怎么做呢？

我从斯坦福找到了这个使用共享内存的并行缩减代码。

该代码是 1<<18 个元素的示例，它等于 262144 并得到正确的结果。

为什么对于某些数量的元素我得到正确的结果，而对于其他数量的元素，如 200000 或 25000，我得到的结果与预期不同？在我看来，它总是在指定所需的线程块

什么是减少变量？谁能给我一些例子？

下面的内核计算声压场，每个线程计算它自己的pressure向量私有实例，然后需要将其汇总到全局内存中。我很确定计算pressure向量的代码是正确的，但我仍然无法让它产生预期的结果。

关于数据维度的一些注意事项： 线程总数将在 100 到 2000 之间变化，但有时可能超出此区间。
groupSize将取决于硬件，但我目前使用的值介于 1(cpu) 和 32(gpu) 之间。
HYD_DIM_TOTAL在编译时已知并且在 4 到 32 之间变化（通常但不一定是 2 的幂）。

这个缩减代码有什么明显的错误吗？

PS：我在带有 AMD APP SDK 2.8 的 i7 3930k 和 NVIDIA GTX580 上运行它。

假设我有一个f接受一些输入并产生一个数字的函数。在函数f中，根据输入创建一个列表，然后将其减少（例如使用foldl' g）以产生最终输出数。因为中间列表毕竟是要归约的，所以是否可以应用reduce函数g 而不表示中间列表。这里的目标是限制用于存储（或表达，如果“存储”一个不太准确的词）列表的内存。

为了说明这一点，此函数为中间列表foldPairProduct占用O(N1 * N2)空间（由于表达式和惰性求值，消耗的空间可能更复杂，但我认为它是成比例的或更糟）。这N1, N2是两个输入列表的大小。

该逻辑的另一种实现是 foldPairProduct'，它占用O(2 * 2)空间。

除了它接受多个列表作为输入之外，它foldCrossProduct的实现类似于它，这种情况更加严重。foldPairProduct中间列表的空间复杂度（仍然是命令式语言的意义上）是O(N1 * N2 * ...* Nk)，其中k是 的长度[[a]]。

如果我们遵循 的实现思路foldPairProduct'，空间复杂度将为k^2，空间效率更高。我的问题是：

1. 我实现foldPairProduct'了一对列表。但是，似乎为任意数量的列表实现它并不简单。

2. 我的意思不是将 Haskell 与命令式语言进行比较，但是是否有一个使用常量空间的实现（或者换句话说，不表达上述长度的中间列表）？也许 Monad 会有所帮助，但我对它很陌生。

3. 编译器真的发挥了它的魔力吗？也就是说，它注意到列表是中间的并且要减少，并且确实找到了一种节省空间的方法来评估它。毕竟，我认为惰性求值和编译器优化就是为此而设计的。

4. 欢迎任何评论。谢谢。

更新 1

性能测试证实了对 和 的“空间复杂度”的分析foldPairProduct，foldCrossProduct基于改变输入大小N1, N2, N3，并观察了 GC 复制的字节数。

性能测试证明了foldPairProduct'令人惊讶地显示N1 * N2甚至更差空间使用的分析。这可能是由于递归调用的评估效率低下。结果附在下面（ghc 设置与 Yuras 所做的相同）。

更新 2

当我从评论和答案中学习时，更新了一些进一步的实验。对于foldPairProduct，使用的总内存与 Daniel Fischer 解释的空间复杂度一致。

因为foldCrossProduct，尽管 Daniel 的复杂性分析对我来说很有意义，但结果并没有显示出线性的内存使用情况。按照丹尼尔的建议，交换了x <- xsand y <- crossproduct ys，它确实实现了线性空间复杂度。

对于foldCrossProduct (max) [[1..100],[1..n], [1..1000]]，当 n = 100、1000、10000、100000 时，使用的内存为 2、2、3、14 MB。

foldPairProduct [1..n] [1..10000]

foldPairProduct [1..10000] [1..n]

foldPairProduct [1..n] [1..n]

foldCrossProduct (max) [[1..n], [1..100], [1..1000]]

foldCrossProduct (max) [[1..100], [1..n], [1..1000]]

foldPairProduct' [1..n] [1..n]

我在 bash 中解决了以下问题，但考虑到我需要减少的文件大小，我觉得它效率很低而且很慢。希望有人知道如何在 Python 中做同样的事情并希望加快速度。

最初的问题是减少非常大的文本文件（50-60 百万行，制表符分隔的列）。其中一列被视为键，即我们确定文件中有多少具有唯一键的行，然后随机选择其中的一个百分比（例如，如果减少 75%，则为总数的四分之一）附加到一个新文件，将保留我们的结果。我们继续检查其余的键，随机化然后将包含每个唯一键的所有行减少相同的百分比。如果无法减少 - 我们只需将所有行转移到结果文件中。

正如我所说，我的 bash 脚本运行良好，但速度很慢，并且将各种 awk 和 grep 结构串在一起。无论如何，Python 应该以一种更优雅的方式来处理这个问题，并且不会过多地牺牲内存（同样，在这种情况下，我们正在处理 50+ 百万行文件）。任何建议/技巧都会有所帮助！谢谢！

令 x1 为 image1 的向量（灰色），x2 为 image2 的向量（灰色），以此类推 xn 为 imagen 的向量（灰色）。比如说，所有的图像大小由 r 行和 c 列 (r*c) 表示

所以，X = [x1, x2, x3, .... xn]。

正如许多文献表明的那样，要减少 n。其他文献也倾向于减少 r*c。

更喜欢哪一个。

为什么我会收到此错误？

(3) 错误 C3037: 'result' : 'reduction' 子句中的变量必须在封闭上下文中共享

我试着用谷歌搜索……所有的例子都是这样的。如果这很重要，我也会在 Visual Studios 2012 中对此进行编码。我讨厌问这样的问题，但这阻止了我继续。

固定：添加并行

#pragma omp parallel for private(buffer) reduction(+:result)