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

並行出現在threadscope但不足以有顯著加速

Answer 1

你的並行過於粗粒度有多少有益的作用。可以有效並行完成的最大塊工作是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) 

在輸出中。每個火花都是工作隊列中的條目，可能會並行執行。轉換後的火花實際上是並行進行的，而修剪的火花意味着主線程在工作線程有機會之前到達它們。如果修剪的數字很高，這意味着你的並行表達式太細。如果火花總數很少，那麼你並沒有試圖做足夠多的並行處理。

最後，我認爲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 2

嗯與策略

第一個改進。 .. 也許？

((forceList mapFib) `par` (forceList mapEuler)) `pseq` (sum mapFib + sum mapEuler) 

I.e.在後臺產生mapFib並計算mapEuler並且僅在它們之後（mapEuler）做(+)它們的總和。 其實我想你可以這樣做：

parMapFibEuler = a `par` b `pseq` (a+b) where 
    a = sum mapFib 
    b = sum mapEuler 

關於Q2： 據我所知策略 - 是「戰略」數據結構與par和seq結合起來。
你可以寫你forceList = withStrategy (seqList rseq)
同樣，你可以寫你的代碼，如：

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

即應用於兩個列表元組的策略將並行強制執行，但每個列表都將被強制依次評估。

Answer 3

首先，我假設你知道你的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 

產量：

Answer 4

你在這裏沒有看到任何平行的原因是因爲你的火花已被垃圾收集。與+RTS -s運行該程序，並注意這一行：

SPARKS: 1 (0 converted, 1 pruned) 

火花已經「修剪」，其通過垃圾收集器移除裝置。在GHC 7中，我們改變了火花的語義，如果火花現在沒有被程序的其餘部分所引用，現在垃圾收集（GC'd）;詳情請見the "Seq no more" paper。

爲什麼在你的情況下，火花GC'd？看代碼：

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使用您的所有處理器。