在Haskell中没有使用天真合并排序并行化的加速

Question

注意:这篇文章完全改写了2011-06-10; 感谢彼得帮助我.另外,如果我不接受一个答案,请不要被冒犯,因为这个问题似乎相当开放.(但是,如果你解决它,你当然会得到复选标记).

另一位用户发布了有关并行化合并排序的问题.我以为我会写一个简单的解决方案,但唉,它并不比顺序版快得多.

问题陈述

合并排序是一种分而治之的算法,其中计算的叶子可以并行化.

代码的工作原理如下:将列表转换为树,表示计算节点.然后,合并步骤返回每个节点的列表.从理论上讲,我们应该看到一些重要的性能增益,因为我们将从O(n log n)算法转变为具有无限处理器的O(n)算法.

当参数l(水平)大于零时,计算的第一步是并行化的.这是通过[经由可变完成STRAT ]选择RPAR策略,这将使得子计算归并"×发生在具有平行归并" Y.然后,我们合并结果,并使用rdeepseq强制进行评估.

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)

instance NFData a => NFData (Tree a) where
    rnf (Leaf v) = deepseq v ()
    rnf (Node x y) = deepseq (x, y) ()

listToTree [] = error "listToTree -- empty list"
listToTree [x] = Leaf x
listToTree xs = uncurry Node $ listToTree *** listToTree $
    splitAt (length xs `div` 2) xs

-- mergeSort' :: Ord a => Tree a -> Eval [a]
mergeSort' l (Leaf v) = return [v]
mergeSort' l (Node x y) = do
    xr <- strat $ runEval $ mergeSort' (l - 1) x
    yr <- rseq $ runEval $ mergeSort' (l - 1) y
    rdeepseq (merge xr yr)
    where
        merge [] y = y
        merge x [] = x
        merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys)
                            | otherwise = y : merge (x:xs) ys
        strat | l > 0 = rpar
              | otherwise = rseq

mergeSort = runEval . mergeSort' 10

通过仅评估几个级别的计算,我们应该具有良好的并行通信复杂性 - n的一些常数因子顺序.

结果

在此处获取第4版源代码[ http://pastebin.com/DxYneAaC ],并使用以下命令运行它以检查线程使用情况或后续命令行以进行基准测试,

rm -f ParallelMergeSort; ghc -O2 -O3 -optc-O3 -optc-ffast-math -eventlog --make -rtsopts -threaded ParallelMergeSort.hs
./ParallelMergeSort +RTS -H512m -K512m -ls -N
threadscope ParallelMergeSort.eventlog

24核X5680 @ 3.33GHz的结果几乎没有改善

> ./ParallelMergeSort 
initialization: 10.461204s sec.
sorting: 6.383197s sec.
> ./ParallelMergeSort +RTS -H512m -K512m -N
initialization: 27.94877s sec.
sorting: 5.228463s sec.

在我自己的机器上,一个四核Phenom II,

> ./ParallelMergeSort 
initialization: 18.943919s sec.
sorting: 10.465077s sec.
> ./ParallelMergeSort +RTS -H512m -K512m -ls -N
initialization: 22.92075s sec.
sorting: 7.431716s sec.

在threadscope中检查结果可以很好地利用少量数据.(但遗憾的是,没有明显的加速).但是,当我尝试在较大的列表上运行它时,如上所述,它在一半时间内使用大约2个cpus.似乎很多火花都被修剪了.它对内存参数也很敏感,其中256mb是最佳点,128mb为9秒,512为8.4,1024为12.3!

解决方案我正在寻找

最后,如果有人知道一些高功率的工具,我会很感激.(伊甸园？).我对Haskell并行性的主要兴趣是能够为研究项目编写小型支持工具,我可以在实验室的集群中使用24或80核心服务器.由于它们不是我们小组研究的重点,我不想花太多时间在并行化效率上.所以,对我来说,更简单更好,即使我最终只能获得20%的使用率.

进一步讨论

• 我注意到threadscope中的第二个栏有时是绿色的(比如它的主页,其中第二个栏似乎总是垃圾收集).这是什么意思？
• 有没有办法回避垃圾收集？这似乎需要花费很多时间.例如,为什么不能分叉子计算,将结果返回到共享内存中,然后死掉？
• 是否有更好的方式(箭头,应用)表达并行性？

Answer 1

答案很简单:因为你没有引入并行性.Eval只是一个命令计算的monad,你必须要求手动并行执行的事情.你可能想要的是:

do xr <- rpar $ runEval $ mergeSort' x
   yr <- rseq $ runEval $ mergeSort' y
   rseq (merge xr yr)

这将使Haskell实际上为第一次计算创建一个火花,而不是试图在现场评估它.

标准提示也适用:

1. 应对结果进行深入评估(例如使用evalTraversable rseq).否则,您将只强制树的头部,并且大部分数据将仅返回未评估.
2. 只是引发一切都很可能会消耗任何收益.引入一个在较低递归级别停止引发的参数是个好主意.

编辑:在编辑问题后,以下实际上不再适用

但最糟糕的部分是最后一个:你所说的算法是非常有缺陷的.你的顶级seq只强制列表中的第一个cons-cell,这允许GHC使用懒惰来产生很好的效果.它实际上永远不会构造结果列表,只是在搜索最小元素(甚至不是严格需要的,但GHC仅在已知最小值之后生成单元格)中查看所有这些元素.

因此,当您开始引入并行性时假设您需要在程序中的某个点上的整个列表时,性能实际上急剧下降时不要感到惊讶......

编辑2:编辑的更多答案

您的程序最大的问题可能是它正在使用列表.如果你想制作一个不仅仅是玩具的例子,至少考虑使用(解包)数组.如果你想进行严肃的数字运算,可以考虑使用像repa这样的专业库.

关于"进一步讨论":

• 颜色代表不同的GC状态,我不记得哪个.尝试查看关联事件的事件日志.

• "回避"垃圾收集的方法是首先不要产生如此多的垃圾,例如通过使用更好的数据结构.

• 好吧,如果你正在寻找强大的并行化的灵感,那么看看monad-par可能是值得的,这是相对较新的,但(我觉得)并行行为不那么"令人惊讶".

使用monad-par,您的示例可能会变成:

  do xr <- spawn $ mergeSort' x
     yr <- spawn $ mergeSort' y
     merge <$> get xr <*> get yr

所以这里get实际上强制你指定连接点 - 并且库deepseq在幕后自动完成所需的操作.