Haskell спекулятивное параллельное исполнение

Question

Я думаю об использовании параллелизма для одной проблемы, которую пытаюсь решить. Проблема примерно такая: данный вход (последовательность точек) находит лучший результат (самый большой треугольник, составленный из этих точек, самая длинная линия и т. Д.). В последовательности точек можно найти 3 разных «фигуры», однако меня интересует только та, у которой «лучший результат» (обычно в некоторой форме, умноженной на коэффициент длины). Назовем фигуры S1, S2, S3.

У меня есть 2 разных алгоритма для решения S1 - «S1a» в O (n ² ), «S1b» в основном ведет себя лучше, но наихудший случай - о O (n ⁴ ).

Первый вопрос: есть ли какой-нибудь простой способ запустить S1a и S1b параллельно, использовать тот, который заканчивается первым, и останавливать другой? Насколько я читаю документацию, это может быть запрограммировано с использованием некоторого forkIO и уничтожение потоков при получении результата - просто спрашиваю, есть ли что-то попроще?

Второй вопрос - гораздо сложнее: я вызываю функцию оптимизации следующим образом:

optimize valueOfSx input

valueOfSx специфично для каждой фигуры и возвращает «оценку» (или оценку оценки) возможное решение. Оптимизация вызывает эту функцию, чтобы найти лучшее решение. То, что меня интересует, это:

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

Однако, если я знаю результат S1, я могу отбросить все решения меньшего размера, и, таким образом, заставить s2 и s3 сходиться быстрее, если лучшего решения не существует (или, по крайней мере, отбросить худшие решения и, таким образом, быть более экономичным). , Что я делаю сейчас:

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

Вопрос: могу ли я запустить, например, S2 и S3 параллельно таким образом, чтобы в зависимости от того, что завершится первым, обновился бы параметр «threshold» функции счета, выполняющейся в другом потоке? Что-то в смысле:

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

Answer 1

В конечном счете, любое решение будет в конечном итоге использовать ForkIO изнутри, потому что вы хотите, чтобы несколько транзакций происходили параллельно. Даже конам Конала работает таким образом.

Для последнего вам, вероятно, понадобится более сложная монада, которая собирается и запускается некоторое время, прежде чем время от времени проверять MVar на монотонно публикуемое улучшающее значение, но самый простой ответ для чередования (в пределах одного потока) - просто написать Partiality монада.

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 для обработки рекурсивных или обильно разбросанных вызовов yield, вы можете выполнять обе свои операции в Частичной монаде и гонять их для получения детерминированного результата.

Но на практике, если вы хотите получить все преимущества параллелизма, вам нужно периодически обновлять и проверять какое-то «улучшение» MVar.

Что-то вроде (не в порядке, извините, компилятор не пригодится!):

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

Конечно, это должно быть в состоянии переписать для поддержки любого идемпотентного коммутативного моноида, а не только макс.

Answer 2

По первому вопросу: Конал Эллиота unamb: http://hackage.haskell.org/package/unamb