Как написать параллельный код с векторами на Haskell?

Question

Одна рука в Haskell Vector a представляется предпочтительным типом для использования в качестве массива чисел.Существует даже (неполное) Vector Tutorial .

С другой стороны, Control.Parallel.Strategies определены в основном в терминах Traversable.Векторная библиотека не предоставляет эти экземпляры.

Минимальное полное определение Traversable t должно также определять Foldable и

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

Я не понимаю, как sequenceA может бытьопределено для Data.Vector.Unboxed.Vector.Итак, каков наилучший подход к написанию параллельного кода с распакованными векторами?Определяя некоторые новые специальные стратегии, такие как evalVector, или явно используя par и pseq, или используя простые Data.Array вместо векторов?

PS Обычные Array s распараллеливаются без проблем: https://gist.github.com/701888

Answer 1

Это хакерская работа для parVector, но у меня это сработало:

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

И запуск этого кода:

[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

Когда я запускаю код вместо IntegerInt в сигнатуре типа:

[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!

РЕДАКТИРОВАТЬ: И решение, которое немного ближе к вашей предыдущей попытке, является более чистым (оно не использует функции изтри отдельных модуля) и прекрасно работает:

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)

Что можно извлечь из этого решения:

1. Используется монада Eval, которая является строгой, поэтому мы обязательнозажечь все (по сравнению с обертыванием вещей в let и не забывая использовать шаблоны взрыва).
2. Вопреки предложенной вами реализации, он (a) не создает новый вектор, который является дорогостоящим (b) evalChunk форсирует оценку каждого элемента, используя rpar и rdeepseq (я не верю, что rpar vec форсирует любой из элементов вектора).
3. Вопреки моему убеждению, slice принимает начальный индекс идлина, а не начальный и конечный индексы.Ой!
4. Нам все еще нужно импортировать Control.DeepSeq (NFData), но я отправил список библиотек по электронной почте, чтобы попытаться решить эту проблему.

Производительность кажется похожей на первую parVector решение в этом ответе, поэтому я не буду публиковать номера.

Answer 2

1) Как вы, вероятно, знаете, vector является продуктом работы DPH , которая оказалась тяжелее, чем первоначально ожидали исследователи.

2) Распакованные векторы не могут разделить работу для отдельных элементов между несколькими процессорами.

3) Я бы гораздо больше надеялся на штучные векторы. Что-то вроде:

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

Или, может быть, вы можете избежать составления списка и использования parlist. Я думаю, что достаточно просто присвоить части массива. Приведенный ниже код, скорее всего, не работает, но концепция создания собственного parVector с использованием rnf и деления вектора пополам до тех пор, пока он не станет единичным элементом (или некоторым настраиваемым размером фрагментов), должна работать.

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