¿Cómo explotar cualquier paralelismo en mi código paralelo haskell?

Question

Acabo de decir que trabajé en el paralelismo semi-explícito de Haskell con GHC 6.12. He escrito el siguiente código haskell para calcular en paralelo el mapa de la función fibonnaci sobre 4 elementos en una lista, y al mismo tiempo el mapa de la función sumEuler sobre dos elementos.

import Control.Parallel 
import Control.Parallel.Strategies 

fib :: Int -> Int 
fib 0 = 0 
fib 1 = 1 
fib n = fib (n-1) + fib (n-2) 

mkList :: Int -> [Int] 
mkList n = [1..n-1] 

relprime :: Int -> Int -> Bool 
relprime x y = gcd x y == 1 

euler :: Int -> Int 
euler n = length (filter (relprime n) (mkList n)) 

sumEuler :: Int -> Int 
sumEuler = sum . (map euler) . mkList 

-- parallel initiation of list walk                                  
mapFib :: [Int] 
mapFib = map fib [37, 38, 39, 40] 

mapEuler :: [Int] 
mapEuler = map sumEuler [7600, 7600] 

parMapFibEuler :: Int 
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler)) 

-- how to evaluate in whnf form by forcing                                 
forceList :: [a] ->() 
forceList [] =() 
forceList (x:xs) = x `pseq` (forceList xs) 


main = do putStrLn (" sum : " ++ show parMapFibEuler) 

para mejorar mi programa en paralelo Reescribí con par y PSEQ y un forzamiento función para forzar la evaluación whnf. Mi problema es que al mirar en el subámbito parece que no obtuve ningún paralelismo. Las cosas son peores porque no gané ninguna aceleración.

Eso por eso que tengo dos preguntas tesis

Pregunta 1 ¿Cómo podría modificar mi código para explotar cualquier paralelismo?

Pregunta 2 ¿Cómo podría escribir mi programa para usar Strategies (parMap, parList, rdeepseq y así sucesivamente ...)?

primera mejora con estrategias

según su contribución

parMapFibEuler = (mapFib, mapEuler) `using` s `seq` (sum mapFib + sum mapEuler) where 
    s = parTuple2 (seqList rseq) (seqList rseq) 

el paralelismo aparece en la threadscope pero no lo suficiente como para tener una aceleración significativa

Answer 1

Su paralelismo es demasiado claro de grano a tener mucho efecto beneficioso. Los trozos de trabajo más grandes que se pueden realizar en paralelo de manera eficiente están en sumEuler, por lo que es allí donde debe agregar sus anotaciones par. Intente cambiar a sumEuler:

sumEuler :: Int -> Int 
sumEuler = sum . (parMap rseq euler) . mkList 

parMap es de Control.Parallel.Strategies; expresa un mapa que se puede hacer en paralelo. El primer argumento, rseq que tiene el tipo Strategy a, se utiliza para forzar el cálculo a un punto específico, de lo contrario no se realizaría ningún trabajo, debido a la pereza. rseq está bien para la mayoría de los tipos numéricos.

No es útil agregar paralelismo a fib aquí, debajo de aproximadamente fib 40 no hay suficiente trabajo para que valga la pena.

Además de threadscope, es útil para ejecutar su programa con la bandera -s. Busque una línea como:

SPARKS: 15202 (15195 converted, 0 pruned) 

en la salida. Cada chispa es una entrada en una cola de trabajo para posiblemente realizarse en paralelo. Las chispas convertidas en realidad se hacen en paralelo, mientras que las chispas podadas significan que el hilo principal llegó a ellos antes de que un hilo trabajador tuviera la oportunidad de hacerlo. Si el número podado es alto, significa que sus expresiones paralelas son demasiado finas. Si la cantidad total de chispas es baja, no estás tratando de hacer lo suficiente en paralelo.

Por último, creo que es mejor parMapFibEuler escribirse como:

parMapFibEuler :: Int 
parMapFibEuler = sum (mapFib `using` parList rseq) + sum mapEuler 

mapEuler es simplemente demasiado corta para tener cualquier paralelismo útil expresado aquí, especialmente como euler ya se lleva a cabo en paralelo. Dudo que también haga una diferencia sustancial para mapFib. Si las listas mapFib y mapEuler fueran más largas, el paralelismo aquí sería más útil. En lugar de parList, puede usar parBuffer, que tiende a funcionar bien para los consumidores de la lista.

Hacer estos dos cambios corta el tiempo de ejecución de 12s a 8s para mí, con GHC 7.0.2.

Answer 2

Hmmm. .. ¿Tal vez?

((forceList mapFib) `par` (forceList mapEuler)) `pseq` (sum mapFib + sum mapEuler) 

I.e. engendrar mapFib en el fondo y calcular mapEuler y solo después de que (mapEuler) hacer (+) de sus sumas. En realidad, yo supongo que se puede hacer algo como:

parMapFibEuler = a `par` b `pseq` (a+b) where 
    a = sum mapFib 
    b = sum mapEuler 

Sobre la Q2: Como sé estrategias - es decir las "estrategias" que combinan estructuras de datos con los par y seq.
Usted puede escribir su forceList = withStrategy (seqList rseq)
Como bien se puede escribir el código como:

parMapFibEuler = (mapFib, mapEuler) `using` s `seq` (sum mapFib + sum mapEuler) where 
    s = parTuple2 (seqList rseq) (seqList rseq) 

es decir, La estrategia aplicada a la tupla de dos listas forzará su evaluación en paralelo, pero cada lista será forzada a ser evaluada secuencialmente.

Answer 3

En primer lugar, supongo que sabes que tu definición de fib es horrible y solo estás haciendo esto para jugar con el paquete paralelo.

Parece que va por el paralelismo en el nivel equivocado. Paralelizar mapFib y mapEuler no dará una buena aceleración porque hay más trabajo para calcular mapFib.Lo que debe hacer es calcular cada uno de estos elementos muy caros en paralelo, lo cual es ligeramente más fino grano, pero no demasiado:

mapFib :: [Int] 
mapFib = parMap rdeepseq fib [37, 38, 39, 40] 

mapEuler :: [Int] 
mapEuler = parMap rdeepseq sumEuler [7600, 7600, 7600,7600] 

parMapFibEuler :: Int 
parMapFibEuler = sum a + sum b 
    where 
    a = mapFib 
    b = mapEuler 

Además, he luchado originalmente usando Control.Parallel.Strategies sobre Control.Parallel pero han llegado que le guste, ya que es más legible y evita problemas como el suyo, donde uno esperaría el paralelismo y tendría que entrecerrar los ojos para descubrir por qué no está obteniendo ninguno.

Por último, siempre se debe publicar cómo se compila y cómo ejecutar código que está esperando ser parallelized. Por ejemplo:

$ ghc --make -rtsopts -O2 -threaded so.hs -eventlog -fforce-recomp 
[1 of 1] Compiling Main    (so.hs, so.o) 
Linking so ... 
$ ./so +RTS -ls -N2 
sum : 299045675 

Rendimiento:

Answer 4

La razón por la que no está viendo ningún paralelismo aquí es porque su chispa ha sido recogido de basura.Ejecutar el programa con +RTS -s y tenga en cuenta esta línea:

SPARKS: 1 (0 converted, 1 pruned) 

la chispa ha sido "podado", lo que significa eliminado por el recolector de basura. En GHC 7 hicimos un cambio en la semántica de las chispas, de modo que una chispa ahora es basura recolectada (GC) si no se menciona en el resto del programa; los detalles están en the "Seq no more" paper.

¿Por qué la chispa GC está en su caja? Mira el código:

parMapFibEuler :: Int 
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler)) 

la chispa aquí es la expresión forkList mapFib. Tenga en cuenta que el valor de esta expresión no es requerido por el resto del programa; solo aparece como argumento en par. GHC sabe que no es necesario, por lo que se recoge la basura.

El objetivo de los cambios recientes en el paquete parallel fue permitirle evitar fácilmente esta trampa para osos. Una buena regla general es usar Control.Parallel.Strategies en lugar de par y pseq directamente. Mi forma preferida de escribir esto sería

parMapFibEuler :: Int 
parMapFibEuler = runEval $ do 
    a <- rpar $ sum mapFib 
    b <- rseq $ sum mapEuler 
    return (a+b) 

pero lamentablemente esto no funciona con GHC 7.0.2, debido a que la chispa se sum mapFib flotaba como una expresión estática (una CAF) y el tiempo de ejecución no lo hace Creo que las chispas que apuntan a expresiones estáticas valen la pena (lo arreglaré). ¡Esto no sucedería en un programa real, por supuesto! Así que vamos a hacer el programa un poco más realista y derrota a la optimización de la CAF:

parMapFibEuler :: Int -> Int 
parMapFibEuler n = runEval $ do 
    a <- rpar $ sum (take n mapFib) 
    b <- rseq $ sum (take n mapEuler) 
    return (a+b) 

main = do [n] <- fmap (fmap read) getArgs 
      putStrLn (" sum : " ++ show (parMapFibEuler n)) 

ahora tengo buena paralelismo con GHC 7.0.2. Sin embargo, tenga en cuenta que los comentarios de @John también se aplican: en general, desea buscar un paralelismo más preciso para que GHC pueda usar todos sus procesadores.