Esecuzione parallela speculativa Haskell

Question

Sto pensando di sfruttare il parallelismo per un problema che sto cercando di risolvere. Il problema è grosso modo questo: l'input dato (sequenza di punti) trova un output migliore (il più grande triangolo composto da questi punti, la linea più lunga ecc.). Ci sono 3 diverse 'forme' da trovare nella sequenza di punti, tuttavia mi interessa solo quella con il 'miglior punteggio' (di solito una qualche forma di coefficiente dei tempi di 'lunghezza'). Chiamiamo le forme S1, S2, S3.

Ho 2 diversi algoritmi per risolvere S1 - 'S1a' è in O (n), 'S1b' comporta principalmente migliore, ma il caso peggiore è di circa O (n).

Prima domanda: esiste un modo semplice per eseguire S1a e S1b in parallelo, utilizzare quello che termina per primo e interrompere l'altro? Per quanto sto leggendo la documentazione, questo potrebbe essere programmato usando alcuni forkIO e uccidendo i thread quando si ottiene un risultato - basta chiedere se c'è qualcosa di più semplice?

Seconda domanda - molto più dura: Sto chiamando la funzione di ottimizzazione in questo modo:

optimize valueOfSx input 

valueOfSx è specifico per ogni forma e restituisce un 'punteggio' (o una supposizione di una partitura) una possibile soluzione. Ottimizza chiama questa funzione per trovare la soluzione migliore. Ciò che mi interessa è:

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

Tuttavia, se conosco il risultato della S1, posso scartare tutte le soluzioni che sono più piccoli, rendendo così S2 ed S3 convergere più velocemente se una soluzione migliore esiste (o almeno due via le peggiori soluzioni e quindi essere più efficienti nello spazio). Quello che sto facendo ora è:

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 

La domanda è: posso eseguire ad es. S2 e S3 in parallelo in questo modo, che termina per prima cosa aggiornerebbe il parametro 'threshold' della funzione score in esecuzione nell'altro thread? Qualcosa nel senso di:

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

Answer 1

In definitiva, qualunque soluzione sarà vento utilizzando ForkIO sotto il cofano, perché si vuole più transazioni di essere presenti in parallelo. Anche la monotambia di Conal funziona in questo modo.

Per quest'ultimo è preferibile un monad più complicato che si accumula e viene eseguito per un po 'prima di controllare occasionalmente un MVar per un valore di miglioramento monotonicamente pubblicato, ma la risposta più semplice per interlacciare (all'interno di un thread) è scrivere semplicemente un Monade di parzialità.

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

Con un'istanza MonadFix opportuno trattare con la ricorsione o generosamente cosparso 'resa' chiamate, è possibile eseguire entrambe le operazioni in monade parziale e correre loro di ottenere un risultato deterministico.

Ma in pratica, se si desidera ottenere il massimo vantaggio dal parallelismo, è necessario aggiornare e controllare periodicamente un tipo di MVar "di miglioramento".

Qualcosa come (a braccio, scusa, nessun compilatore a portata di mano!):

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 

Naturalmente, che dovrebbe essere in grado di essere riscritta per supportare qualsiasi monoide commutativa idempotente, non solo max.

Answer 2

Per la prima domanda, Check-Out di unamb Conal Elliott: http://hackage.haskell.org/package/unamb