Как мне написать параллельное сокращение, используя стратегии в Haskell?

Question

В высокопроизводительных вычислениях суммы, продукты и т. Д. Часто рассчитываются с использованием «параллельного сокращения», которое занимает n элементов и завершается за O (log n ) времени (с учетомдостаточно параллелизма).В Haskell мы обычно используем fold для такого рода вычислений, но время оценки всегда линейно по длине списка.

Data Parallel Haskell имеет кое-что встроенное, нокак насчет общей структуры списка?Можем ли мы сделать это с Control.Parallel.Strategies?

Итак, предполагая, что f является ассоциативным, как мы пишем

parFold :: (a -> a -> a) -> [a] -> a

, так что parFold f xs нужно тольковремя логарифмическое в length xs?

Answer 1

Я не думаю, что список является правильным типом данных для этого. Поскольку это просто связанный список, данные обязательно будут доступны последовательно. Хотя вы можете оценивать предметы параллельно, вы не сильно выиграете на этапе сокращения. Если вам действительно нужен список, я думаю, что лучшая функция будет просто

parFold f = foldl1' f . withStrategy (parList rseq)

или, может быть,

parFold f = foldl1' f . withStrategy (parBuffer 5 rseq)

Если шаг сокращения сложен, вы можете получить выигрыш, разделив список следующим образом:

parReduce f = foldl' f mempty . reducedList . chunkList . withStrategy (parList rseq)
 where
  chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls
  reducedList = parMap rseq (foldl' f mempty)

Я позволил себе предположить, что ваши данные равны Monoid для mempty, если это невозможно, вы можете либо заменить mempty своим собственным пустым типом, либо использовать в худшем случае foldl1'.

Здесь используются два оператора из Control.Parallel.Strategies. parList оценивает все элементы списка параллельно. После этого chunkList делит список на куски по 1000 элементов. Каждый из этих кусков затем параллельно уменьшается на parMap.

Вы также можете попробовать

parReduce2 f = foldl' f mempty . reducedList . chunkList
 where
  chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls
  reducedList = parMap rseq (foldl' f mempty)

В зависимости от того, как именно распределяется работа, один из них может быть более эффективным, чем другие.

Если вы можете использовать структуру данных, которая имеет хорошую поддержку для индексации (Array, Vector, Map и т. Д.), То вы можете сделать двоичные подразделения для этапа сокращения, который, вероятно, будет лучше в целом.

Answer 2

Не уверен, что должна делать ваша функция parFold.Если предполагается, что это параллельная версия foldr или foldl, я думаю, что ее определение неверно.

parFold :: (a -> a -> a) -> [a] -> a

// fold right in haskell (takes 3 arguments)
foldr :: (a -> b -> b) -> b -> [a] -> b

Fold применяет одну и ту же функцию к каждому элементу списка и накапливает результат каждого приложения.Я полагаю, что для его параллельной версии потребуется, чтобы приложение функции к элементам выполнялось параллельно - немного похоже на то, что делает parList.

    par_foldr :: (NFData a, NFData b) => (a -> b -> b) -> b -> [a] -> b
    par_foldr f z [] = z
    par_foldr f z (x:xs) = res `using` \ _ -> rseq x' `par` rdeepseq res
                       where x' = par_foldr f z xs
                             res = x `f` x'

Answer 3

Это похоже на хорошее начало:

parFold :: (a -> a -> a) -> [a] -> a
parFold f = go
  where
  strategy = parList rseq

  go [x] = x
  go xs = go (reduce xs `using` strategy)

  reduce (x:y:xs) = f x y : reduce xs
  reduce list     = list   -- empty or singleton list

Это работает, но параллелизм не так уж велик.Замена parList на что-то вроде parListChunks 1000 немного помогает, но на 8-ядерном компьютере скорость все еще ограничена до 1,5x.