Haskell推测并行执行 [英] Haskell speculative parallel execution

问题描述

我正在考虑对于我想解决的一个问题利用并行性。问题大致如下：给定输入（点序列）找到最佳输出（由这些点组成的最大三角形，最长线等）。在点序列中存在3种不同的形状，但是我只对具有最好分数（通常是某种形式的长度乘积系数）的形状感兴趣。让我们调用形状S1，S2，S3。

I am thinking about exploiting parallelism for one problem I am trying to solve. The problem is roughly this: given input (sequence of points) find a best output (biggest triangle composed from these points, longest line etc.). There are 3 different 'shapes' to be found in the sequence of points, however I am interested only in the one with 'best score' (usually some form of 'length' times coefficient). Let's call the shapes S1, S2, S3.

我有两个不同的算法用于求解S1 - 'S1a'在O（n < ），S1b主要表现更好，但是最坏情况是大约O（n <4> ）。

I have 2 different algorithms for solving S1 - 'S1a' is in O(n²), 'S1b' mostly behaves better, but the worst case is about O(n⁴).

第一个问题：是否有一些简单的方法可以并行运行S1a和S1b，使用先完成后停止另一个？至于我正在阅读的文档，这可以编程使用一些forkIO和杀死的线程，当一个结果获得 - 只是问是否有一些更简单？

First question: is there some simple way to run S1a and S1b in parallel, use the one that finishes first and stop the other? As far as I am reading documentation, this could be programmed using some forkIO and killing the threads when a result is obtained - just asking if there is something simpler?

第二个问题 - 更强大：我以这种方式调用优化函数：

Second question - much tougher: I am calling the optimization function this way:

optimize valueOfSx input

valueOfSx特定于每个形状，并返回可能的解决方案的分数（或猜分数）。 Optimize调用此函数找出最佳解决方案。我感兴趣的是：

valueOfSx is specific for every shape and returns a 'score' (or a guess of a score) a possible solution. Optimize calls this function to find out best solution. What I am interested in is:

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

如果我知道S1的结果，我可以丢弃更小的所有解决方案，从而使得s2和s3如果没有更好的解决方案存在（或者至少丢弃最差的解决方案，因此更高的空间效率），收敛得更快。我现在做的是：

However, if I know the result of S1, I can discard all solutions that are smaller, thus making s2 and s3 converge faster if no better solution exists (or at least throw away the worst solutions and thus be more space efficient). What I am doing now is:

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

问题是：我可以运行eg S2和S3以这样的方式并行：哪一个最先完成将更新在另一个线程中运行的分数函数的threshold参数？某种意义上的：

The question is: can I run e.g. S2 and S3 in parallel in such a way, that whichever finishes first would update the 'threshold' parameter of the score function running in the other thread? Something in the sense of:

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

推荐答案

最终，任何解决方案都将使用ForkIO在引擎盖下结束，因为您想要并行发生多个事务。

Ultimately, any solution will wind up using ForkIO under the hood because you want multiple transactions to be occurring in parallel. Even Conal's unamb works this way.

对于后者，你可能需要一个更复杂的monad，它会在一段时间内检查一个MVar，值，但是交织（在一个线程内）的最简单的答案是只写一个Partiality monad。

For the latter you probably want a more complicated monad that batches up and runs for a while before checking an MVar occasionally for a monotonically posted improving value, but the simplest answer to interleave (within one thread) is to just write a 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 ())

MonadFix实例来处理递归或自由地产生调用，你可以在部分monad中执行你的操作，然后比赛他们获得一个确定的结果。

With an appropriate MonadFix instance to deal with recursion or liberally sprinkled 'yield' calls, you can perform both of your operations in the Partial monad and race them to obtain a deterministic result.

但是在实践中，如果你想获得并行性的全部好处，你需要定期更新和检查某种改进MVar。

But in practice, if you want to get the full benefit of parallelism you'll want to update and check some kind of 'improving' MVar periodically.

cuff，sorry，no compiler handy！）：

Something like (off the cuff, sorry, no compiler handy!):

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

当然，应该可以重写为支持任何幂等的交换monoid，不只是最大。

Of course, that should be able to be rewritten to support any idempotent commutative monoid, not just max.

这篇关于Haskell推测并行执行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！