haskell - Haskell 中的并行 "Folding"

Question

我有一个类型如下的函数:

union :: a -> a -> a

并且a具有可加性属性。所以我们可以把union看作(+)

的一个版本

假设我们有[a]，并且想要执行并行“折叠”，对于非并行折叠我们只能这样做:

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

您需要将您的联合推广到任何关联二元运算符⊕，使得 (a ⊕ b) ⊕ c == a ⊕ (b ⊕ c)。如果同时你甚至有一个相对于 ⊕ 呈中性的单位元素，那么你就有了一个幺半群。

关联性的重要方面是，您可以将列表中的连续元素 block 任意分组，并以任何顺序 ⊕ 它们，因为 a ⊕ (b ⊕ (c ⊕ d)) == (a ⊕ b) ⊕ ( c ⊕ d) - 每个括号可以并行计算；那么你需要“减少”所有括号的“总和”，并且你已经对 map 减少进行了排序。

为了使这种并行化有意义，您需要分块操作比 ⊕ 更快 - 否则，顺序执行 ⊕ 比分块更好。其中一种情况是当您有一个随机访问“列表”时 - 例如，一个数组。 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 没有任何意义。