Programación multinúcleo en Haskell - Control.Parallel

Question

Estoy tratando de aprender a usar el módulo Control.Parallel, pero creo que no lo entendí bien.

Estoy tratando de ejecutar el siguiente código (fibs.hs).

import Control.Parallel 

fib :: Int -> Int 
fib 0 = 0 
fib 1 = 1 
fib n = p `par` (q `pseq` (p + q)) 
    where 
     p = fib (n-1) 
     q = fib (n-2) 


main = print $ fib 30 

Compilé esto con:

ghc -O2 --make -threaded fibs.hs 

Y entonces consigo los siguientes resultados ejecución de este programa (salida de un script en Python que se ejecuta cada programa 100 veces y devuelve el promedio y la desviación estándar de la tiempo de ejecución):

./fibs +RTS -N1 -> avg= 0.060203 s, deviation = 0.004112 s 
./fibs +RTS -N2 -> avg= 0.052335 s, deviation = 0.006713 s 
./fibs +RTS -N3 -> avg= 0.052935 s, deviation = 0.006183 s 
./fibs +RTS -N4 -> avg= 0.053976 s, deviation = 0.007106 s 
./fibs +RTS -N5 -> avg= 0.055227 s, deviation = 0.008598 s 
./fibs +RTS -N6 -> avg= 0.055703 s, deviation = 0.006537 s 
./fibs +RTS -N7 -> avg= 0.058327 s, deviation = 0.007526 s 

Mis preguntas son:

1. Lo que está ocurriendo exactamente cuando evalúo:

   a `par` (b `pseq` (a + b)) ? 
   

   entiendo que un par b se supone dar a entender que el compilador sobre el cálculo de una en paralelo con b y volver b. DE ACUERDO. ¿Pero qué hace pseq?

2. ¿Por qué veo un aumento de rendimiento tan pequeño? Estoy ejecutando esto en una máquina cuádruple Intel Core 2. Esperaría que correr con -N5 o -N6 no hiciera una diferencia real en el rendimiento o que el programa comenzara a funcionar muy mal. Pero ¿por qué no veo una mejora de -N2 a -N3 y por qué la mejora inicial es tan pequeña?

Answer 1

Como Don explained, el problema es que está creando demasiadas chispas. Así es como puede volver a escribir para obtener una buena aceleración.

import Control.Parallel 

cutoff :: Int 
cutoff = 20 

parFib :: Int -> Int 
parFib n | n < cutoff = fib n 
parFib n = p `par` q `pseq` (p + q) 
    where 
     p = parFib $ n - 1 
     q = parFib $ n - 2 

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

main :: IO() 
main = print $ parFib 40 

demostración:

[computer ~]$ ghc --make -threaded -O2 Main.hs 
[1 of 1] Compiling Main    (Main.hs, Main.o) 
Linking Main ... 
[computer ~]$ time ./Main +RTS -N1 
102334155 

real 0m1.509s 
user 0m1.450s 
sys  0m0.003s 
[computer ~]$ time ./Main +RTS -N2 
102334155 

real 0m0.776s 
user 0m1.487s 
sys  0m0.023s 
[computer ~]$ time ./Main +RTS -N3 
102334155 

real 0m0.564s 
user 0m1.487s 
sys  0m0.030s 
[computer ~]$ time ./Main +RTS -N4 
102334155 

real 0m0.510s 
user 0m1.587s 
sys  0m0.047s 
[computer ~]$ 

Answer 2

Re (1): par permite a computado de otro hilo. Supongo que aquí, pero creo que pseq se comporta de forma muy similar a seq: obliga a calcular primero el primer resultado (bueno, seq no garantiza esto, pero en la práctica en GHC sí lo hace). Entonces en este caso, el cómputo de a se bifurca como un hilo, y el otro subproceso calcula b y luego suma a y b.

Re (2): Este es un cálculo bastante trivial que se bifurca a otros hilos; probablemente sea tan rápido para que la CPU simplemente lo calcule solo. Estoy apostando a que la sobrecarga de hilos está lastimando casi tanto como ayudando con este simple cálculo.

Answer 3

Está creando un número exponencial de chispas (piense en cuántas llamadas recursivas está creando aquí). Para obtener un buen paralelismo, debe crear menos trabajo paralelo en este caso, ya que su hardware no puede manejar tantos subprocesos (por lo que GHC no los hace).

La solución es utilizar una estrategia de corte, tal como se describe en esta charla: http://donsbot.wordpress.com/2009/09/05/defun-2009-multicore-programming-in-haskell-now/

Básicamente, cambiar a la versión en línea recta una vez que llegan a cierta profundidad, y el uso + RTS -sstderr para ver cuántos las chispas se están convirtiendo, por lo que puede determinar si está perdiendo el trabajo o no.

Answer 4

Ya que nadie dio una respuesta definitiva sobre pseq, aquí está la official description: ss :

semánticamente idéntica a la SEC, pero con una diferencia operativa sutil es estricto en sus dos argumentos, , por lo que el compilador puede, por ejemplo, reorganizar un seq b en b seq un seq b. Esto normalmente no es un problema al usar seq para expresar rigor, pero puede ser un problema cuando anotando el código para el paralelismo, porque necesitamos más control sobre el orden de evaluación ; es posible que deseemos evaluar a antes de b, porque sabemos que b ya se ha activado en en paralelo con el par.

Es por eso que tenemos pseq. En contraste a la SEC, PSEQ sólo es estricta en su primer argumento (por lo que el compilador se refiere), que restringe las transformaciones que el compilador puede hacer , y asegura que el usuario puede mantener el control de la evaluación orden.