¿Cómo escribir código paralelo con vectores Haskell?

Question

Por una parte, en Haskell Vector a parece ser el tipo preferido para usar como una matriz de números. Incluso hay un (incompleto) Vector Tutorial.

Por otro lado, Control.Parallel.Strategies se definen principalmente en términos de Traversable. La biblioteca de vectores no proporciona estas instancias.

La definición completa mínima de Traversable t también debe definir Foldable y

traverse :: Applicative f => (a -> f b) -> t a -> f (t b) 
sequenceA :: Applicative f => t (f a) -> f (t a) 

no veo cómo sequenceA se pueden definir para Data.Vector.Unboxed.Vector. Entonces, ¿cuál es el mejor enfoque para escribir código paralelo con vectores sin caja? ¿Definir algunas estrategias ad hoc nuevas como evalVector o usar par y pseq explícitamente o usar Data.Array en lugar de vectores?

P.S. Plain Array s son paralelizable sin problemas: https://gist.github.com/701888

Answer 1

Es un trabajo de corte para parVector pero esto funcionó para mí:

import qualified Data.Vector as V 
import Control.Parallel.Strategies 
import Control.Parallel 
import Control.DeepSeq 

ack :: Int -> Int -> Int 
ack 0 n = n+1 
ack m 0 = ack (m-1) 1 
ack m n = ack (m-1) (ack m (n-1)) 

main = do 
    let vec = V.enumFromN 1 1000 
    let res = (V.map (ack 2) vec) `using` parVector 
    print res 

parVector :: NFData a => Strategy (V.Vector a) 
parVector vec = eval vec `seq` Done vec 
    where 
    chunkSize = 1 
    eval v 
    | vLen == 0 =() 
    | vLen <= chunkSize = rnf (v V.! 0) -- FIX this to handle chunks > 1 
    | otherwise = eval (V.take half v) `par` eval (V.drop half v) 
    where vLen = V.length v 
      half = vLen `div` 2 

Y la ejecución de este código:

[tommd@Mavlo Test]$ ghc --make -O2 -threaded t.hs 
... dumb warning ... 
[tommd@Mavlo Test]$ time ./t +RTS -N1 >/dev/null 
real 0m1.962s user 0m1.951s sys  0m0.009s 
[tommd@Mavlo Test]$ time ./t +RTS -N2 >/dev/null 
real 0m1.119s user 0m2.221s sys 0m0.005s 

Cuando ejecuto el código con Integer en lugar de Int en el escriba la firma:

[tommd@Mavlo Test]$ time ./t +RTS -N2 >/dev/null 

real 0m4.754s 
user 0m9.435s 
sys  0m0.028s 
[tommd@Mavlo Test]$ time ./t +RTS -N1 >/dev/null 

real 0m9.008s 
user 0m8.952s 
sys  0m0.029s 

Rock!

EDIT: Y una solución que es un poco más cerca de su intento anterior es más limpio (que no utiliza las funciones de tres módulos separados) y funciona muy bien:

parVector :: NFData a => Strategy (V.Vector a) 
parVector vec = 
    let vLen = V.length vec 
     half = vLen `div` 2 
     minChunk = 10 
    in if vLen > minChunk 
     then do 
     let v1 = V.unsafeSlice 0 half vec 
      v2 = V.unsafeSlice half (vLen - half) vec 
     parVector v1 
     parVector v2 
     return vec 
     else 
     evalChunk (vLen-1) >> 
     return vec 
    where 
    evalChunk 0 = rpar (rdeepseq (vec V.! 0)) >> return vec 
    evalChunk i = rpar (rdeepseq (vec V.! i)) >> evalChunk (i-1) 

cosas que aprender de esta solución:

1. utiliza la mónada Eval, que es estricta por lo que estamos seguros de provocar todo (en comparación a envolver las cosas en let y recordar a utilizar patrones de explosión).
2. Contrariamente a su ejecución propuesto que (a) no construye un nuevo vector, lo cual es costoso (b) evalChunk fuerzas de evaluación de cada elemento utilizando rpar y rdeepseq (no creo rpar vec fuerzas de cualquiera de los elementos del vector) .
3. Contrariamente a mi creencia, slice toma un índice y una longitud de inicio, no un índice de inicio y final. Oops!
4. Todavía necesitamos importar Control.DeepSeq (NFData), pero he enviado por correo electrónico la lista de bibliotecas para intentar solucionar ese problema.

El rendimiento parece similar a la primera solución parVector en esta respuesta, por lo que no voy a publicar números.

Answer 2

1) Como usted probablemente sabe, vector es un producto de la DPH trabajo que ha demostrado ser más difícil que los investigadores esperaban inicialmente.

2) Los vectores no compartidos no pueden dividir el trabajo para elementos individuales en varias CPU.

3) Sería mucho más optimista para los vectores en caja. Algo así como:

using (map (rnf . (vec !)) [0..V.length vec - 1]) (parList rdeepseq) 

O tal vez usted puede evitar la construcción de la lista y el uso de PARLIST. Creo que solo asignar partes de la matriz es suficiente. El código siguiente probablemente esté roto, pero el concepto de crear su propio parVector usando rnf y dividir el vector por la mitad hasta que sea un elemento único (o algún tamaño de fragmento sintonizable de elementos) debería funcionar.

parVector :: Strategy (Vector a) 
parVector = let !_ = eval vec in Done vec 
    where 
    chunkSize = 1 
    eval v 
    | vLen == 0 =() 
    | vLen <= chunkSize = rnf (v ! 0) -- FIX this to handle chunks > 1 
    | otherwise = eval (V.take half v) `par` eval (V.drop half v) 
    where vLen = V.length v 
      half = vLen `div` 2