Execução paralela especulativa de Haskell

Question

Estou pensando em explorar o paralelismo para um problema que estou tentando resolver. O problema é aproximadamente o seguinte: dada a entrada (sequência de pontos) Encontre a melhor saída (maior triângulo composto a partir desses pontos, linha mais longa etc.). Existem três 'formas' diferentes na sequência de pontos, no entanto, estou interessado apenas no 'melhor pontuação' (geralmente em alguma forma de coeficiente de 'comprimento'). Vamos chamar as formas S1, S2, S3.

Eu tenho 2 algoritmos diferentes para resolver S1 - 'S1a' está em O (n²), 'S1b' se comporta melhor, mas o pior caso é sobre O (n⁴).

Primeira pergunta: Existe uma maneira simples de executar S1A e S1B em paralelo, use um que termine primeiro e pare o outro? Tanto quanto estou lendo a documentação, isso pode ser programado usando alguns Forkio e matando os threads quando um resultado é obtido - apenas perguntando se há algo mais simples?

Segunda pergunta - muito mais difícil: estou chamando a função de otimização da seguinte maneira:

optimize valueOfSx input

O Valueofsx é específico para cada forma e retorna uma 'pontuação' (ou um palpite de uma pontuação) uma solução possível. Otimize chama essa função para descobrir a melhor solução. O que estou interessado é:

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

No entanto, se eu souber o resultado do S1, posso descartar todas as soluções menores, fazendo com que S2 e S3 convergem mais rapidamente se não houver uma solução melhor (ou pelo menos jogar fora as piores soluções e, portanto, ser mais eficiente em termos de espaço). O que estou fazendo agora é:

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

A questão é: posso executar o EG S2 e o S3 em paralelo de tal maneira, o que o acabamento primeiro atualizaria o parâmetro 'limite' da função de pontuação em execução no outro thread? Algo no sentido de:

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

Answer 1

Por fim, qualquer solução acabará usando o Forkio sob o capô, porque você deseja que várias transações ocorram em paralelo. Até o Unbmb de Conal funciona dessa maneira.

Para o último, você provavelmente deseja uma mônada mais complicada que lotes e corre por um tempo antes de verificar um MVAR ocasionalmente para um valor de melhoria monotonicamente postado, mas a resposta mais simples para intercalada (dentro de um tópico) é apenas escrever uma Monad Pariality.

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 ())

Com uma instância apropriada do Monadfix para lidar com a recursão ou as chamadas de 'rendimento' liberalmente, você pode executar duas operações na mônada parcial e enfrentá -las para obter um resultado determinístico.

Mas, na prática, se você deseja obter o benefício total do paralelismo, deseja atualizar e verificar algum tipo de 'melhoria' do MVAR periodicamente.

Algo como (fora do punho, desculpe, sem compilador 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

Obviamente, isso deve ser capaz de ser reescrito para apoiar qualquer monoide comutativo idempotente, não apenas no máximo.

Answer 2

Para a primeira pergunta, confira Conal Elliott's unamb: http://hackage.haskell.org/package/unamb