引发多少开销？

Question

"并行和并发编程"中的这个图表:http://chimera.labs.oreilly.com/books/1230000000929/ch03.html#fig_kmeans-granularity起初似乎表明存在严重的开销,引发太多.但是如果仔细观察y轴,你会发现它已被放大到有趣的部分.事实上,最佳和最差案例表现之间的比例约为80%,这也不算太糟糕.

一般来说,确定块的方式和数量是困难的,容易出错,极其特定于应用程序,并且明年当您购买具有更强处理能力的新计算机时可能会发生变化.我更倾向于总是使用rpar来获得最细粒度的物品并以25%的开销生活.

引发的开销通常会产生比此图所示更糟糕的成本吗？(特别是如果我总是折叠二叉树而不是列表,那么关于"顺序工作量"的第二个要点不适用)

---

针对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(#leaves)时间运行吗？或O(深度)时间？有没有更好的方法来写这个？

如果我抽出太多东西以获得满意的答案,请告诉我.我对haskell并行性如何工作的心理模型仍然非常模糊.

Answer 1

单个火花非常便宜.

• 火花池.每次调用都会par a b将thunk a添加到(当前HEC的)Spark Pool中; 这个thunk被称为"火花".[1]

如果任何HEC变为空闲,它可以检查池并开始评估顶部的thunk.

因此,引发大致是添加一个指向队列的指针.

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

也在[1]

问题是你可以轻松创造数十亿的火花.此时,您只是将程序转换为队列构建器 - 所有时间都花在使用指向代码的指针更新spark池.

好的建议是分析,确定实际上有多少火花被转化为工作,并用它来指导何时停止火花的阈值.