如何使用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

我不认为列表是正确的数据类型.因为它只是一个链表,所以必须按顺序访问数据.虽然您可以并行评估项目,但在减少步骤中您将无法获得太多收益.如果你真的需要一个List,我认为最好的功能就是

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

或者可能

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

如果缩减步骤很复杂,您可以通过细分列表获得收益,如下所示:

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)

我冒昧地假设你的数据是Monoidmempty,如果这是不可能的,你可以用你自己的空类型替换mempty,或者更糟糕的情况下使用foldl1'.

这里有两个运营商Control.Parallel.Strategies在使用.在parList评估了平行列表中的所有项目.之后,chunkList将列表分成1000个元素的块.然后,这些块中的每一个都被并行减少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)

根据工作的确切分配方式,其中一个可能比其他工作更有效.

如果您可以使用对索引具有良好支持的数据结构(数组,向量,映射等),那么您可以为缩减步骤执行二进制细分,这可能会更好.