Как написать задачу с вложенным циклом, используя параллельные стратегии в 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

Надеюсь, вам понравится это сравнение.

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, сгенерированный код точно такой же.

Для оценки списка в сегментах вы можете просто использовать стратегию разбиения на фрагменты, как указано выше. Однако объем работы, представляемой каждым чанком, может сильно отличаться, поэтому вы можете попытаться выровнять его, сделав более крупные чанки для конца списка. Кроме того, я не думаю, что здесь есть много возможностей для улучшения.