haskell - 如何利用我的 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

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

  SPARKS: 1 (0 converted, 1 pruned)

Spark 已被“修剪”，这意味着被垃圾收集器删除。在 GHC 7 中，我们对 Spark 的语义进行了更改，如果程序的其余部分没有引用 Spark，那么它现在会被垃圾收集 (GC)；详情见the "Seq no more" paper .

为什么在你的情况下 Spark 会被 GC 处理？看代码:

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

这里的 Spark 是表达式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) float 的，并且运行时不会认为触发该点静态表达式值得保留(我会解决这个问题)。当然，这在真实的程序中不会发生!因此，让我们让程序变得更现实一点，并击败 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 使用您的所有处理器。