如何在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

我的问题是：

• 在这里使用折叠是对的吗？我想，由于所有的计算都需要完成才能得到结果，我应该强制求值。
• 是否有更好的使用分段的方法？在这个问题中，我可以利用哪些常见的模式？

，

• ，还有什么其他的策略可以应用于这个问题？此外，只使用par和seq原语并行化的任何可能性.

Answer 1

好，让我们这次使用REPA (REgular并行数组)，并将其与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

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

Answer 2

下面是如何将您的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，生成的代码都是完全相同的。

为了对列表进行分段评估，您可以使用上面所示的分块策略。然而，每个块所代表的工作量可能相差很大，因此您可以尝试通过为列表的末尾创建更大的块来平衡它。除此之外，我认为这里没有多少改进的余地。