如何使用Haskell向量编写并行代码？

Question

一方面，在Haskell编程中，Vector a似乎是首选的数字数组类型。甚至有一个（不完整的）向量教程。

另一方面，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)

我不知道如何为Data.Vector.Unboxed.Vector定义sequenceA。那么，使用未装箱向量编写并行代码的最佳方法是什么？定义一些新的特定策略，例如evalVector，显式地使用par和pseq或者使用纯Data.Array而不是向量吗？

附注：普通数组可以无问题地并行化：https://gist.github.com/701888

- sastanin

---

你对DPH的成果有些焦急了吗？ - Thomas M. DuBuisson

有点吧。我想尝试在Haskell中编写数字代码，但还不知道应该使用什么。 - sastanin

我认为你的parVector版本不会起作用：rseq不会评估任何元素（它只是WHNF），而V.concat是不必要的O(n)操作 - 我们正在尝试强制计算元素，没有必要构造新向量。 - Thomas M. DuBuisson

另外，vLen - half 可能应该是 vLen - 1，但这也不完全正确，因为它会在我的计算机上出现段错误。 - Thomas M. DuBuisson

我将它上传为 vector-strategies 包，因为它对广大用户来说非常有用，但 Roman 不想将其添加到 Vector 的构建依赖项中（可以理解）。 - Thomas M. DuBuisson

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

当我在类型签名中使用 Integer 而不是 Int 运行代码时：

[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

加油！

编辑：一个更接近你之前尝试的解决方案更为简洁（它不使用来自三个独立模块的函数），而且效果很好：

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 Monad，它是严格的，因此我们确保激发所有内容（与用let包装内容并记住使用bang模式相比）。

2.与您提出的实现相反，它（a）不构造新向量，这是昂贵的（b）evalChunk使用rpar和rdeepseq强制评估每个元素（我不认为rpar vec会强制执行任何向量的元素）。

3.与我的信念相反，slice需要一个起始索引和长度，而不是起始和结束索引。哎呀！

4.我们仍然需要导入Control.DeepSeq（NFData），但我已经向库列表发送了电子邮件以尝试解决该问题。

性能看起来类似于这个答案中的第一个parVector解决方案，因此我不会发布数字。

- Thomas M. DuBuisson

---

请注意，Tom的库现在已经在Hackage上了：http://hackage.haskell.org/package/vector-strategies - Don Stewart

Answer 2

1) 你可能知道，vector是DPH工作的产物，它比研究人员最初预期的更加困难。

2) 未经处理的向量无法将个别元素的工作分配给多个CPU。

3) 对于装箱向量，我会更有希望。例如：

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

或许你可以避免构建列表并使用parlist。我认为只需要分配数组的部分就足够了。下面的代码可能有问题，但是使用rnf制作自己的parVector，并将向量分成一半，直到它成为单个元素（或某个可调整的块大小的元素）的概念应该可以工作。

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

- Thomas M. DuBuisson

---

Tom，谢谢你的想法。我会尝试一下。我的理解是，即使是这个 parVector 也不能在未装箱的向量上工作，是吗？ - sastanin

好的。也许 Roman（向量的作者，有时在这里发布帖子）会进来澄清一下，但是未装箱的数据不能是延迟计算（不能是thunk）。强制未装箱向量的任何元素都会强制执行其他元素，并且任何并行性必须在Vector包内完成（如果可能的话）。 - Thomas M. DuBuisson

我尝试了parVector策略，虽然我不得不重写它以便与更新的parallel一起构建（请参见编辑后的问题）。不幸的是，它并没有提供任何加速。 - sastanin