Suy thoái khi sử dụng các chiến lược song song trong Haskell

Question

Tôi đã làm việc thông qua các bài tập lập trình song song xác định của Andre Loh trong các bài tập haskell. Tôi đã cố gắng để chuyển đổi mã tuần tự N-Queens thành song song bằng cách sử dụng chiến lược, nhưng tôi nhận thấy rằng mã song song chạy chậm hơn nhiều so với mã tuần tự và cũng có lỗi với không đủ ngăn xếp.

Đây là mã cho song song 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) 

Dòng (\l -> concat (map (addQueen n) l using parListChunk (n div numCapabilities) rdeepseq)) là những gì tôi đã thay đổi từ mã gốc. Tôi đã nhìn thấy giải pháp của Simon Marlow nhưng tôi muốn biết lý do cho sự chậm lại và lỗi trong mã của tôi.

Xin cảm ơn trước.

Answer 1

Bạn đang tạo ra quá nhiều việc. Tham số parListChunk của div n numCapabilities có thể là, cái gì, 7 trên hệ thống của bạn (2 lõi và bạn đang chạy với n ~ 14). Danh sách sẽ phát triển lớn rất nhanh chóng, vì vậy không có điểm nào trong việc tạo ra các đơn vị nhỏ như vậy (và tôi không hiểu tại sao nó có ý nghĩa buộc nó với giá trị là n).

Nếu tôi thêm yếu tố mười (tạo đơn vị phát tia lửa 70 trong trường hợp này) thì tôi nhận được một hiệu suất rõ ràng giành chiến thắng trên luồng đơn. Ngoài ra, tôi không có vấn đề ngăn xếp bạn tham khảo - nếu nó biến mất với một sự thay đổi giá trị parListChunk của bạn sau đó tôi muốn báo cáo rằng như là một lỗi.

Nếu tôi thực hiện chunking mỗi 800 thì thời gian ở trên hết tại 5.375s so với 7.9. Hơn 800 và hiệu suất bắt đầu trở nên tệ hơn nữa, 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