Làm cách nào để viết giảm song song bằng các chiến lược trong Haskell?

Question

Trong tính toán hiệu suất cao, tổng, sản phẩm, v.v. thường được tính bằng cách sử dụng "giảm song song" mất n yếu tố và hoàn thành trong thời gian O (log n) (được cung cấp đủ song song). Trong Haskell, chúng tôi thường sử dụng một số gấp cho loại tính toán này, nhưng thời gian đánh giá luôn tuyến tính trong độ dài của danh sách.

Dữ liệu Parallel Haskell có một số tính năng này được tích hợp sẵn, nhưng còn trong khung công tác chung của danh sách thì sao? Chúng ta có thể làm điều đó với Control.Parallel.Strategies?

Vì vậy, giả sử f là kết hợp, làm thế nào để chúng ta viết

parFold :: (a -> a -> a) -> [a] -> a

để parFold f xs chỉ cần thời gian logarit trong length xs?

Answer 1

Tôi không nghĩ danh sách là loại dữ liệu phù hợp cho việc này. Bởi vì nó chỉ là một danh sách liên kết, dữ liệu nhất thiết sẽ được truy cập tuần tự. Mặc dù bạn có thể đánh giá các mục song song, bạn sẽ không đạt được nhiều trong bước giảm. Nếu bạn thực sự cần một danh sách, tôi nghĩ rằng chức năng tốt nhất là chỉ

parFold f = foldl1' f . withStrategy (parList rseq) 

hoặc có thể

parFold f = foldl1' f . withStrategy (parBuffer 5 rseq) 

Nếu bước giảm rất phức tạp, bạn có thể có được một lợi bởi phân chia danh sách như thế này:

parReduce f = foldl' f mempty . reducedList . chunkList . withStrategy (parList rseq) 
where 
    chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls 
    reducedList = parMap rseq (foldl' f mempty) 

tôi đã lấy sự tự do của giả định dữ liệu của bạn là một Monoid cho mempty, nếu điều này là không thể bạn có thể thay thế mempty với loại sản phẩm nào của riêng bạn, hoặc tệ hơn trường hợp sử dụng foldl1'.

Có hai toán tử từ Control.Parallel.Strategies được sử dụng tại đây. Các parList đánh giá tất cả các mục của danh sách song song. Sau đó, chunkList chia danh sách thành các phần của 1000 phần tử. Mỗi khối này sau đó được giảm song song với parMap.

Bạn cũng có thể thử

parReduce2 f = foldl' f mempty . reducedList . chunkList 
where 
    chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls 
    reducedList = parMap rseq (foldl' f mempty) 

Tùy thuộc vào chính xác cách thức các công việc được phân phối, một trong những có thể hiệu quả hơn những người khác.

Nếu bạn có thể sử dụng cấu trúc dữ liệu có hỗ trợ tốt cho việc lập chỉ mục (Array, Vector, Map, vv), thì bạn có thể làm phân mục nhị phân cho bước giảm, có thể sẽ tốt hơn.

Answer 2

Điều này có vẻ giống như một sự khởi đầu tốt:

parFold :: (a -> a -> a) -> [a] -> a 
parFold f = go 
    where 
    strategy = parList rseq 

    go [x] = x 
    go xs = go (reduce xs `using` strategy) 

    reduce (x:y:xs) = f x y : reduce xs 
    reduce list  = list -- empty or singleton list 

Đó hoạt động, nhưng song song không phải là quá tuyệt vời. Thay thế parList với một cái gì đó như parListChunks 1000 giúp một chút, nhưng tăng tốc vẫn còn giới hạn dưới 1,5x trên một máy 8 lõi.

Answer 3

Không chắc chắn chức năng parFold của bạn là gì phải làm. Nếu đó là dự định là một phiên bản song song của foldr hoặc foldl, tôi nghĩ định nghĩa của nó là sai.

parFold :: (a -> a -> a) -> [a] -> a 

// fold right in haskell (takes 3 arguments) 
foldr :: (a -> b -> b) -> b -> [a] -> b 

Lần áp dụng cùng một chức năng cho từng phần tử trong danh sách và tích lũy kết quả của mỗi ứng dụng. Đến với một phiên bản song song của nó, tôi đoán, sẽ yêu cầu rằng các ứng dụng chức năng cho các yếu tố được thực hiện song song - một chút giống như những gì parList nào.

par_foldr :: (NFData a, NFData b) => (a -> b -> b) -> b -> [a] -> b 
    par_foldr f z [] = z 
    par_foldr f z (x:xs) = res `using` \ _ -> rseq x' `par` rdeepseq res 
         where x' = par_foldr f z xs 
          res = x `f` x'