Làm thế nào để khai thác bất kỳ song song nào trong mã song song haskell của tôi?

Question

Tôi vừa mới tuyên bố làm việc trong song song bán rõ ràng haskell với GHC 6.12. Tôi đã viết mã haskell sau đây để tính toán song song với bản đồ của hàm fibonnaci khi 4 phần tử trên một danh sách, và trong cùng một thời gian bản đồ của hàm sumEuler trên hai phần tử.

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) 

để cải thiện chương trình của tôi song song tôi viết lại nó với mệnh và pseq và buộc chức năng để buộc đánh giá whnf. Vấn đề của tôi là bằng cách tìm trong threadscope nó xuất hiện mà tôi đã không đạt được bất kỳ song song. Mọi thứ trở nên tồi tệ hơn vì tôi không tăng tốc.

Đó lý do tại sao tôi có đề tài hai câu hỏi

Câu hỏi 1 Làm thế nào tôi có thể sửa đổi mã của tôi để khai thác bất kỳ xử lý song song?

Câu hỏi 2 Làm cách nào để viết chương trình của mình để sử dụng Chiến lược (parMap, parList, rdeepseq, v.v ...)?

cải thiện đầu tiên với chiến lược

theo đóng góp của ông

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

song song xuất hiện trong threadscope nhưng không đủ để có sự tăng tốc đáng kể

Answer 1

xử lý song song của bạn là quá trình hạt viên để có nhiều tác dụng có lợi. Khối lượng công việc lớn nhất có thể được thực hiện song song hiệu quả là ở sumEuler, vì vậy đó là nơi bạn nên thêm chú thích par của mình. Hãy thử thay đổi sumEuler tới:

sumEuler :: Int -> Int 
sumEuler = sum . (parMap rseq euler) . mkList 

parMap là từ Control.Parallel.Strategies; nó thể hiện một bản đồ có thể được thực hiện song song. Đối số đầu tiên, rseq có loại Strategy a, được sử dụng để buộc tính toán đến một điểm cụ thể, nếu không sẽ không có công việc nào được thực hiện, do sự lười biếng. rseq là tốt cho hầu hết các loại số.

Không hữu ích khi thêm song song vào fib ở đây, bên dưới khoảng fib 40 không có đủ công sức để làm cho nó đáng giá.

Ngoài chuỗi chủ đề, việc chạy chương trình của bạn với cờ -s rất hữu ích. Tìm một dòng như:

SPARKS: 15202 (15195 converted, 0 pruned) 

ở đầu ra. Mỗi tia lửa là một mục trong một hàng đợi công việc để có thể được thực hiện song song. Các tia lửa được chuyển đổi thực sự được thực hiện song song, trong khi các tia lửa cắt tỉa có nghĩa là sợi chính đã đến trước khi một sợi công nhân có cơ hội làm như vậy. Nếu số cắt tỉa cao, có nghĩa là các biểu thức song song của bạn quá chi tiết. Nếu tổng số tia lửa là thấp, bạn không cố gắng làm đủ song song.

Cuối cùng, tôi nghĩ parMapFibEuler được viết tốt hơn như:

parMapFibEuler :: Int 
parMapFibEuler = sum (mapFib `using` parList rseq) + sum mapEuler 

mapEuler chỉ đơn giản là quá ngắn để có bất kỳ xử lý song song một cách hữu ích bày tỏ ở đây, đặc biệt là khi euler đã được thực hiện song song. Tôi nghi ngờ rằng nó tạo ra sự khác biệt đáng kể cho mapFib. Nếu danh sách mapFib và mapEuler dài hơn, tính song song ở đây sẽ hữu ích hơn. Thay vì parList, bạn có thể sử dụng parBuffer, có xu hướng hoạt động tốt cho người tiêu dùng trong danh sách.

Thực hiện hai thay đổi này làm giảm thời gian chạy từ 12 giây xuống 8 giây đối với tôi, với GHC 7.0.2.

Answer 2

Hmmm. .. Có lẽ?

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

I.e. đẻ trứng mapFib trong nền và tính toán mapEuler và chỉ sau khi nó (mapEuler) làm (+) khoản tiền của chúng. Thật sự tôi đoán bạn có thể làm điều gì đó như:

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

Về Q2: Như tôi đã biết chiến lược - là "chiến lược" để kết hợp dữ liệu cấu trúc với những par và seq.
Bạn có thể viết của bạn forceList = withStrategy (seqList rseq)
Như bạn cũng có thể viết mã của bạn như:

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

Tức là chiến lược được áp dụng cho tuple của hai danh sách sẽ buộc họ bị loại bỏ song song, nhưng mỗi danh sách sẽ bị buộc phải được đánh giá tuần tự.

Answer 3

Trước hết, tôi giả sử bạn biết định nghĩa fib của bạn là khủng khiếp và bạn chỉ đang thực hiện việc này để chơi với gói song song.

Có vẻ như bạn đang học song song ở cấp độ sai. Song song mapFib và mapEuler sẽ không tăng tốc tốt vì có nhiều công việc để tính toán mapFib.Những gì bạn cần làm là tính toán mỗi người trong số những yếu tố này rất tốn kém song song, đó là hạt hơi tốt hơn nhưng không quá vậy:

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 

Ngoài ra, tôi ban đầu đã chiến đấu bằng Control.Parallel.Strategies qua Control.Parallel nhưng đã đến để thích nó vì nó dễ đọc hơn và tránh các vấn đề như của bạn, nơi người ta sẽ mong đợi sự song song và phải nheo mắt vào nó để tìm ra lý do tại sao bạn không nhận được bất kỳ thứ gì.

Cuối cùng, bạn nên luôn đăng cách bạn biên dịch và cách bạn chạy mã mà bạn mong muốn được song song. Ví dụ:

$ 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 

Sản lượng:

Answer 4

Lý do bạn không thấy bất kỳ sự song song nào ở đây là vì tia lửa của bạn đã bị thu gom rác.Chạy chương trình với +RTS -s và lưu ý dòng này:

SPARKS: 1 (0 converted, 1 pruned) 

tia lửa đã được "cắt tỉa", có nghĩa là loại bỏ bằng cách thu gom rác thải. Trong GHC 7, chúng tôi đã thay đổi ngữ nghĩa của tia lửa, như vậy tia lửa hiện nay là rác thu thập được (GC'd) nếu nó không được giới thiệu bởi phần còn lại của chương trình; chi tiết có trong số the "Seq no more" paper.

Tại sao tia lửa điện tử GC trong trường hợp của bạn? Nhìn vào mã:

parMapFibEuler :: Int 
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler)) 

tia lửa ở đây là biểu thức forkList mapFib. Lưu ý rằng giá trị của biểu thức này không được yêu cầu bởi phần còn lại của chương trình; nó chỉ xuất hiện như một đối số cho par. GHC biết rằng nó không phải là cần thiết, vì vậy nó được thu gom rác thải.

Toàn bộ điểm thay đổi gần đây đối với gói parallel là để bạn dễ dàng tránh bẫy gấu này. Quy tắc tốt của ngón tay cái là sử dụng trực tiếp Control.Parallel.Strategies thay vì trực tiếp par và pseq. cách ưa thích của tôi để viết đây sẽ là

parMapFibEuler :: Int 
parMapFibEuler = runEval $ do 
    a <- rpar $ sum mapFib 
    b <- rseq $ sum mapEuler 
    return (a+b) 

nhưng thật đáng buồn này không làm việc với GHC 7.0.2, bởi vì tia lửa sum mapFib đang nổi lên như một biểu hiện tĩnh (một CAF), và thời gian chạy không nghĩ rằng tia lửa trỏ đến biểu thức tĩnh là đáng để giữ (tôi sẽ sửa lỗi này). Điều này sẽ không xảy ra trong một chương trình thực sự, tất nhiên! Vì vậy, hãy làm cho chương trình trở nên thực tế hơn một chút và đánh bại tối ưu hóa 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)) 

Bây giờ tôi có được sự tương đương tốt với GHC 7.0.2. Tuy nhiên, lưu ý rằng các bình luận của @ John cũng được áp dụng: thông thường bạn muốn tìm kiếm tính song song chi tiết hơn để cho phép GHC sử dụng tất cả các bộ vi xử lý của bạn.