Haskell ejecución paralela especulativa

Question

Estoy pensando en aprovechar el paralelismo para un problema que estoy tratando de resolver. El problema es más o menos esto: entrada dada (secuencia de puntos) encuentra una mejor salida (el triángulo más grande compuesto de estos puntos, la línea más larga, etc.). Hay 3 "formas" diferentes que se encuentran en la secuencia de puntos, sin embargo, solo me interesa el que tiene "mejor puntaje" (por lo general, alguna forma de coeficiente de "longitud"). Llamemos a las formas S1, S2, S3.

tengo 2 algoritmos diferentes para resolver S1 - 'S1a' es en O (n), 'S1b' en su mayoría se comporta mejor, pero el peor de los casos se trata de O (n).

Primera pregunta: ¿hay alguna manera simple de ejecutar S1a y S1b en paralelo, use la que termina primero y la otra? En lo que respecta a la lectura de la documentación, esto podría programarse con algún forkIO y eliminar los hilos cuando se obtiene un resultado, solo preguntando si hay algo más simple.

Segunda pregunta - mucho más dura: Estoy llamando a la función de optimización de esta manera:

optimize valueOfSx input 

valueOfSx es específico para cada forma y devuelve una 'puntuación' (o una suposición de una veintena) una posible solución. Optimize llama a esta función para encontrar la mejor solución. Lo que me interesa es:

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

Sin embargo, si conozco el resultado de S1, puedo descartar todas las soluciones que son más pequeños, con lo que S2 y S3 converger más rápidamente si hay una solución mejor existe (o al menos un tiro las peores soluciones y así ser más eficiente en el uso del espacio). Lo que estoy haciendo ahora es:

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 pregunta es: ¿puedo ejecutar, p. S2 y S3 en paralelo de tal manera, que lo que termine primero ¿actualizaría el parámetro 'umbral' de la función de puntaje que se ejecuta en el otro hilo? Algo en el sentido de:

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

Answer 1

En última instancia, cualquier solución va a acabar usando ForkIO bajo el capó porque quiere múltiples transacciones que se producen en paralela. Incluso la unmb de Conal funciona de esta manera.

Para este último, probablemente desee una mónada más complicada que se acumule y ejecute durante un tiempo antes de comprobar un MVar de vez en cuando para obtener un valor de mejora publicado monótonamente, pero la respuesta más simple para intercalar (dentro de un hilo) es escribir un Monad de parcialidad

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 una instancia MonadFix adecuados para ocuparse de la recursividad o 'rendimiento' generosamente salpicado de llamadas, puede realizar tanto de sus operaciones en la mónada parcial y la raza de ellos para obtener un resultado determinista.

Pero en la práctica, si quiere obtener el beneficio completo del paralelismo, querrá actualizar y comprobar algún tipo de 'mejora' de MVar periódicamente.

Algo así como (fuera de lugar, lo siento, no hay compilador a 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 

Por supuesto, que debe ser capaz de ser reescritos para apoyar cualquier monoide conmutativo idempotente, no sólo máx.

Answer 2

Para la primera pregunta, echa un vistazo a unamb Conal Elliott: http://hackage.haskell.org/package/unamb