Haskell에서 병렬 전략을 사용할 때 속도 저하

Question

나는 haskell 연습에서 Andre Loh의 결정 론적 병렬 프로그래밍의 연습을하고있었습니다. 전략을 사용하여 N-Queens 순차 코드를 병렬로 변환하려고했지만 병렬 코드가 순차 코드보다 훨씬 느리게 실행되고 스택 공간이 부족하여 오류가 발생하는 것으로 나타났습니다.

이

는

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) 

라인 (\l -> concat (map (addQueen n) l using parListChunk (n div numCapabilities) rdeepseq))는 I 원본 코드로 변경 무엇 병렬 N-퀸즈 코드이다. Simon Marlow의 솔루션을 보았지만 코드가 느려지고 오류가 발생하는 이유를 알고 싶었습니다.

미리 감사드립니다.

Answer 1

당신은 너무 많은 일을하고 있습니다. parListChunk 매개 변수는 div n numCapabilities 일 것입니다. 시스템에서는 7 개 (코어 2 개, n ~ 14 개)입니다. 이 목록은 매우 빠르게 커지므로 이러한 작은 작업 단위를 촉발 할 필요가 없습니다. (이유는 그것을 n의 값으로 묶는 것이 타당하지 않습니다.)

10의 인수를 추가하면 (이 경우 스파크 장치 70을 작성) 단일 스레딩보다 성능이 훨씬 좋아집니다. 또한, 당신이 참조하는 스택 문제가 없습니다 - 당신의 parListChunk 값으로 변경되면 버리는 경우 버그로보고 싶습니다.

내가 800 번 청크를 만들면 5.375s 대 7.9s의 시간대가 끝납니다. 800 이상이되면 성능이 다시 악화되기 시작합니다.

편집 :

[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