Haskell parMap и параллелизм

У меня есть реализация игры жизни Конвея. Я хочу ускорить его, если это возможно, используя параллелизм.

life :: [(Int, Int)] -> [(Int, Int)]
life cells = map snd . filter rules . freq $ concatMap neighbours cells
    where rules (n, c) = n == 3 || (n == 2 && c `elem` cells)
          freq = map (length &&& head) . group . sort

parLife :: [(Int, Int)] -> [(Int, Int)]
parLife cells = parMap rseq snd . filter rules . freq . concat $ parMap rseq neighbours cells
    where rules (n, c) = n == 3 || (n == 2 && c `elem` cells)
          freq = map (length &&& head) . group . sort

neigbours :: (Int, Int) -> [(Int, Int)]
neighbours (x, y) = [(x + dx, y + dy) | dx <- [-1..1], dy <- [-1..1], dx /= 0 || dy /= 0]

при профилировании на соседей приходится 6,3% затраченного времени, так что, пока маленький, я ожидал заметного ускорения от параллельного сопоставления.

Я тестировал с помощью простой функции

main = print $ last $ take 200 $ iterate life fPent
    where fPent = [(1, 2), (2, 2), (2, 1), (2, 3), (3, 3)]

и скомпилировал параллельную версию как

ghc --make -O2 -threaded life.hs

и запускал как

./life +RTS -N3

получается, что параллельная версия медленнее. Я неправильно использую parMap? это даже случай, когда можно использовать параллелизм?


parallel-processing haskell conways-game-of-life
person cdk    schedule 01.09.2012    source источник
comment
Во-первых, у вас в компьютере есть хотя бы 3 ядра? Во-вторых, параллелизм всегда сопряжен с некоторыми накладными расходами, поэтому, если работа, выполняемая каждым потоком, очень мала, дополнительные накладные расходы перевесят любое ускорение.   -  person huon    schedule 01.09.2012
comment
у меня i5-2500k, так что точно доступно до 4 ядер   -  person cdk    schedule 01.09.2012
comment
Обратите внимание, что вы можете получить гораздо большее ускорение от улучшения алгоритма, чем от распараллеливания. Основная часть времени проводится в sort и elem. Используя тот факт, что список ячеек отсортирован (и изменив fPent так, чтобы он был отсортирован), вы можете сократить время примерно вдвое.   -  person Daniel Fischer    schedule 01.09.2012
comment
@DanielFischer: список не обязательно отсортирован, если отсортирован fPent. freq принимает список каждой ячейки, соседней с живой ячейкой, в качестве входных данных, и одна и та же ячейка может быть соседней со многими разными живыми ячейками и отображаться разбросанными по всему списку. Если бы был способ найти общее количество вхождений каждого уникального элемента в списке быстрее, чем сортировка, это действительно улучшило бы алгоритм.   -  person cdk    schedule 08.09.2012
comment
Крис, вы сортируете список на шаге: freq = map (length &&& head) . group . sort, поэтому cells для следующего поколения всегда сортируются.   -  person Daniel Fischer    schedule 08.09.2012

Ответы (1)


arrow_upward
2
arrow_downward

Я не думаю, что вы измеряете правильно. Ваш parLife действительно немного быстрее, чем life. Фактически, на моей машине (Phenom X4, 4 ядра) первое занимает всего около 92,5% времени, которое занимает второе, что, учитывая, что вы говорите, что ожидаете улучшения только на 6%, довольно хорошо.

Какова ваша установка для бенчмаркинга? Пробовали ли вы использовать criterion? Вот что я сделал:

import Criterion
import Criterion.Main

-- your code, minus main

runGame f n = last $ take n $ iterate f fPent
    where fPent = [(1, 2), (2, 2), (2, 1), (2, 3), (3, 3)]

main = defaultMain
    [ bench "No parallelism 200" $ whnf (runGame life)    200
    , bench "Parallelism 200"    $ whnf (runGame parLife) 200 ]

Скомпилировано с ghc --make -O2 -o bench и запущено с ./bench -o bencht.hmtl +RTS -N3.

Подробный результат отчета.

person Aleksandar Dimitrov    schedule 01.09.2012
comment
Хм, странно. Я также получаю результат, что parLife быстрее по критерию, но когда я запускаю вещь в автономном режиме, parLife постоянно значительно медленнее, чем life. - person Daniel Fischer; 01.09.2012
comment
Ах, только с потоковой средой выполнения, а не без потоковой! - person Daniel Fischer; 01.09.2012
comment
Я думаю, что это как-то связано с долговечностью процесса… Т.е. инициализация пула потоков и т. д. обходится дороже, чем (по общему признанию, незначительные) выгоды, которые мы получаем от распараллеливания. - person Aleksandar Dimitrov; 01.09.2012
comment
Возможно. Но я выполнил 500 итераций, чтобы получить более надежные тайминги. Этого достаточно, чтобы инициализация пула потоков и т. д. не имела значения. Вероятно, многопоточная среда выполнения имеет более высокие накладные расходы на искрообразование. - person Daniel Fischer; 01.09.2012
comment
О, но подождите! Безпоточная среда выполнения даже не поддерживает параллелизм, никаких искр! - person Daniel Fischer; 01.09.2012
comment
Ага. Возможно, стоит запустить его через thread-scope, чтобы увидеть, что именно происходит. Но, как вы предложили выше, есть более очевидные моменты для ускорения этого кода. - person Aleksandar Dimitrov; 01.09.2012