Làm thế nào để viết mã song song với vectơ Haskell?

Question

Một mặt, trong Haskell Vector a có vẻ là loại ưa thích để sử dụng làm một dãy số. Thậm chí còn có một (không đầy đủ) Vector Tutorial.

Mặt khác, Control.Parallel.Strategies được xác định chủ yếu theo số Traversable. Thư viện Vector không cung cấp các trường hợp này.

Định nghĩa hoàn thành tối thiểu của Traversable t cũng nên xác định Foldable và

traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 
sequenceA :: Applicative f => t (f a) -> f (t a) 

Tôi không thấy như thế nào sequenceA thể được định nghĩa cho Data.Vector.Unboxed.Vector. Vì vậy, cách tiếp cận tốt nhất để viết mã song song với vectơ không hộp là gì? Xác định một số chiến lược quảng cáo mới như evalVector hoặc sử dụng par và pseq một cách rõ ràng hoặc sử dụng đồng bằng Data.Array thay vì vectơ?

P.S. Đồng bằng Array s là song song mà không có vấn đề: https://gist.github.com/701888

Answer 1

Đó là một công việc hack cho parVector nhưng điều này đã làm việc cho tôi:

import qualified Data.Vector as V 
import Control.Parallel.Strategies 
import Control.Parallel 
import Control.DeepSeq 

ack :: Int -> Int -> Int 
ack 0 n = n+1 
ack m 0 = ack (m-1) 1 
ack m n = ack (m-1) (ack m (n-1)) 

main = do 
    let vec = V.enumFromN 1 1000 
    let res = (V.map (ack 2) vec) `using` parVector 
    print res 

parVector :: NFData a => Strategy (V.Vector a) 
parVector vec = eval vec `seq` Done vec 
    where 
    chunkSize = 1 
    eval v 
    | vLen == 0 =() 
    | vLen <= chunkSize = rnf (v V.! 0) -- FIX this to handle chunks > 1 
    | otherwise = eval (V.take half v) `par` eval (V.drop half v) 
    where vLen = V.length v 
      half = vLen `div` 2 

Và chạy mã này:

[tommd@Mavlo Test]$ ghc --make -O2 -threaded t.hs 
... dumb warning ... 
[tommd@Mavlo Test]$ time ./t +RTS -N1 >/dev/null 
real 0m1.962s user 0m1.951s sys  0m0.009s 
[tommd@Mavlo Test]$ time ./t +RTS -N2 >/dev/null 
real 0m1.119s user 0m2.221s sys 0m0.005s 

Khi tôi chạy mã với Integer thay vì Int trong loại chữ ký:

[tommd@Mavlo Test]$ time ./t +RTS -N2 >/dev/null 

real 0m4.754s 
user 0m9.435s 
sys  0m0.028s 
[tommd@Mavlo Test]$ time ./t +RTS -N1 >/dev/null 

real 0m9.008s 
user 0m8.952s 
sys  0m0.029s 

Rock!

EDIT: Và một giải pháp mà là một chút gần gũi hơn với nỗ lực trước đó của bạn là sạch hơn (nó không sử dụng chức năng từ ba mô-đun riêng biệt) và các công trình lớn:

parVector :: NFData a => Strategy (V.Vector a) 
parVector vec = 
    let vLen = V.length vec 
     half = vLen `div` 2 
     minChunk = 10 
    in if vLen > minChunk 
     then do 
     let v1 = V.unsafeSlice 0 half vec 
      v2 = V.unsafeSlice half (vLen - half) vec 
     parVector v1 
     parVector v2 
     return vec 
     else 
     evalChunk (vLen-1) >> 
     return vec 
    where 
    evalChunk 0 = rpar (rdeepseq (vec V.! 0)) >> return vec 
    evalChunk i = rpar (rdeepseq (vec V.! i)) >> evalChunk (i-1) 

Những điều cần học hỏi từ giải pháp này:

1. Đơn vị sử dụng Eval đơn nguyên, vì vậy chúng tôi chắc chắn sẽ làm mọi thứ (so với việc gói đồ trong số let và ghi nhớ sử dụng mẫu chữ).Trái ngược với việc thực hiện đề xuất của bạn, (a) không xây dựng một vectơ mới, tốn kém (b) evalChunk đánh giá hiệu lực của từng phần tử sử dụng rpar và rdeepseq (Tôi không tin rằng bất kỳ phần tử nào của vectơ) .
2. Trái với niềm tin của tôi, slice có chỉ số bắt đầu và độ dài, không phải chỉ mục bắt đầu và kết thúc. Rất tiếc!
3. Chúng tôi vẫn cần nhập Control.DeepSeq (NFData), nhưng tôi đã gửi e-mail danh sách thư viện để thử và khắc phục sự cố đó.

Hiệu suất có vẻ tương tự như giải pháp parVector đầu tiên trong câu trả lời này, vì vậy tôi sẽ không đăng số.

Answer 2

1) Như bạn có thể biết, vector là sản phẩm của công việc DPH đã chứng minh khó hơn các nhà nghiên cứu ban đầu mong đợi.

2) vectơ không được phân chia không thể chia công việc cho các phần tử riêng lẻ trên nhiều CPU.

3) Tôi hy vọng nhiều hơn cho các vectơ đóng hộp. Một cái gì đó như:

using (map (rnf . (vec !)) [0..V.length vec - 1]) (parList rdeepseq) 

Hoặc có thể bạn tránh việc xây dựng danh sách và sử dụng danh sách. Tôi nghĩ rằng chỉ cần gán các phần của mảng là đủ. Mã dưới đây có thể bị hỏng, nhưng khái niệm tạo parVector của riêng bạn bằng cách sử dụng rnf và chia vectơ làm đôi cho đến khi nó là một phần tử đơn lẻ (hoặc một số phần tử có thể điều chỉnh được) sẽ hoạt động.

parVector :: Strategy (Vector a) 
parVector = let !_ = eval vec in Done vec 
    where 
    chunkSize = 1 
    eval v 
    | vLen == 0 =() 
    | vLen <= chunkSize = rnf (v ! 0) -- FIX this to handle chunks > 1 
    | otherwise = eval (V.take half v) `par` eval (V.drop half v) 
    where vLen = V.length v 
      half = vLen `div` 2