Как использовать любой параллелизм в моем параллельном коде на haskell?

Question

Я только что заявил, что работает в полуявном параллелизме haskell с GHC 6.12. Я написал следующий код haskell для параллельного вычисления карты функции fibonnaci по 4 элементам в списке и в то же время карты функции sumEuler по двум элементам.

import Control.Parallel
import Control.Parallel.Strategies

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

mkList :: Int -> [Int]
mkList n = [1..n-1]

relprime :: Int -> Int -> Bool
relprime x y = gcd x y == 1

euler :: Int -> Int
euler n = length (filter (relprime n) (mkList n))

sumEuler :: Int -> Int
sumEuler = sum . (map euler) . mkList

-- parallel initiation of list walk                                                                                                                                    
mapFib :: [Int]
mapFib = map fib [37, 38, 39, 40]

mapEuler :: [Int]
mapEuler = map sumEuler [7600, 7600]

parMapFibEuler :: Int
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler))

-- how to evaluate in whnf form by forcing                                                                                                                                
forceList :: [a] -> ()
forceList [] = ()
forceList (x:xs) = x `pseq` (forceList xs)


main = do putStrLn (" sum : " ++ show parMapFibEuler)

, чтобы улучшить мою программу параллельно, я переписал ее с par и pseq и , заставляющими вызвать принудительную оценку whnf. Моя проблема в том, что, глядя в нить, я не получаю никакого параллелизма. Все хуже, потому что я не набрал ускорение.

Вот почему у меня есть два вопроса

Вопрос 1 Как я могу изменить свой код, чтобы использовать какой-либо параллелизм?

Вопрос 2 Как мне написать свою программу, чтобы использовать стратегии (parMap, parList, rdeepseq и т. Д.)?

Первое улучшение со стратегиями

в соответствии с его вкладом

parMapFibEuler = (mapFib, mapEuler) `using` s `seq` (sum mapFib + sum mapEuler) where
    s = parTuple2 (seqList rseq) (seqList rseq)

параллелизм появляется в потоковой области, но недостаточно для значительного ускорения

Answer 1

Причина, по которой вы не видите здесь никакого параллелизма, заключается в том, что ваша искра была собрана мусором. Запустите программу с +RTS -s и запишите следующую строку:

  SPARKS: 1 (0 converted, 1 pruned)

искра была "подрезана", что означает, что сборщик мусора удаляет ее. В GHC 7 мы внесли изменения в семантику искр, так что искра теперь собирается мусором (GC'd), если на нее не ссылается остальная часть программы; подробности в бумаге "Seq no more" .

Почему искра GC'd в вашем случае? Посмотрите на код:

parMapFibEuler :: Int
parMapFibEuler = (forceList mapFib) `par` (forceList mapEuler `pseq` (sum mapFib + sum mapEuler))

искрой здесь является выражение forkList mapFib. Обратите внимание, что значение этого выражения не требуется остальной части программы; он появляется только в качестве аргумента par. GHC знает, что это не требуется, поэтому он собирает мусор.

Суть недавних изменений в пакете parallel заключалась в том, чтобы вы могли легко избежать этой медвежьей ловушки. Хорошее правило - использовать Control.Parallel.Strategies вместо par и pseq напрямую. Мой предпочтительный способ написать это будет

parMapFibEuler :: Int
parMapFibEuler = runEval $ do
  a <- rpar $ sum mapFib
  b <- rseq $ sum mapEuler
  return (a+b)

но, к сожалению, это не работает с GHC 7.0.2, потому что искра sum mapFib всплывает как статическое выражение (CAF), и среда выполнения не думает, что искры, указывающие на статические выражения, стоит сохранить (Я это исправлю). Конечно, этого не произойдет в реальной программе! Итак, давайте сделаем программу немного более реалистичной и победим оптимизацию CAF:

parMapFibEuler :: Int -> Int
parMapFibEuler n = runEval $ do
  a <- rpar $ sum (take n mapFib)
  b <- rseq $ sum (take n mapEuler)
  return (a+b)

main = do [n] <- fmap (fmap read) getArgs
          putStrLn (" sum : " ++ show (parMapFibEuler n))

Теперь я получаю хороший параллелизм с GHC 7.0.2. Тем не менее, обратите внимание, что комментарии @ John также применимы: как правило, вы хотите искать более детальный параллелизм, чтобы позволить GHC использовать все ваши процессоры.

Answer 2

Ваш параллелизм слишком сложен, чтобы иметь много полезного эффекта. Наибольшая часть работы, которая может быть выполнена эффективно параллельно, находится в sumEuler, поэтому вам нужно добавить свои par аннотации. Попробуйте изменить sumEuler на:

sumEuler :: Int -> Int
sumEuler = sum . (parMap rseq euler) . mkList

parMap от Control.Parallel.Strategies; он выражает карту, которую можно сделать параллельно. Первый аргумент rseq, имеющий тип Strategy a, используется для принудительного вычисления в определенной точке, в противном случае никакая работа не будет выполнена из-за лени. rseq подходит для большинства числовых типов.

Бесполезно добавлять параллелизм к fib здесь, ниже примерно fib 40 недостаточно работы, чтобы это стоило.

Помимо потока, полезно запускать вашу программу с флагом -s. Ищите строку вроде:

SPARKS: 15202 (15195 converted, 0 pruned)

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

Наконец, я думаю, parMapFibEuler лучше записать как:

parMapFibEuler :: Int
parMapFibEuler = sum (mapFib `using` parList rseq) + sum mapEuler

mapEuler просто слишком короток, чтобы здесь можно было с пользой выразить какой-либо параллелизм, тем более что euler уже выполняется параллельно. Я сомневаюсь, что это имеет существенное значение и для mapFib. Если бы списки mapFib и mapEuler были длиннее, параллелизм здесь был бы более полезным. Вместо parList вы можете использовать parBuffer, что хорошо работает для списка потребителей.

Выполнение этих двух изменений сокращает время выполнения с 12 до 8 секунд для меня с GHC 7.0.2.

Answer 3

Прежде всего, я предполагаю, что вы знаете, что ваше fib определение ужасно, и вы просто делаете это, чтобы поиграть с параллельным пакетом.

Вы, похоже, идете на параллелизм на неправильном уровне.Распараллеливание mapFib и mapEuler не даст хорошего ускорения, потому что есть больше работы для вычисления mapFib.Что вы должны сделать, так это вычислить каждый из этих очень дорогих элементов параллельно, что немного более точно, но не слишком:

mapFib :: [Int]
mapFib = parMap rdeepseq fib [37, 38, 39, 40]

mapEuler :: [Int]
mapEuler = parMap  rdeepseq sumEuler [7600, 7600, 7600,7600]

parMapFibEuler :: Int
parMapFibEuler = sum a + sum b
  where
  a = mapFib
  b = mapEuler

Кроме того, я изначально боролся с использованием Control.Parallel.Strategies над Control.Parallel, ноон понравился вам, так как он более читабелен и позволяет избежать проблем, подобных вашей, когда можно ожидать параллелизма и прищуриться на него, чтобы выяснить, почему вы его не получаете.

Наконец, вы всегда должны публиковать, каквы компилируете и как вы запускаете код, который вы ожидаете распараллелить.Например:

$ ghc --make -rtsopts -O2 -threaded so.hs -eventlog -fforce-recomp
[1 of 1] Compiling Main             ( so.hs, so.o )
Linking so ...
$ ./so +RTS -ls -N2
 sum : 299045675

Выход:

Answer 4

Хммм ... Может быть?

((forceList mapFib) `par` (forceList mapEuler)) `pseq` (sum mapFib + sum mapEuler)

т.е. порождает mapFib в фоновом режиме и вычисляет mapEuler и только после этого (mapEuler) делает (+) их сумм. На самом деле, я думаю, вы можете сделать что-то вроде:

parMapFibEuler = a `par` b `pseq` (a+b) where
     a = sum mapFib
     b = sum mapEuler

О Q2: Как я знаю, стратегии - это «стратегии» для объединения структур данных с этими par и seq.
Вы можете написать свой forceList = withStrategy (seqList rseq)
Также вы можете написать свой код как:

parMapFibEuler = (mapFib, mapEuler) `using` s `seq` (sum mapFib + sum mapEuler) where
    s = parTuple2 (seqList rseq) (seqList rseq)

т.е. Стратегия, применяемая к кортежу двух списков, заставит их параллельно проводить оценку, но каждый список будет вынужден оцениваться последовательно.