は、与えられた

Question

結果。 Parallel and Concurrent Programming in Haskellから、フィボナッチを平行して2つの方法で実行しました：

（1）リスト全体でparMapを使用してください。半分に（最初main） （2）カットリスト、前述のテキストを読むことから（第2 main）

rparで各作業を分割、私は速いと＃1を期待ただろう：

これは、コードを並列化するときの重要な原則を示しています。小さなチャンクを固定した数のチャンクに分割しないようにしてください。

私はコンパイルを介して（唯一の他をコメントアウト、1 mainを含む）の両方を実行しました：

• コンパイル - ghc -O2 Fib.hs -threaded -rtsopts -eventlog
• 実行 - ここ.\Fib.exe +RTS -N2 -s

がための結果であります（1）および（2）のそれぞれ：

（1） - （2）parMap

Tot time (elapsed) Avg pause Max pause 
    Gen 0   0 colls,  0 par 0.000s 0.000s  0.0000s 0.0000s 
    Gen 1   2 colls,  1 par 0.000s 0.000s  0.0001s 0.0001s 

    Parallel GC work balance: 84.39% (serial 0%, perfect 100%) 

    TASKS: 4 (1 bound, 3 peak workers (3 total), using -N2) 

    SPARKS: 80 (74 converted, 0 overflowed, 0 dud, 0 GC'd, 6 fizzled) 

    INIT time 0.000s ( 0.000s elapsed) 
    MUT  time 8.594s ( 4.331s elapsed) 
    GC  time 0.000s ( 0.000s elapsed) 
    EXIT time 0.000s ( 0.000s elapsed) 
    Total time 8.594s ( 4.332s elapsed) 

    Alloc rate 12,259 bytes per MUT second 

    Productivity 100.0% of total user, 198.4% of total elapsed 

を使用する - 私はテキストがでヒントし理解して分割リスト+各半分

         Tot time (elapsed) Avg pause Max pause 
    Gen 0   0 colls,  0 par 0.000s 0.000s  0.0000s 0.0000s 
    Gen 1   2 colls,  1 par 0.000s 0.000s  0.0002s 0.0003s 

    Parallel GC work balance: 12.41% (serial 0%, perfect 100%) 

    TASKS: 4 (1 bound, 3 peak workers (3 total), using -N2) 

    SPARKS: 40 (10 converted, 0 overflowed, 0 dud, 0 GC'd, 30 fizzled) 

    INIT time 0.000s ( 0.001s elapsed) 
    MUT  time 7.453s ( 3.751s elapsed) 
    GC  time 0.000s ( 0.000s elapsed) 
    EXIT time 0.000s ( 0.000s elapsed) 
    Total time 7.453s ( 3.752s elapsed) 

    Alloc rate 14,398 bytes per MUT second 

    Productivity 100.0% of total user, 198.6% of total elapsed 

にrparを使用する理由、ありませんでしたparMapのバージョンは分割したものよりも速い+ rparバージョンですか？

Answer 1

タイミングに影響するのは次のものだけではわかりませんが、確かに大きな役割を果たしています。リストで

、この

のような作業が並行して実行を開始することは非常に少ない手間がかかりますので、リスト内の各要素のために何かを実行を開始するための最速の方法があることを覚えておいてください分割することは非効率的ですちょうどそれらを相次いで実行し、rparでそれらを発火させる。それはparMapの機能です。

あなたのケースでは、splitAtははるかに多くの作業が必要です。リストの半分を走査し、次に別のリストにスペースを割り当てる必要があります。代わりに、このトラバーサル中にfib実行を開始したかもしれません。

[1..40]を(replicate 1000 35)に置き換えてみてください。これははるかに多くの並列化可能です：合理的に困難な問題の多くは、すべて同じ困難です。 1000要素の長さのリストでは、splitItが100秒以上で実行され、sparkは1秒未満で実行されます。あなたのソリューションは、何かを計算するのではなく、リストの分割と追加を大部分の時間を費やしてしまいます。

Answer 2

最初に、fib nを計算するのに必要な作業が指数関数的であることに注意してください。つまり、map fib [1..n]の計算には、fib (n+1)という計算とほぼ同じ時間がかかります。あなたは可能な限り、各スレッドで行われる作業の量を均等にしたい二つのスレッドで効率的にmap fib [1..40]を計算するには

import System.TimeIt 
import Control.Monad 
... 
main = forM_ [1..40] $ \n -> timeIt $ print (fib n) 

：これを確認するには、ちょうどそれがnの様々な値のためfib nを計算するのにかかる時間をプリントアウト。そのような分業の1つは、かなりうまく動作しますが、一方のスレッドがmap fib [1..38]を計算し、もう一方のスレッドが[fib 39, fib 40]を計算することが分かります。

fib iの計算ごとにスパークを作成すると、2つのスレッド間の分担が完全に非決定的になります。各スレッドによって行われる作業を均等化するには、実際にスパークが何であるかを注意深く工夫する必要があります。

2つのプログラムで作成されたスパークの数を調べます（1つは80、もう一方は40）。明らかに各fib iがスパークされており、どちらの場合もfib iの計算が2つのスレッドにランダムに割り当てられていることを意味します。ここで

は二つのスレッドで約1.5倍のスピードアップを得るための方法である： - map fib [1..38]用と他のあなたはRTSの概要を見れば

import Control.Parallel.Strategies 

fib :: Int -> Int 
fib x 
| x <= 1 = 1 
| otherwise = fib (x-1) + fib (x-2) 

main = do 
    let fs = (map fib [1..40]) `using` parListSplitAt 38 rdeepseq rdeepseq 
    print fs 

あなたはそれが2つのしか火花を作成していることがわかりますmap fib [39,40]の場合80の火花について

...あなたはparMap rseq代わりのparMap rparを使用する場合火花の数がparMap rparがちょうど完全に冗長である別の火花を作成する火花を作成しているので、明らかに40に低下を作成しました。一般的に私は評価方法としてrdeepseqに固執します。それは単純で簡単で、推論しやすく、エラーを起こしにくいです。