问题标签 [data-parallel-haskell]

我正在尝试并行合并两个列表。我有两个排序列表[(i, j, val)]。列表按 排序j，对于相同j，按 排序i。如果两个列表包含相同(i, j)的值，则将它们的值相加并组合为一个，例如，如果第一个列表包含(i, j, val_1)，第二个列表包含，(i, j, val_2)则将两个组合在一起(i, j, val_1 + val_2)。

合并是高度顺序的，经过搜索，我找到了这篇论文。本文的想法是使用二进制搜索来获取最终列表中元素的排名。假设我们在i第一个列表中的第 th 位置，所以我们的(i - 1)元素小于第一个列表中的当前元素，并对第二个列表中该元素的位置执行二进制搜索（假设该位置为j）。所以我们当前元素在最终列表中的位置将是i + j - 1( i - 1 + j - 1 + 1)。我为此使用 dph-par 编写了一个 Haskell 代码，但我有点坚持更新。我有两个清单

在更新这两个列表之后，我们应该有

搜索引擎

主文件

有人可以帮我更新一下。我不确定，但该算法涉及大量数据移动，因此请为此目的建议我更好的方法。

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

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

我正在使用 GHC 7.4.1 尝试编译使用 Repa 的程序。但是在编译过程中，我的内存不足。使用ghc -v，我可以看到它陷入了 SpecConstr 阶段。

SpecConstr 是 GHC 的核心到核心转换之一。Simon Peyton Jones在这里有一个很好的描述，并且这里有一些代码，但是对我来说这很慢，因为我对 GHC 的内部工作不是很熟悉。

我希望能够以某种方式帮助编译器 - 有没有办法告诉它卡在哪里？或者，有没有办法限制这个阶段的内存使用，直到我可以在更大的机器上重新编译？

谢谢，乍得

更具体地说，我有以下看起来无害的小 Repa 3 程序：

在我的 2Ghz core 2 duo 笔记本电脑上处理 640x420 图像需要这么多时间：

我知道肯定有什么问题，因为我在使用 Repa 2 的更复杂的算法上获得了更好的性能。在该 API 下，我发现的重大改进来自于在每次数组转换之前添加对“强制”的调用（我理解表示每次调用映射、卷积、遍历等）。我不能完全弄清楚在 Repa 3 中要做的类似事情 - 事实上，我认为新的表现类型参数应该确保在何时需要强制数组时没有歧义？新的一元接口如何适应这个方案？我已阅读 Don S 的精彩教程，但 Repa 2 和 3 API 之间存在一些关键差距，在线 AFAIK 很少讨论。

更简单地说，是否有一种影响最小的方法来解决上述程序的效率问题？

我一直在对 Data Parallel Haskell 进行大量研究，并发现了两种单独的并行数组类型。该[::]类型似乎更多地出现在研究论文中，似乎是理想的类型，但PArray似乎无处不在。关于该主题的 wiki 页面非常清楚地表明，[::]不能将类型数组传递给未矢量化的代码。为什么？为什么会有这种中间PArray类型？这对我来说似乎完全是多余的。wiki 将其称为“平面数组”，但矢量化的全部意义在于使并行数组平面化。

更新：在阅读了更多论文、文档和源代码后，我更加困惑。[::]或其同义词PArr似乎在GHC.PArr中作为平面数组实现，而PArray在多个地方称为“平面”的中间类型在Data.Array.Parallel.PArray.Base和从那里导入的其他模块中实现为一个数据系列，使用我阅读的许多论文中描述的扁平化转换。为什么平面阵列不平坦而嵌套阵列不平坦？

更新2：经过更多研究，我发现文档完全是一团糟。wiki 页面近一年没有任何内容更新，与 hackage 文档相矛盾（请参阅Data.Array.Parallel.Prelude，其中明确表示不要导入特殊前奏），并且通常已过时。GHC Trac 页面也已过时，例如，包括 DPH 软件包指南，其中提到了至少就 Hackage 而言（我没有，也不完全没有地方可以查看）其他地方），不存在，也没有提到像 dph-lifted-vseg 这样的包。

更好的一点是，我相信我现在理解了第一次更新的答案， GHC.PArr中的这部分评论暗示了这一点：

我的猜测是，启用矢量化后，该模块会自动替换为使用扁平化转换的另一种表示形式。这甚至可能类似于

，解决了我原来的问题。然而，后一点不仅没有多大意义（为什么[::]在向量化关闭时限制为平面数组类型？），而且除了上面提到的评论之外，我没有发现任何证据支持这两种理论。似乎学习任何东西的唯一可靠方法是查看 GHC 源，考虑到它的大小和复杂性，这是我渴望做的事情，即使我确信我会成功。

我试图使用 DPH 实现 nqueens 问题，但最终出现 Can't vectorise GHC.Prim.Int# 错误。当我搜索错误时，我发现了一个 GHC 错误，它讨论了用于模式匹配的矢量化文字 (http://haskell.1045720.n5.nabble.com/GHC-5702-Can-t-vectorise-pattern-matching-on -numeric-literals-td5076659.html）。我不确定这是否是同一个错误。我的代码如下，

如果我做错了什么，请告诉我。我正在使用 GHC 7.4.1。

提前致谢。

2012.4.0.0 Haskell有人在平台上使用数据并行 Haskell吗？

我是 Haskell 初学者 - 但想尝试从列表切换到并行数组。

当我尝试跑步时

我遇到了一个构建问题bmp.1.2.3.1：

当然这是某种类型的版本不匹配 - 但不确定该怎么做。有高手吗？

我正在尝试使用 Data Parallel Haskell 运行一些简单的实验，但我显然有一些选项错误。即使我尝试一些非常简单的事情，比如

我得到一个例外

假设我设置错误 - 但是......

在尝试使用 GHCi 和运行使用 GHC 生成的可执行文件时，我都会遇到同样的错误。

我最近阅读了有关即将在和库中进行广义流融合的论文。这似乎是一个非常有趣的发展。我现在开始尝试（从 GHC 7.6 开始，并计划在它出现时升级到 7.8 SIMD 版本）。我还从库文档中看到它可以完成并行数组工作。与 GHC 7.4相比，它似乎是成熟的版本。现在这似乎已经成熟，我想知道从 GHC 7.6 开始，软件包之间的主要优缺点是什么。我搜索了 StackOverflow 和 google，但找不到 和 之间的比较。因此，这个问题。vectorDPHDPHRepaRepaDPHDPHRepaDPHRepaDPH

我正在编写代码来做一个子集产品：它需要一个元素列表和一个指标变量列表（长度相同）。产品是在树中计算的，这对我们的应用程序至关重要。每个产品都很昂贵，所以我的目标是并行计算树的每个级别，按顺序评估连续的级别。因此没有任何嵌套的并行性正在发生。

我只有一个函数中的 repa 代码，靠近我的整体代码的顶层。请注意，subsetProd不是一元的。

步骤：

1. 将列表分块成对（无并行性）
2. 压缩分块列表（无并行性）
3. 将乘积函数映射到此列表（使用 Repa 映射），创建延迟数组
4. 调用 computeP 并行评估地图
5. 将 Repa 结果转换回列表
6. 进行递归调用（在输入大小一半的列表上）

编码：

整个程序是用

根据这些说明，在 GHC 7.6.2 x64 上。

我运行我的程序（子集）使用

8 秒后：

当我增加 -N 参数时，我的代码确实变慢了（-N1 为 7.628 秒，-N2 为 7.891 秒，-N4 为 8.659 秒）但我创建了 0 个火花，这似乎是为什么我没有得到任何并行性。此外，使用大量优化进行编译有助于运行时，但对并行性没有帮助。

Threadscope 确认没有对三个 HEC 进行任何认真的工作，但垃圾收集器似乎正在使用所有 4 个 HEC。

那么，为什么 Repa 不产生任何火花呢？我的产品树有 64 个叶子，所以即使 Repa 为每个内部节点制作了一个火花，也应该有大约 63 个火花。我觉得这可能与我使用封装并行性的 ST monad 有关，尽管我不太确定为什么这会导致问题。也许火花只能在 IO monad 中创建？

如果是这种情况，是否有人知道我如何执行这个树产品，其中每个级别都是并行完成的（不会导致嵌套并行，这对我的任务来说似乎是不必要的）。一般来说，也许有更好的方法来并行化树产品或更好地利用 Repa。

解释为什么运行时间随着我增加 -N 参数而增加的加分点，即使没有创建火花也是如此。

编辑 我将上面的代码示例更改为我的问题的编译示例。程序流程几乎与我的真实代码完美匹配：我随机选择一些输入，然后对它们进行子集乘积。我现在正在使用身份单子。我已经尝试对我的代码进行许多小的更改：是否内联，是否使用爆炸模式，使用两个 Repa 列表和一个 Repa zipWith 与按顺序压缩列表并使用 Repa 映射等的变化，等等，这些都没有帮助。

即使我在示例代码中遇到了这个问题，我的实际程序也要大得多。