如何在Haskell中使用策略编写并行约简？

在高性能计算中，通常使用“并行减少”来计算总和，产品等，该“并行减少”需要时间（给定足够的并行性），并且在O（日志n）时间内完成。在Haskell中，我们通常使用折叠来进行这种计算，但评估时间在列表长度上总是线性的。如何在Haskell中使用策略编写并行约简？

数据并行Haskell有一些内置的，但在列表的通用框架呢？我们可以用Control.Parallel.Strategies吗？

因此，假设f是关联的，我们怎么写

parFold :: (a -> a -> a) -> [a] -> a

使parFold f xs只需要在length xs时间对数？

来源

2010-10-26 Chad Scherrer

正如人们已经注意到的，list是递归并行分割的一个糟糕的数据结构。你需要某种二叉树/绳索结构，如Fortress语言：http://labs.oracle.com/projects/plrg/Publications/ICFPAugust2009Steele.pdf – sclv 2010-10-27 00:56:42

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

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)

我已经采取了假设你的数据的自由是mempty一个Monoid，如果无法做到这一点，你可以用自己的空类型更换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)

根据工作究竟是如何分布的，其中之一可能比其他人更有效。

如果您可以使用对索引有很好支持的数据结构（数组，矢量，映射等），那么您可以对缩减步骤执行二进制细分，总体来说可能会更好。

来源

2010-10-26 22:32:01

谢谢，约翰。我喜欢使用foldl'over chunk的想法。但是在每个块减少之后，外部折叠'是连续的，并且其输入可能非常大。什么是表达递归的最佳方式？输入可能是也可能不是列表，但是这应该可以使用策略来表达。 – 2010-10-27 18:11:19

'reducedList'中的'parMap'函数将并行评估所有块。但是，如果您的输入太大以至于您不想一次将所有内容加载到内存中，那么您可以使用laziness和parBuffer。我在'parBuffer'方面取得了非常好的成绩，因为它可以让你利用并行和懒惰。我认为它会工作，如果你使用'reducedList = withStrategy（parBuffer 10 rseq）。地图（foldl'f mempty）'。我认为这比列表的递归更好，因为你避免了多次遍历。 – 2010-10-27 19:01:32

这似乎是一个良好的开端：

parFold :: (a -> a -> a) -> [a] -> a 
parFold f = go 
    where 
    strategy = parList rseq 

    go [x] = x 
    go xs = go (reduce xs `using` strategy) 

    reduce (x:y:xs) = f x y : reduce xs 
    reduce list  = list -- empty or singleton list

它的工作原理，但其并行是没有那么大。用parListChunks 1000之类的东西代替parList会有所帮助，但在8核机器上加速仍然限制在1.5x以下。

来源

2010-10-26 21:42:51

不知道你的parFold函数应该做什么。如果这是一个平行版本的foldr或foldl，我认为它的定义是错误的。

parFold :: (a -> a -> a) -> [a] -> a 

// fold right in haskell (takes 3 arguments) 
foldr :: (a -> b -> b) -> b -> [a] -> b

折叠将相同的功能应用于列表的每个元素并累积每个应用程序的结果。使用它的一个并行版本，我想，将要求功能应用程序的元素并行完成 - 有点像parList做什么。

par_foldr :: (NFData a, NFData b) => (a -> b -> b) -> b -> [a] -> b 
    par_foldr f z [] = z 
    par_foldr f z (x:xs) = res `using` \ _ -> rseq x' `par` rdeepseq res 
         where x' = par_foldr f z xs 
          res = x `f` x'

来源

2011-07-01 00:44:37 vis

如何在Haskell中使用策略编写并行约简？

回答

相关问题