Haskell parMap 和并行性

Question

Haskell parMap 和并行性

haskellparallel-processingconways-game-of-life

9

我有一个Conway生命游戏的实现。如果可能，我想通过使用并行化来加速它。

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不正确吗？这种情况是否可以使用并行处理？

- cdk

首先，你的电脑至少有3个核心吗？其次，并行性总是伴随着一些开销，因此如果每个线程执行的工作非常小，则额外的开销将抵消任何加速。 - huon

我有一台i5-2500k电脑，因此肯定有最多4个可用核心。 - cdk

请注意，通过改进算法而不是并行化，您可以获得更大的加速效果。大部分时间都花在了“sort”和“elem”上。利用单元格列表已排序的事实（并更改“fPent”以使其排序），您可以将时间大致减半。 - Daniel Fischer

@DanielFischer：如果fPent未排序，则列表不一定已排序。freq将每个相邻的活细胞的列表作为其输入，并且同一个细胞可能是许多不同的活细胞的邻居并散布在整个列表中。如果有一种方法可以更快地找到列表中每个唯一元素的总出现次数而不是排序，那确实会改善算法。 - cdk

Chris，你在这一步中对列表进行排序：freq = map (length &&& head) . group . sort，所以下一代的 cells 总是有序的。 - Daniel Fischer

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aleksandar Dimitrov · Accepted Answer

我认为你的测量方法不正确。你的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运行。

这是报告的详细结果。