haskell - 如何使用 Haskell 中的策略编写并行归约？

Question

在高性能计算中，总和、乘积等通常使用“并行缩减”来计算，该“并行缩减”需要 n 个元素并在 O(log n) 时间内完成(给定足够的并行度)。在 Haskell 中，我们通常使用折叠来进行这种计算，但评估时间总是与列表长度成线性关系。

Data Parallel Haskell 内置了一些这样的功能，但是在列表的通用框架中呢？我们可以用 Control.Parallel.Strategies 来做吗？ ?

所以，假设 f是联想的，我们怎么写
parFold :: (a -> a -> a) -> [a] -> a
这样parFold f xs只需要length xs中的时间对数?

Answer 1

我不认为列表是正确的数据类型。因为它只是一个链表，数据必然会被顺序访问。尽管您可以并行评估项目，但在缩减步骤中您不会获得太多 yield 。如果你真的需要一个列表，我认为最好的功能就是

parFold f = foldl1' f . withStrategy (parList rseq)

或者可能

parFold f = foldl1' f . withStrategy (parBuffer 5 rseq)

如果减少步骤很复杂，您可能会通过像这样分割列表来获得 yield :

parReduce f = foldl' f mempty . reducedList . chunkList . withStrategy (parList rseq)
 where
  chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls
  reducedList = parMap rseq (foldl' f mempty)

我冒昧地假设您的数据是 Monoid对于 mempty，如果这是不可能的，你可以用你自己的空类型替换 mempty，或者更糟糕的情况使用 foldl1' .
Control.Parallel.Strategies 中有两个运算符在这里使用。 parList并行评估列表中的所有项目。之后， chunkList将列表分成 1000 个元素的 block 。然后，这些 block 中的每一个都被 parMap 并行减少。 .

你也可以试试

parReduce2 f = foldl' f mempty . reducedList . chunkList
 where
  chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls
  reducedList = parMap rseq (foldl' f mempty)

根据工作的确切分配方式，其中之一可能比其他更有效。

如果您可以使用对索引有良好支持的数据结构(数组、向量、映射等)，那么您可以对归约步骤进行二进制分割，总体上可能会更好。