Haskell ejecución paralela especulativa

concurrency parallel-processing

Question

Estoy pensando en explotar 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'' está en O (n ² ), ''S1b'' sobre todo se comporta mejor, pero el peor caso es sobre O (n ⁴ ).

Primera pregunta: ¿hay alguna manera simple de ejecutar S1a y S1b en paralelo, usar el que termina primero y el otro? 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 difícil: 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 estimación de una puntuación) como 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ñas, haciendo que s2 y s3 ​​converjan más rápido si no existe una mejor solución (o al menos deseche las peores soluciones y así sea 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, por ejemplo, S2 y S3 en paralelo de tal manera que lo que termine primero actualice 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 terminará utilizando ForkIO bajo el capó porque quiere que ocurran múltiples transacciones en paralelo. 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 consultar 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 una mónada 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 de MonadFix apropiada para tratar la recursividad o llamadas de ''rendimiento'' abundantemente salpicadas, puede realizar ambas operaciones en la mónada parcial y competir con ellas para obtener un resultado determinista.

Pero en la práctica, si desea obtener el beneficio completo del paralelismo, querrá actualizar y verificar algún tipo de ''mejora'' 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, eso debería poder reescribirse para soportar cualquier monoide conmutativo idempotente, no solo el máximo.

Answer 2

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