Come scrivere codice parallelo con i vettori Haskell?

Question

Da una parte, in Haskell Vector a sembra essere il tipo preferito da utilizzare come matrice di numeri. C'è anche un (incompleto) Vector Tutorial.

D'altra parte, Control.Parallel.Strategies sono definiti principalmente in termini di Traversable. La libreria vettoriale non fornisce queste istanze.

La definizione completa minima di Traversable t dovrebbe anche definire Foldable e

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

Io non vedo come sequenceA possono essere definiti per Data.Vector.Unboxed.Vector. Quindi, qual è l'approccio migliore per scrivere codice parallelo con vettori non condivisi? Definendo alcune nuove strategie ad hoc come evalVector o usando par e pseq esplicitamente o usando il semplice Data.Array anziché i vettori?

P.S. Plain Array s sono parallelizzabile senza problemi: https://gist.github.com/701888

Answer 1

E 'un lavoro hack per parVector, ma questo ha funzionato per me:

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 

E esecuzione di questo codice:

[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 

Quando eseguo il codice con Integer invece di Int nel type signature:

[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: E una soluzione che è un po 'più vicino alla vostra precedente tentativo è più pulito (non utilizzare le funzioni da tre moduli separati) e funziona alla grande:

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) 

cose da imparare da questa soluzione:

1. Esso utilizza il Eval monade, che è stretta così siamo sicuri di suscitare tutto (rispetto ad avvolgere le cose in let e ricordando di usare modelli Bang).
2. Contrariamente a l'implementazione proposto esso (a) non costruisce un nuovo vettore, che è costosa (b) valutazione evalChunk forze di ogni elemento utilizzando rpar e rdeepseq (non credo rpar vec forze qualsiasi degli elementi del vettore) .
3. Contrariamente a quanto crediamo, slice prende un indice e una lunghezza iniziali, non un indice iniziale e finale. Oops!
4. Abbiamo ancora bisogno di importare Control.DeepSeq (NFData), ma ho inviato per e-mail l'elenco delle librerie per provare a risolvere il problema.

Le prestazioni sembrano simili alla prima soluzione parVector in questa risposta, quindi non invierò numeri.

Answer 2

1) Come probabilmente sapete, vector è un prodotto della DPH lavoro che ha dimostrato più difficile di quanto i ricercatori hanno inizialmente previsti.

2) I vettori Unboxed non possono suddividere il lavoro per i singoli elementi su più CPU.

3) Sarei molto più fiducioso per i vettori in scatola. Qualcosa di simile:

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

O forse si può evitare di costruire la lista e usare parlist. Penso che sia sufficiente assegnare parti dell'array. Il codice riportato di seguito è probabilmente rotto, ma il concetto di creare il proprio parVector utilizzando rnf e dividendo il vettore a metà fino a quando non si tratta di un singolo elemento (o di alcune dimensioni di elementi modificabili degli elementi) dovrebbe funzionare.

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