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

Question

我刚刚说过使用GHC 6.12开发haskell半显式并行性.我编写了以下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)

以提高我的程序并行我重写了它看齐和PSEQ和强制功能强制whnf评价.我的问题是,通过查看threadscope,我似乎没有获得任何并行性.情况更糟,因为我没有获得任何加速.

这就是我有两个问题的原因

问题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中,我们改变了火花的语义,这样如果程序的其余部分没有引用火花就会被垃圾收集(GC'd); 细节在"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,因为火花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; 它表示可以并行完成的地图.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明显延长,在此并行会更加有用.而不是parList你可以使用parBuffer,这往往适合列表消费者.

使用GHC 7.0.2,进行这两项更改可以将运行时间从12秒减少到8秒.