Haskell中的多核编程 - Control.Parallel

Question

我想学习如何使用Control.Parallel模块，但我认为我的理解不正确。

我尝试运行以下代码（fibs.hs）。

import Control.Parallel

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = p `par` (q `pseq`  (p + q))
    where
      p = fib (n-1)
      q = fib (n-2)


main = print $ fib 30

我使用以下内容进行编译：

ghc -O2 --make -threaded fibs.hs

接着我执行了这个程序并得到以下结果（一个运行Python脚本100次并返回平均执行时间和标准差的输出）：

./fibs +RTS -N1 -> avg= 0.060203 s, deviation = 0.004112 s  
./fibs +RTS -N2 -> avg= 0.052335 s, deviation = 0.006713 s  
./fibs +RTS -N3 -> avg= 0.052935 s, deviation = 0.006183 s  
./fibs +RTS -N4 -> avg= 0.053976 s, deviation = 0.007106 s  
./fibs +RTS -N5 -> avg= 0.055227 s, deviation = 0.008598 s  
./fibs +RTS -N6 -> avg= 0.055703 s, deviation = 0.006537 s  
./fibs +RTS -N7 -> avg= 0.058327 s, deviation = 0.007526 s  

我的问题如下：

1. 当我执行以下操作时，究竟会发生什么：

   a `par` (b `pseq` (a + b))   ?
   

   我知道par a b表示提示编译器在计算a和b的时候并行处理a，最后返回b。好，但是pseq是干什么的呢？

2. 为什么性能提升这么小？我在一台Intel Core 2 Quad机器上运行这个程序。我希望使用-N5或-N6不会对性能产生实质性影响，或者程序会表现得非常糟糕。但是为什么从-N2到-N3没有任何改善，而最初的改善如此之小？

- Rafael S. Calsaverini

Answer 1

正如Don 所解释的，问题在于您创建了过多的Sparks。以下是您可能需要重写的示例，以获得良好的加速效果。

import Control.Parallel

cutoff :: Int
cutoff = 20

parFib :: Int -> Int
parFib n | n < cutoff = fib n
parFib n = p `par` q `pseq` (p + q)
    where
      p = parFib $ n - 1
      q = parFib $ n - 2

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

main :: IO ()
main = print $ parFib 40

演示：

[computer ~]$ ghc --make -threaded -O2 Main.hs
[1 of 1] Compiling Main             ( Main.hs, Main.o )
Linking Main ...
[computer ~]$ time ./Main +RTS -N1
102334155

real    0m1.509s
user    0m1.450s
sys     0m0.003s
[computer ~]$ time ./Main +RTS -N2
102334155

real    0m0.776s
user    0m1.487s
sys     0m0.023s
[computer ~]$ time ./Main +RTS -N3
102334155

real    0m0.564s
user    0m1.487s
sys     0m0.030s
[computer ~]$ time ./Main +RTS -N4
102334155

real    0m0.510s
user    0m1.587s
sys     0m0.047s
[computer ~]$ 

- Michael Steele

Answer 2

在这里，您正在创建指数级别的火花（想象一下您创建了多少递归调用）。要实现良好的并行性，您需要在这种情况下创建更少的并行工作，因为您的硬件无法处理那么多线程（因此GHC不会创建它们）。

解决方案是使用截断策略，如此演讲中所述：http://donsbot.wordpress.com/2009/09/05/defun-2009-multicore-programming-in-haskell-now/

基本上，一旦达到一定深度，切换到直线版本，并使用+RTS-sstderr查看正在被转换的火花数量，以便确定是否浪费工作。

- Don Stewart

---

Haskell会自动平衡Sparks以获得最佳性能吗？ - Chuck

它可以自动平衡线程。运行时拥有未评估的表达式队列（火花），当工作量减少时将其转换为线程。但是，请注意不要创建太多的火花（从而浪费时间填充火花队列）。 - Don Stewart

Answer 3

由于没有人给出关于pseq的明确答案，这里是官方描述：

在语义上与seq相同，但存在微妙的操作差异：seq对其两个参数都是严格的，因此编译器可能会将seqb重新排列为b seqa seqb。当使用seq表示严格性时，通常不会有问题，但在为并行性注释代码时可能会有问题，因为我们需要更多地控制评估顺序；我们可能希望在b之前评估a，因为我们知道b已经被并行地激活。

这就是为什么我们有pseq。与seq相比，pseq只对其第一个参数（就编译器而言）是严格的，这限制了编译器可以进行的变换，并确保用户可以保留对评估顺序的控制。

- LarsH

Answer 4

回复（1）：par 允许在另一个线程中计算 a。我猜测，pseq 的行为很像 seq：它强制先计算第一个结果（好吧，在 GHC 上，seq 不能保证这样做，但实际上它确实这样做）。因此，在这种情况下，计算 a 被分叉为一个线程，另一个线程计算 b，然后求和 a 和 b。

回复（2）：这是一个被分叉到其他线程的相当微不足道的计算；对于 CPU 来说，直接计算可能会更快。我打赌线程的开销对于这个简单的计算而言帮助不大，反而有些损失。

- Conrad Meyer