如何在此示例中添加并行计算？

Question

我有一种算法，可以在给定段上同步计算某个积分。我想使用Control.Parallel库，或者par :: a -> b -> b将并行计算添加到此算法。我怎样才能做到这一点？

integrate :: (Double -> Double) -> Double -> Double -> Double
integrate f a b =
  let
    step     = (b - a) / 1000
    segments = [a + x * step | x <- [0..999]]
    area x   = step * (f x + f (x + step)) / 2
  in sum $ map area segments

Answer 1

从外观上，您试图f从b到a使用梯形规则来近似该区域上函数的积分。您尝试并行化代码是正确的，但是尝试有两个问题：

• 首先，您需要一个偷工作的调度程序才能获得任何好处，因为par这不太可能使您加速
• 其次，每个中间点的实现方式f(x)都要计算两次，除了边界点f(a)和f(b)

不久之前，我需要此功能，因此我将其添加到massiv库中：方便地trapezoidRule解决了上述两个问题，并避免了使用列表。

这是一个开箱即用的解决方案，但是它不会自动并行化计算，因为只计算了数组的一个元素（它被设计用来估计许多区域的积分）

integrate' :: (Double -> Double) -> Double -> Double -> Double
integrate' f a b = trapezoidRule Seq P (\scale x -> f (scale x)) a d (Sz1 1) n ! 0
  where
    n = 1000
    d = b - a

作为健全性检查：

?> integrate (\x -> x * x) 10 20 -- implementation from the question
2333.3335
?> integrate' (\x -> x * x) 10 20
2333.3335

这是一个将执行自动并行化并避免冗余评估的解决方案：

integrateA :: Int -> (Double -> Double) -> Double -> Double -> Double
integrateA n f a b =
  let step = (b - a) / fromIntegral n
      sz = size segments - 1
      segments = computeAs P $ A.map f (enumFromStepN Par a step (Sz (n + 1)))
      area y0 y1 = step * (y0 + y1) / 2
      areas = A.zipWith area (extract' 0 sz segments) (extract' 1 sz segments)
   in A.sum areas

由于列表融合，在您的解决方案使用列表的情况下，将不会进行分配，因此，对于简单的情况，它将非常快。在上述解决方案中，将n+1分配大小数组以促进共享并避免双重功能评估。由于调度不是免费的，因此调度也会带来额外的成本。但是最后，对于真正昂贵的功能和非常大的功能，n可以在四核处理器上加快〜x3倍的速度。

以下是将高斯函数与集成的一些基准n = 100000：

benchmarking Gaussian1D/list
time                 3.657 ms   (3.623 ms .. 3.687 ms)
                     0.999 R²   (0.998 R² .. 1.000 R²)
mean                 3.627 ms   (3.604 ms .. 3.658 ms)
std dev              80.50 ?s   (63.62 ?s .. 115.4 ?s)

benchmarking Gaussian1D/array Seq
time                 3.408 ms   (3.304 ms .. 3.523 ms)
                     0.987 R²   (0.979 R² .. 0.994 R²)
mean                 3.670 ms   (3.578 ms .. 3.839 ms)
std dev              408.0 ?s   (293.8 ?s .. 627.6 ?s)
variance introduced by outliers: 69% (severely inflated)

benchmarking Gaussian1D/array Par
time                 1.340 ms   (1.286 ms .. 1.393 ms)
                     0.980 R²   (0.967 R² .. 0.989 R²)
mean                 1.393 ms   (1.328 ms .. 1.485 ms)
std dev              263.3 ?s   (160.1 ?s .. 385.6 ?s)
variance introduced by outliers: 90% (severely inflated)

旁注建议。切换到辛普森法则将为您提供更好的近似值。可以在massiv;）中实现

编辑

这是一个很有趣的问题，我决定看看在没有任何数组分配的情况下实现它会花费什么。这是我想出的：

?> integrate (\x -> x * x) 10 20 -- implementation from the question
2333.3335
?> integrate' (\x -> x * x) 10 20
2333.3335

上面的方法在常量内存中运行，因为确实创建的几个数组不是由内存支持的实际数组，而是延迟数组。折叠累加器周围有一些技巧，我们可以共享结果，从而避免双重功能评估。这导致惊人的速度：

benchmarking Gaussian1D/array Seq no-alloc
time                 1.788 ms   (1.777 ms .. 1.799 ms)
                     1.000 R²   (0.999 R² .. 1.000 R²)
mean                 1.787 ms   (1.781 ms .. 1.795 ms)
std dev              23.85 ?s   (17.19 ?s .. 31.96 ?s)

上述方法的缺点是它不容易并行化，但并非不可能。拥抱自己，这是一种怪兽，可以在8种功能上运行（硬编码，在我的情况下为4个具有超线程的内核）：

-- | Will not produce correct results if `n` is not divisible by 8
integrateN8 :: Int -> (Double -> Double) -> Double -> Double -> Double
integrateN8 n f a b =
  let k = 8
      n' = n `div` k
      step = (b - a) / fromIntegral n
      segments =
        makeArrayR D (ParN (fromIntegral k)) (Sz1 k) $ \i ->
          let start = a + step * fromIntegral n' * fromIntegral i + step
           in (f start, A.map f (enumFromStepN Seq (start + step) step (Sz (n' - 1))))
      area y0 y1 = step * (y0 + y1) / 2
      sumWith (acc, y0) y1 =
        let acc' = acc + area y0 y1
         in acc' `seq` (acc', y1)
      partialResults =
        computeAs U $ A.map (\(y0, arr) -> (y0, A.foldlS sumWith (0, y0) arr)) segments
      combine (acc, y0) (y1, (acci, yn)) =
        let acc' = acc + acci + area y0 y1
         in acc' `seq` (acc', yn)
   in fst $ foldlS combine (0, f a) partialResults

分配的唯一实数数组是用于保存的数组partialResults，共有16个Double元素。速度提升并不那么剧烈，但是仍然存在：

benchmarking Gaussian1D/array Par no-alloc
time                 960.1 ?s   (914.3 ?s .. 1.020 ms)
                     0.968 R²   (0.944 R² .. 0.990 R²)
mean                 931.8 ?s   (900.8 ?s .. 976.3 ?s)
std dev              129.2 ?s   (84.20 ?s .. 198.8 ?s)
variance introduced by outliers: 84% (severely inflated)