在Haskell中并行"折叠"

Question

我有一个类型的功能如下:

union :: a -> a -> a

并a具有可加性属性.所以我们可以union视为一个版本(+)

比方说,我们有[a]并且想要执行并行"folding",对于非并行折叠,我们只能这样做:

foldl1' union [a]

但是如何并行执行呢？我可以证明Num价值和(+)功能的问题.

例如,我们有一个列表[1,2,3,4,5,6],(+) 并且我们应该分开

[1,2,3] (+) [4,5,6]
[1,2] (+) [3] (+) [4,5] (+) [6]
([1] (+) [2]) (+) ([3] (+) [4]) (+) ([5] (+) [6])

然后(+)我们想要并行执行每个操作,并结合起来回答

[3] (+) [7] (+) [11] = 21

请注意,由于可a加性,我们拆分列表或以任何顺序执行操作.

有没有办法使用任何标准库？

Answer 1

您需要将您union的任何关联二元运算符概括为⊕,使得(a⊕b)⊕c==a⊕(b⊕c).如果同时你甚至有一个相对于neutral中性的单位元素,你就有一个幺半群.

关联性的一个重要方面是你可以在列表中任意分组连续元素的块,并且它们可以按任何顺序排列,因为a⊕(b⊕(c⊕d))==(a⊕b)⊕(c⊕d ) - 每个支架可以并行计算; 那么你需要"减少"所有括号的"总和",并且你已经对map-reduce进行了排序.

为了使这种并行化有意义,你需要比⊕更快的分块操作 - 否则,顺序执行is比分块更好.一个这样的情况是当你有一个随机访问"列表" - 比如一个数组.Data.Array.Repa具有大量的并行折叠功能.

如果你正在考虑自己实现一个实践,你需要选择一个好的复杂功能⊕这样的好处将显示出来.

例如:

import Control.Parallel
import Data.List

pfold :: (Num a, Enum a) => (a -> a -> a) -> [a] -> a
pfold _ [x] = x
pfold mappend xs  = (ys `par` zs) `pseq` (ys `mappend` zs) where
  len = length xs
  (ys', zs') = splitAt (len `div` 2) xs
  ys = pfold mappend ys'
  zs = pfold mappend zs'

main = print $ pfold (+) [ foldl' (*) 1 [1..x] | x <- [1..5000] ]
  -- need a more complicated computation than (+) of numbers
  -- so we produce a list of products of many numbers

在这里,我故意使用一个mappend只在本地调用的关联操作,以表明它可以用于比一个幺半群更弱的概念 - 只有关联性对并行性很重要; 因为并行性只对非空列表有意义,所以不需要mempty.

ghc -O2 -threaded a.hs
a +RTS -N1 -s

总运行时间为8.78秒,而

a +RTS -N2 -s

在我的双核笔记本电脑上总运行时间为5.89秒.显然,在这台机器上尝试超过-N2没有意义.