Параллельная карта Haskell с `par` и` pseq` - PullRequest
Новая
       28

Параллельная карта Haskell с `par` и` pseq`

0 голосов
/ 05 мая 2019

Я провожу некоторые эксперименты с параллелизмом в Хаскеле. Часть этого - проверка различий между Стратегиями и обычными комбинаторами par и pseq.

Я создал такую ​​функцию: 

parMap :: NFData b => (a -> b) -> [a] -> [b]
parMap _ [] = []
parMap f (a:as) =
  let v = f a
      vs = parMap f as
  in rnf v `par` vs `pseq` v : vs

Я пытаюсь достичь параллелизма с как можно меньшим количеством библиотек (следовательно, без стратегий, без пар) и с небольшим уровнем абстракции, как у Haskell.

С помощью этой функции я пытаюсь выполнить матрично-матричное умножение с помощью одной из этих двух функций: 

matmultListPar :: (Num a, NFData a) => [[a]] -> [[a]] -> [[a]]
matmultListPar a b = parMap multiplyRowByEachColumn a
  where multiplyRowByEachColumn r = map (\c -> sum . zipWith (*) r $ c) $ b'
        b' = transpose b

matmultListParChunks :: (Num a, NFData a) => Int -> [[a]] -> [[a]] -> [[a]]
matmultListParChunks size a b
  = let
        chunks = toChunks size a
        b' = transpose b
    in concat $ parMap (flip matmultList $ b) chunks

matmultList определяется следующим образом: 

matmultList :: (Num a) => [[a]] -> [[a]] -> [[a]]
matmultList a b = fmap multiplyRowByEachColumn a
  where multiplyRowByEachColumn r = fmap (\c -> sum $ zipWith (*) r c) $ b'
        b' = transpose b

И toChunks: 

toChunks :: Int -> [a] -> [[a]]
toChunks _ [] = []
toChunks size list
  = let (i, f) = splitAt size list
    in i : (toChunks size f)

Просто для наглядности - матрица хранится в мажорной строке.

Моя проблема и, следовательно, вопросы:

  1. При применении стратегии parList rdeepseq к полному matmultList я получаю почти двукратное ускорение на двух ядрах. С моим parMap я получаю практически полное ускорение.

  2. Проверка статистики искр с помощью переключателя -s для RTS Я вижу, что большинство искр GC'd для parMap (при конвертации для стратегии).

  3. Как вы можете догадаться, при моем parMap (измеряется с помощью criterion тестов) параллельное ускорение не достигается, в то время как по стратегии

При проверке кода библиотек на Haskell я заметил, что комбинатор par использует функцию par# для запуска, в то время как стратегии используют что-то вроде spark# (я больше не могу его найти, поэтому могу ошибаться).

Мне нужно rnf в parMap, так как a может быть [Double], поэтому всплеска на WHNF недостаточно (я также экспериментировал с force в разных местах).

Недостаток ускорения вызван моей неправильной реализацией, слишком мелкими вычислениями (искры GC) или различиями между par и стратегиями? Или что-то еще целиком? Как добиться ускорения с par и pseq?

...