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

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

У меня есть 2 разных алгоритма для решения S1 - "S1a" в O (n2), "S1b" в основном ведет себя лучше, но наихудший случай касается O (n4).

Первый вопрос: есть ли какой-нибудь простой способ запустить 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
Источник

2 ответа

Решение

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

Для последнего вам, вероятно, понадобится более сложная монада, которая собирается и запускается некоторое время, прежде чем время от времени проверять 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

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

Источник

Для первого вопроса, проверить Конал Эллиотта unamb: http://hackage.haskell.org/package/unamb

Источник
Другие вопросы по тегам