如何利用我的 haskell 并行代码中的并行性？

Question

我刚刚说过使用 Haskell 半显式并行性与 GHC 6.12 进行工作。我编写了以下 haskell 代码来并行计算列表上 4 个元素上的 fibonnaci 函数的映射，同时计算两个元素上的函数 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 评估。我的问题是，通过查看线程范围，我似乎没有获得任何并行性。事情变得更糟，因为我没有获得任何加速。

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

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

问题 2 我如何编写程序才能使用策略（parMap、parList、rdeepseq 等...）？

策略的首次改进

根据他的贡献

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

，并行性出现在线程范围中，但不足以显着加速

Answer 1

您在这里看不到任何并行性的原因是因为您的火花已被垃圾收集。使用 +RTS -s 运行程序并注意这一行：

  SPARKS: 1 (0 converted, 1 pruned)

火花已被“修剪”，这意味着被垃圾收集器删除。在 GHC 7 中，我们对 Spark 的语义进行了更改，如果程序的其余部分没有引用 Spark，那么它现在会被垃圾收集 (GC)；详细信息请参阅“不再使用 Seq”论文。

为什么你的情况下 Spark 会被 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）浮动，并且运行时不会不要认为指向静态表达式的火花值得保留（我会解决这个问题）。当然，这在真实的程序中不会发生！因此，让我们让程序更加现实一点，并击败 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 使用您的所有处理器。

Answer 2

你的并行性太粗略了，无法产生太多有益的效果。可以高效并行完成的最大工作块在 sumEuler 中，因此您应该在其中添加 par 注释。尝试将 sumEuler 更改为：

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

parMap 来自 Control.Parallel.Strategies；它表达了一个可以并行完成的映射。第一个参数，具有Strategy a类型的rseq，用于强制计算到特定点，否则由于惰性而不会完成任何工作。 rseq 适用于大多数数字类型。

在这里向 fib 添加并行性没有什么用处，下面关于 fib 40 没有足够的工作使其值得。

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

SPARKS: 15202 (15195 converted, 0 pruned)

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

最后，我认为 parMapFibEuler 最好写成：

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

mapEuler 太短了，无法在这里有效地表达任何并行性，特别是当 euler 已经执行时并联。我怀疑它是否会对 mapFib 产生实质性影响。如果列表 mapFib 和 mapEuler 更长，这里的并行性会更有用。您可以使用 parBuffer 来代替 parList，它对于列表使用者来说效果很好。

使用 GHC 7.0.2，进行这两项更改将运行时间从 12 秒缩短到 8 秒。

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

关于第二个问题：
据我所知，策略 - 是将数据结构与 par 和 seq 结合起来的“策略”。
您可以编写 forceList = withStrategy (seqList rseq)
您也可以编写如下代码：

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

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

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.Strategies 而不是 Control.Parallel，但后来开始喜欢它，因为它更可读并避免像你这样的问题，人们会期望并行性，并且必须眯着眼睛才能弄清楚为什么你没有得到任何并行性。

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

$ 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

产量：