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

Question

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

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

У меня есть 2 различных алгоритма для решения S1 - 'S1a' находится в O ⁽ⁿ²⁾, 'S1b' главным образом ведет себя лучше, но худший случай о O ⁽ⁿ⁴⁾.

Первый вопрос: там некоторый простой путь состоит в том, чтобы выполнить 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 = 0
firstSolution = firstOf (optimize (zeroOn threshold valueOfS2), optimize (zeroOn threshold valueofS3))
update threshold from firstSolution
wait for second solution

8

haskell concurrency parallel-processing speculative-execution

задан Michael Myers 24 October 2011 в 22:40

2 ответа

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

5

ответ дан 5 December 2019 в 17:37

Другие вопросы по тегам:

haskell concurrency parallel-processing speculative-execution

Похожие вопросы:

score 5 · Accepted Answer

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

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

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

Но на практике, если вы хотите получить все преимущества параллелизма, вы захотите периодически обновлять и проверять некий 'улучшающий' 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

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