Jak napisać kod równoległy za pomocą wektorów Haskella?

Question

Jedna ręka, w języku Haskell Vector a, wydaje się być preferowanym typem używanym jako tablica liczb. Istnieje nawet (niekompletne) Vector Tutorial.

Z drugiej strony, Control.Parallel.Strategies są zdefiniowane głównie pod względem Traversable. Biblioteka wektorowa nie zapewnia tych wystąpień.

Minimalna pełna definicja Traversable t powinien również określić Foldable i

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

nie widzę jak sequenceA można zdefiniować dla Data.Vector.Unboxed.Vector. Jakie jest najlepsze podejście do pisania kodu równoległego z nieskrytymi wektorami? Zdefiniowanie niektórych nowych strategii ad hoc, takich jak evalVector lub jawnie lub przy użyciu zwykłego Data.Array zamiast wektorów?

P.S. Plain Array s są parallelizable bez problemów: https://gist.github.com/701888

Answer 1

To praca Hack dla parVector ale ten pracował dla mnie:

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 

i działa ten kod:

[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 

Kiedy uruchomić kod z Integer zamiast Int w wpisz podpis:

[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 

Skała!

EDIT: I to rozwiązanie, które jest nieco bliżej swojej wcześniejszej próbie jest czystsze (nie używać funkcji z trzech oddzielnych modułów) i działa świetnie:

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) 

rzeczy do nauczenia się z tego rozwiązania:

1. używa Eval monady, które jest ścisłe, więc jesteśmy pewni iskra wszystko (w porównaniu do owijania rzeczy w let i pamiętając, aby korzystać z wzorców Wybuchu).
2. W przeciwieństwie do proponowanego wprowadzenia go (a) nie ma wybudować nowy wektor, który jest kosztowny (b) evalChunk siły oceny każdego elementu przy użyciu rpar i rdeepseq (nie wierzę rpar vec siły któregokolwiek z elementów VECTOR) .
3. Wbrew mojej opinii slice przyjmuje indeks początkowy i długość, a nie indeks początkowy i końcowy. Ups!
4. Nadal musimy zaimportować Control.DeepSeq (NFData), ale wysłałem listę bibliotek na adres e-mail, aby spróbować rozwiązać ten problem.

Wydajność jest podobna do pierwszego rozwiązania parVector, więc nie będę publikować liczb.

Answer 2

1) Jak zapewne wiecie, vector jest produktem pracy DPH który okazał trudniejsze niż naukowców początkowo spodziewano.

2) Wektory bez opakowania nie mogą podzielić pracy poszczególnych elementów na wiele procesorów.

3) Byłbym dużo bardziej obiecujący dla wektorów w pudełkach. Coś jak:

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

A może uda ci się uniknąć tworzenia listy i używania parlist. Myślę, że wystarczy przypisać części tablicy. Poniższy kod jest prawdopodobnie uszkodzony, ale koncepcja tworzenia własnego parVector przy użyciu rnf i dzielenia wektora na pół, aż będzie to pojedynczy element (lub jakiś przestrajalny rozmiar elementów) powinien działać.

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