Thực hiện song song đầu cơ Haskell

Question

Tôi đang suy nghĩ về khai thác song song đối với một vấn đề mà tôi đang cố giải quyết. Vấn đề là khoảng này: cho đầu vào (chuỗi các điểm) tìm thấy một đầu ra tốt nhất (tam giác lớn nhất bao gồm từ những điểm này, dòng dài nhất vv). Có 3 'hình dạng' khác nhau được tìm thấy trong chuỗi các điểm, tuy nhiên tôi chỉ quan tâm đến một 'điểm tốt nhất' (thường là một dạng của hệ số thời gian 'chiều dài'). Hãy gọi các hình S1, S2, S3.

tôi có 2 thuật toán khác nhau để giải quyết S1 - 'S1A' là trong thời gian O (n), 'S1b' chủ yếu là cư xử tốt hơn, nhưng trường hợp xấu nhất là khoảng O (n).

Câu hỏi đầu tiên: có cách nào đơn giản để chạy S1a và S1b song song, sử dụng kết thúc đầu tiên và dừng cái kia không? Theo như tôi đang đọc tài liệu, điều này có thể được lập trình bằng cách sử dụng một số ngã ba và giết chết các chủ đề khi một kết quả thu được - chỉ cần hỏi nếu có cái gì đơn giản hơn?

Câu hỏi thứ hai - khó khăn hơn nhiều: Tôi gọi hàm tối ưu hóa theo cách này:

optimize valueOfSx input 

valueOfSx là cụ thể cho mỗi hình dạng và trả về một 'điểm' (hoặc đoán của điểm a) một giải pháp khả thi. Optimize gọi hàm này để tìm ra giải pháp tốt nhất. Những gì tôi quan tâm là:

s1 = optimize valueOfS1 input 
s2 = optimize valueOfS2 input 
s3 = optimize valueOfS3 input 
<- maximum [s1,s2,s3] 

Tuy nhiên, nếu tôi biết kết quả của S1, tôi có thể loại bỏ tất cả các giải pháp có kích thước nhỏ, do đó làm cho s2 và s3 hội tụ nhanh hơn nếu không có giải pháp tốt hơn tồn tại (hoặc ít nhất là ném đi những giải pháp tồi tệ nhất và do đó có nhiều không gian hiệu quả hơn). Những gì tôi đang làm bây giờ là:

zeroOn threshold f = decide .f 
    where decide x = if (x < threshold) then 0 else x 
s1 = optimize valueOfS1 input 
s2 = optimize (zeroOn s1 valueOfS2) input 
s3 = optimize (zeroOn (max s1 s2) valueOfS3) input 

Câu hỏi đặt ra là: tôi có thể chạy ví dụ: S2 và S3 song song theo cách như vậy, bất kỳ kết thúc nào trước tiên sẽ cập nhật tham số 'ngưỡng' của hàm số điểm đang chạy trong luồng khác? Một cái gì đó theo nghĩa:

threshold = 0 
firstSolution = firstOf (optimize (zeroOn threshold valueOfS2), optimize (zeroOn threshold valueofS3)) 
update threshold from firstSolution 
wait for second solution 

Answer 1

Cuối cùng, giải pháp nào sẽ gió lên bằng ForkIO dưới mui xe bởi vì bạn muốn nhiều giao dịch được diễn ra trong song song, tương đông. Ngay cả unal của Conal cũng hoạt động theo cách này.

Đối với thứ hai, bạn có thể muốn một đơn nguyên phức tạp hơn xếp hàng và chạy trong một thời gian trước khi kiểm tra MVar thỉnh thoảng cho giá trị cải tiến đơn điệu, nhưng câu trả lời đơn giản nhất để xen kẽ (chỉ trong một chủ đề) Partiality monad.

data Partial a = Return a | Partial (Partial a) 

instance Monad Partial where 
    return = Return 
    Return a >>= f = f a 
    Partial m >>= f = Partial (m >>= k) 


run :: Partial a -> a 
run (Partial m) = run m 
run (Return a) = a 

race :: Partial a -> Partial a -> Partial a 
race (Return a) _ = a 
race _ (Return b) = b 
race (Partial m) (Partial n) = race m n 

yield :: Partial() 
yield = Partial (Return()) 

Với một thể hiện MonadFix thích hợp để đối phó với đệ quy hoặc tự do rắc 'năng suất' cuộc gọi, bạn có thể thực hiện cả hai hoạt động của bạn trong đơn nguyên phần và chủng tộc họ để có được một kết quả xác định.

Nhưng trong thực tế, nếu bạn muốn nhận được toàn bộ lợi ích của tính song song, bạn sẽ muốn cập nhật và kiểm tra một số loại 'cải thiện' MVar theo định kỳ.

Một cái gì đó như (tắt còng, xin lỗi, không có trình biên dịch nào tiện dụng!):

import Control.Concurrent.MVar (newMVar, readMVar) 
import Control.Parallel.Strategies (using, parList) 
import GHC.IOBase (unsafeDupablePerformIO, unsafePerformIO) 

diag x = (x,x) 

parMax :: (Bounded a, Ord a) => [a] -> a 
parMax xs = unsafePerformIO $ do 
    threshold <- newMVar minBound 
    let optimize x = unsafeDupablePerformIO $ 
     x `seq` modifyMVar threshold (return . diag . max x) 
    return . maximum $ map optimize xs `using` parList 

Tất nhiên, bạn có thể viết lại để hỗ trợ bất kỳ monoid giao hoán không có tính chất nào, không chỉ tối đa.

Answer 2

Đối với câu hỏi đầu tiên, Kiểm tra Conal Elliott của unamb: http://hackage.haskell.org/package/unamb