火花计算产生多少额外开销?

12

在《并行与并发编程》一书中的这张图片:http://chimera.labs.oreilly.com/books/1230000000929/ch03.html#fig_kmeans-granularity,起初似乎表明触发过多会带来严重的开销。但如果你仔细看纵轴,你会注意到它已经放大到感兴趣的部分。实际上,所示最好和最坏情况性能之间的比率约为80%,这并不算太糟糕。

总体而言,确定如何以及以多大的块是困难的,容易出错,极度依赖应用程序,并且可能会在明年购买具有更多处理能力的新计算机时发生变化。我更喜欢始终使用最精细的元素和rpar,并接受25%的开销。

触发的开销是否可能比此图显示的要高得多?(特别是如果我总是在二叉树上执行fold而不是列表,因此第二个项目“顺序工作量”的数量就不适用)


针对Don Stewart回答的问题更新:

闪电池是否只包含一个队列,所有处理器都难以访问?还是有很多个?

例如,如果我拥有一台带有无限处理器的计算机和一个二叉树,并且我想对所有叶子进行求和,如:

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(#叶子节点数量)的时间内运行吗?还是在 O(深度)的时间内运行? 有没有更好的编写方式?

如果我为了得到令人满意的答案而过于抽象,请让我知道。 我对 Haskell 并行性的心理模型仍然非常模糊。


使用并行运行时,每个使用的 HEC(处理器)都有一个队列,如果我没记错的话。这一切都在 Don 提供的论文中有所描述。 - Alp Mestanogullari
1个回答

9

一颗火花很便宜。

  • 火花池。每次调用par a b都会将惰性求值a添加到(当前HEC的)火花池中;这个惰性求值被称为“火花”。[1]

如果任何一个HEC变为空闲状态,则可以检查池并开始评估其顶部上的thunk。

因此,激发大约是添加到队列的指针。

为使火花分配更加便宜和异步,我们将每个HEC的火花池重新实现为有界的工作窃取队列 (Arora等人1998; Chase和Lev 2005)。工作窃取队列是一种无锁数据结构,具有某些吸引人的属性: 队列的所有者可以在没有同步的情况下从一端推入和弹出,同时其他线程可以从队列的另一端“窃取”, 只产生单个原子指令。

也在[1]中。

问题在于您可以轻松地创建数十亿个火花。此时,您只是将程序变成了一个队列构建器——所有时间都花费在更新指向代码的火花池中。
一个好的建议是进行分析,确定实际上有多少火花被转化为工作,并使用这些信息来指导何时停止火花的阈值。

通过不锁定Spark池,例如每个处理器一个池,并依赖于字写入是原子性的,可以使Spark更加便宜。 - augustss
好观点Lennart。已更新为描述现在使用的无锁队列。 - Don Stewart
@DonStewart 哇,谢谢!这个答案给了我一些启示,但我还是不是很清楚。你能看看我的更新问题吗? - dspyz

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接