如何在Haskell中使用并行策略编写嵌套循环问题

Question

我正在尝试使用并行策略，想知道以下代码是否正确。Java 代码：

    double x = 0.0;
    double[] arr = new double[2000];

    for (int i = 0; i < arr.length; i++) 
        arr[i] = i;

    for (int i = 0; i < arr.length; i++) {
        x += arr[i] * 5;

        for (int j = i + 1; j < arr.length; j++)
            x -= arr[j] * 3;
    }

使用并行策略计算结果的Haskell程序：

    n = 2000
    ns = [0..n-1]

    segments = chunk 100 ns

    chunk n [] = []
    chunk n xs = ys : chunk n zs
      where (ys,zs) = splitAt n xs

    parCompute = foldl' (+) 0 (map (\ts -> compute ts) segments `using` parList rdeepseq)

    compute ts = foldl' addfunc 0 ts
        where
            addfunc acc i = (acc + x) - (foldl' minusfunc 0 [(i+1)..(n-1)])
                where
                    x = (ns!!i) * 5
                    minusfunc acc' j = (acc' + x')
                        where
                            x' = (ns!!j) * 3

    main = print parCompute

我的问题是：

• 在这里使用foldl'是否正确？我认为由于需要执行所有计算才能得出结果，所以应该强制评估。

• 有没有更好的方法来使用segments？在这个问题中存在哪些常见模式可以利用？

• 还有什么其他策略可以应用于这个问题？另外，是否有可能只使用par和seq原语来并行化。

- vis

---

样式注释：嵌套的where语句很丑陋。 - rampion

我认为这些代码片段并不等价。代码“x -= arr[j] * 3”应用于列表中位置“i”之后的所有项，但在Haskell代码中，等价的代码仅应用于本地块，而不是所有超过位置“i”的值。或者我可能读错了。 - Tim Perry

@Tim：它确实给出了相同的答案。我已经将Haskell的结果与Java进行了比对。 - vis

在这种情况下，我很高兴我错了。 - Tim Perry

Answer 1

以下是我如何将您的Java程序翻译为并行的Haskell程序：

parCompute ts = sum (computes `using` parListChunk 100 rseq)
  where 
    computes  = zipWith f ts (tail (tails ts))
    f t tls   = 5 * t - 3 * sum tls

首先，引入严格性在这里是一个好主意。另一方面，GHC也足够聪明，能够发现这一点！实际上，无论您使用foldl、foldl'还是简单地使用sum，生成的代码都是完全相同的。

对于按段评估列表，您可以简单地使用如上所示的分块策略。每个块所代表的工作量可能会有很大的差异，因此您可以尝试通过为列表末尾制作更大的块来平衡它们。除此之外，我认为在这里没有太多改进的空间。

- Peter Wortmann

---

谢谢您的回复。您的解决方案看起来很好，也很有用，但我对于foldl、foldl'生成的代码是否相同还不太确定。foldl'会在每次函数应用后强制完全评估累积结果。在某些情况下，它比使用foldl更快，但不确定生成的代码以何种方式相同。 - vis

Answer 2

好的，这次我们来使用REPA（正则并行数组）并将其与parListChunk方法进行比较（因为Java示例使用的是数组而不是列表）：

module Main where

import Control.Parallel.Strategies
import Data.List (tails)
import System.Environment (getArgs)
import qualified Data.Array.Repa as R
import qualified Data.Array.Repa.Shape as RS

chunksize = 100

parListCompute :: [Int] -> [Int]
parListCompute ts = (computes `using` parListChunk chunksize rseq)
  where
    computes = zipWith f ts (tail (tails ts))
    f t tls  = 5 * t - 3 * sum tls

parRepaCompute :: R.Array R.DIM1 Int -> R.Array R.DIM1 Int
parRepaCompute arr = R.force $ computes
  where
    computes    = R.map f arr
    f x         = 5*x - 3*(sumRest (x+1) 0)
    sumRest x acc | x > (RS.size . R.extent $ arr) = acc
                  | otherwise                      = sumRest (x+1) (acc+x)

main = do
  (s:_) <- getArgs
  case s of
    "1" -> putStrLn . show .sum $ parListCompute l
    "2" -> putStrLn . show . R.sum $ parRepaCompute r
  where l = [1..70000]
        r = R.fromList (R.Z R.:. (length l)) l

这里是结果：

~/haskell$ ghc --make nestloop.hs -O2 -rtsopts -threaded 
[1 of 1] Compiling Main             ( nestloop.hs, nestloop.o )
Linking nestloop ...
haskell$ time ./nestloop 1 +RTS -N4
-342987749755000

real    0m5.115s
user    0m19.870s
sys     0m0.170s
~/haskell$ time ./nestloop 2 +RTS -N4
[-342987749755000]

real    0m1.658s
user    0m3.670s
sys     0m0.070s

我希望你会喜欢这个比较。

- aycanirican

---

谢谢您的比较，这确实很有用。在选择最佳答案之前，我会等待看看是否有其他选择。 - vis