haskell - 如何在 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'正确吗？我想既然需要完成所有计算才能得到结果，我应该强制评估。

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

• 还有哪些其他策略可以应用于此问题？此外，仅使用 par 和 seq 原语进行并行化的任何可能性。

Answer 1

好吧，这次我们使用 REPA(REgular Parallel Arrays)并将其与 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

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