如何利用Haskell并行代码中的任何并行性？

Question

我刚开始使用GHC 6.12进行Haskell半显式并行编程。我编写了以下Haskell代码，对列表中的4个元素计算斐波那契函数的映射，并同时对两个元素计算sumEuler函数的映射。

import Control.Parallel
import Control.Parallel.Strategies

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

mkList :: Int -> [Int]
mkList n = [1..n-1]

relprime :: Int -> Int -> Bool
relprime x y = gcd x y == 1

euler :: Int -> Int
euler n = length (filter (relprime n) (mkList n))

sumEuler :: Int -> Int
sumEuler = sum . (map euler) . mkList

-- parallel initiation of list walk                                                                                                                                    
mapFib :: [Int]
mapFib = map fib [37, 38, 39, 40]

mapEuler :: [Int]
mapEuler = map sumEuler [7600, 7600]

parMapFibEuler :: Int
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler))

-- how to evaluate in whnf form by forcing                                                                                                                                
forceList :: [a] -> ()
forceList [] = ()
forceList (x:xs) = x `pseq` (forceList xs)


main = do putStrLn (" sum : " ++ show parMapFibEuler)

为了提高我的程序的并行性能，我使用了par和pseq以及一个forcing函数来强制进行whnf评估的重写。但问题是，在查看Threadscope时，我发现没有获得任何并行性，并且速度也没有提升。

这就是为什么我有以下两个问题：

问题1：如何修改我的代码以利用任何并行性？

问题2：如何编写我的程序以使用策略（如parMap、parList、rdeepseq等）？

通过策略的第一个改进

根据他的贡献

parMapFibEuler = (mapFib, mapEuler) `using` s `seq` (sum mapFib + sum mapEuler) where
    s = parTuple2 (seqList rseq) (seqList rseq)

并行性在ThreadScope中出现，但不足以显著提高速度。

- Fopa Léon Constantin

---

在 GHC 7 中，parallel 包得到了极大的改进，因此您可能也考虑升级。 - Don Stewart

你可以对斐波那契函数进行备忘录优化，以提高其速度... - Hai

Answer 1

你没有看到任何并行处理的原因是因为你的Spark已经被垃圾回收了。使用+RTS -s运行程序，并注意这一行：

  SPARKS: 1 (0 converted, 1 pruned)

火花已被“修剪”，这意味着被垃圾回收器移除。在 GHC 7 中，我们对火花的语义进行了更改，现在如果火花没有被程序中的其他部分引用，则会被垃圾回收（GC）；详细信息请参见“Seq no more”论文。

为什么在您的情况下火花会被 GC？看看代码：

parMapFibEuler :: Int
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler))

这里的亮点是表达式 forkList mapFib。请注意，该表达式的值不被程序的其余部分所需；它只出现为 par 的参数。 GHC 知道它不被需要，因此进行垃圾回收。

最近对 parallel 包的更改的整个重点是让您轻松避免这种陷阱。一个好的经验法则是使用 Control.Parallel.Strategies 而不是直接使用 par 和 pseq。我写这个的首选方式是：

parMapFibEuler :: Int
parMapFibEuler = runEval $ do
  a <- rpar $ sum mapFib
  b <- rseq $ sum mapEuler
  return (a+b)

但遗憾的是，这在 GHC 7.0.2 上不起作用，因为 spark sum mapFib 被提取为一个静态表达式（CAF），并且运行时不认为指向静态表达式的 sparks 值得保留（我会修复这个问题）。当然，在真实的程序中是不会发生这种情况的！所以让我们让程序变得更加现实，并打败 CAF 优化:

parMapFibEuler :: Int -> Int
parMapFibEuler n = runEval $ do
  a <- rpar $ sum (take n mapFib)
  b <- rseq $ sum (take n mapEuler)
  return (a+b)

main = do [n] <- fmap (fmap read) getArgs
          putStrLn (" sum : " ++ show (parMapFibEuler n))

现在我使用GHC 7.0.2获得了很好的并行性。然而，请注意@John的评论也适用：通常您希望寻找更细粒度的并行性，以便让GHC使用您所有的处理器。

- Simon Marlow

---

非常感谢您，这解释了我在研究这个问题时一直想知道的一些行为。 - John L

Answer 2

你的并行粒度太粗，无法产生很大的好处。能够高效地并行处理的最大工作块在sumEuler函数中，因此你应该在这里添加par注释。尝试将sumEuler改为：

sumEuler :: Int -> Int
sumEuler = sum . (parMap rseq euler) . mkList

parMap来自Control.Parallel.Strategies；它表示可以并行执行的映射。第一个参数rseq，类型为Strategy a，用于将计算强制到特定点，否则由于惰性不会执行任何工作。对于大多数数字类型，rseq都是可以接受的。

在这里给fib添加并行性并没有什么用处，在fib 40以下的范围内，没有足够的工作量使其值得。

除了使用threadscope外，使用-s标志运行程序也很有用。查找类似于以下行：

SPARKS: 15202 (15195 converted, 0 pruned)

在输出中，每个“spark”都是一个工作队列条目，可能会并行执行。已转换的火花实际上是并行完成的，而修剪的火花意味着主线程在工作线程有机会之前就完成了它们。如果修剪数量很高，则意味着您的并行表达式过于细粒度。如果火花总数较低，则表示您没有尝试足够的并行操作。

最后，我认为parMapFibEuler最好这样写：

parMapFibEuler :: Int
parMapFibEuler = sum (mapFib `using` parList rseq) + sum mapEuler

mapEuler太短了，无法有效地表达任何并行性，尤其是由于euler已经被并行执行。我对于mapFib也不确定它是否会有实质性的改变。如果列表mapFib和mapEuler更长，则此处的并行性将更加有用。您可以使用parBuffer代替parList，后者通常适用于列表消费者。

进行这两个更改可使运行时间从12秒缩短至8秒（对于GHC 7.0.2版本）。

- John L

Answer 3

嗯... 或许呢？

((forceList mapFib) `par` (forceList mapEuler)) `pseq` (sum mapFib + sum mapEuler)

也就是说，在后台生成mapFib并计算mapEuler，只有在mapEuler完成之后，才进行它们的和的(+)运算。 实际上，我想你可以这样做：

parMapFibEuler = a `par` b `pseq` (a+b) where
     a = sum mapFib
     b = sum mapEuler

关于 Q2： 据我所知，策略是将数据结构与 par 和 seq 结合起来的“策略”。
您可以编写 forceList = withStrategy (seqList rseq)
同样，您也可以像这样编写代码：

parMapFibEuler = (mapFib, mapEuler) `using` s `seq` (sum mapFib + sum mapEuler) where
    s = parTuple2 (seqList rseq) (seqList rseq)

即应用于两个列表的策略将强制并行评估它们，但每个列表将被强制顺序评估。

- ony

---

谢谢您的回复，但是您提出的代码与我在问题中编写的代码相似。我已经测试了您的建议，ThreadScope绘图结果与之前相同。 - Fopa Léon Constantin

只需要进行一点修改就可以让它正常工作。parMapFibEuler = ((mapFib，mapEuler) using s) seq (sum mapFib + sum mapEuler)，其中s = parTuple2 (seqList rseq) (seqList rseq)。 - Fopa Léon Constantin

Answer 4

首先，我假设您知道您的fib定义很糟糕，而您只是为了使用并行包而这样做。

您似乎在错误的级别上进行并行处理。 并行处理mapFib和mapEuler不会给出良好的加速，因为计算mapFib需要更多的工作量。 您应该并行计算每个非常昂贵的元素，这略微细粒度但不过度：

mapFib :: [Int]
mapFib = parMap rdeepseq fib [37, 38, 39, 40]

mapEuler :: [Int]
mapEuler = parMap  rdeepseq sumEuler [7600, 7600, 7600,7600]

parMapFibEuler :: Int
parMapFibEuler = sum a + sum b
  where
  a = mapFib
  b = mapEuler

另外，我最初反对使用Control.Parallel而选择了Control.Parallel.Strategies，但现在我喜欢它，因为它更易读，并避免了像你这样的问题，其中一个人会期望并行性，但必须眯起眼睛才能弄清楚为什么没有得到任何结果。

最后，您应该始终发布您编译和运行期望并行化的代码的方式。例如：

$ ghc --make -rtsopts -O2 -threaded so.hs -eventlog -fforce-recomp
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
$ ./so +RTS -ls -N2
 sum : 299045675

产生的结果：

- Thomas M. DuBuisson