12

“并行和并发编程”中的这张图：http ://chimera.labs.oreilly.com/books/1230000000929/ch03.html#fig_kmeans-granularity起初似乎表明火花过多会产生严重的开销。但是，如果您仔细查看 y 轴，您会注意到它已被放大到有趣的部分。事实上，显示的最佳和最差情况性能之间的比率约为 80%，这还不算太差。

一般来说，弄清楚如何分块以及分块的数量是困难的、容易出错的、极其特定于应用程序的，并且明年当你购买一台具有更强处理能力的新计算机时可能会发生变化。我更愿意始终将 rpar 与最细粒度的项目一起使用，并承受 25% 的开销。

引发火花的开销通常会产生比此图中显示的更糟糕的成本吗？（特别是如果我总是折叠二叉树而不是列表，所以关于“顺序工作量”的第二个要点不适用）

针对唐斯图尔特的回答更新了问题：

火花池是否只包含一个所有处理器都难以访问的队列？还是有很多？

例如，如果我有一台具有无限处理器和二叉树的计算机，并且我想对所有叶子求和，如下所示：

data Node = Leaf Int | Branch Node Node

sumL (Leaf x) = x
sumL (Branch n1 n2) = let (x,y) = (sumL n1, sumL n2) in (x `par` y) `seq` (x + y)

这个程序会在 O(#leaves) 时间内运行吗？还是 O（深度）时间？有没有更好的方法来写这个？

如果我抽象太多而无法获得满意的答案，请告诉我。我对 haskell 并行性如何工作的心智模型仍然非常模糊。

4

1 回答 1

9

一个火花非常便宜。

  • 火花池。每次调用都会par a b将 thunk a 添加到（当前 HEC 的）Spark Pool；这种重击称为“火花”。[1]

如果任何 HEC 空闲，它可以检查池并开始评估顶部的 thunk。

所以火花粗略地添加了一个指向队列的指针。

为了使 spark 分发更便宜和更异步，我们将每个 HEC 的 Spark Pool 重新实现为有界工作窃取队列（Arora et al. 1998; Chase and Lev 2005）。工作窃取队列是一种无锁数据结构，具有一些吸引人的特性：队列的所有者可以在不同步的情况下从一端推送和弹出，同时其他线程可以从队列的另一端“窃取”仅产生一条原子指令.

也在[1]

问题是你可以很容易地创造出数十亿的火花。那时，您只是将您的程序变成了一个队列构建器——所有时间都花在使用指向代码的指针来更新火花池。

好的建议是分析，确定有多少火花实际上变成了工作，并用它来指导何时停止火花的阈值。

于 2014-05-27T07:30:04.930 回答