Haskellで並列ストラテジーを使用した場合のスローダウン

Question

私は、haskell演習でAndre Lohの決定論的並列プログラミングの演習を行っていました。戦略を使用してN-Queensのシーケンシャルコードをパラレルに変換しようとしていましたが、パラレルコードがシーケンシャルコードよりも遅く実行され、スタックスペースが不足しているというエラーが発生しました。

これはライン(\l -> concat (map (addQueen n) l using parListChunk (n div numCapabilities) rdeepseq))私は元のコードから変更何

import Control.Monad 
import System.Environment 
import GHC.Conc 
import Control.Parallel.Strategies 
import Data.List 
import Data.Function 

type PartialSolution = [Int] -- per column, list the row the queen is in 
type Solution = PartialSolution 

type BoardSize = Int 

chunk :: Int -> [a] -> [[a]] 
chunk n [] = [] 
chunk n xs = case splitAt n xs of 
     (ys, zs) -> ys : chunk n zs 

-- Generate all solutions for a given board size. 
queens :: BoardSize -> [Solution] 
--queens n = iterate (concatMap (addQueen n)) [[]] !! n 
queens n = iterate (\l -> concat (map (addQueen n) l `using` parListChunk (n `div`   numCapabilities) rdeepseq)) [[]] !! n 


-- Given the size of the problem and a partial solution for the 
-- first few columns, find all possible assignments for the next 
-- column and extend the partial solution. 
addQueen :: BoardSize -> PartialSolution -> [PartialSolution] 
addQueen n s = [ x : s | x <- [1..n], safe x s 1 ] 

-- Given a row number, a partial solution and an offset, check 
-- that a queen placed at that row threatens no queen in the 
-- partial solution. 
safe :: Int -> PartialSolution -> Int -> Bool 
safe x [] n = True 
safe x (c:y) n = x /= c && x /= c + n && x /= c - n && safe x y (n + 1) 

main = do 
     [n] <- getArgs 
     print $ length $ queens (read n) 

、並列N - クイーンのためのコードです。私はSimon Marlowのソリューションを見てきましたが、私のコードでは減速とエラーの理由を知りたかったのです。

ありがとうございます。

Answer 1

あなたはあまりにも多くの仕事を誘発しています。 parListChunkのパラメータがdiv n numCapabilitiesの場合、おそらく、システム上では7個（2つのコアとn〜14で実行しています）です。リストは非常に急速に大きくなるので、そのような小さな作業単位を引き起こすことには意味がありません（なぜそれがnの値に結びつくのがわかりません）。

10の要素を追加すると（この場合、スパークリングユニット70を作成すると）、シングルスレッディングよりもはっきりとパフォーマンスが向上します。また、あなたが参照しているスタックの問題はありません。もしあなたのparListChunkの値が変更されたら、バグとして報告したいと思います。

チャンクを800にすると、タイムは5.375sから7.9sに上がります。 800を超えるとパフォーマンスが悪化し始める、ymmv。

EDIT：

[tommd@mavlo Test]$ ghc --version 
The Glorious Glasgow Haskell Compilation System, version 7.0.4 
[tommd@mavlo Test]$ ghc -O2 so.hs -rtsopts -threaded -fforce-recomp ; time ./so 13 +RTS -N2 
[1 of 1] Compiling Main    (so.hs, so.o) 
Linking so ... 
73712 
real 0m5.404s 

[tommd@mavlo Test]$ ghc -O2 so.hs -rtsopts -fforce-recomp ; time ./so 13 
[1 of 1] Compiling Main    (so.hs, so.o) 
Linking so ... 
73712 
real 0m8.134s