gpt4 book ai didi

haskell - 在 Haskell 中使用并行策略时速度变慢

转载 作者:行者123 更新时间:2023-12-02 08:36:01 26 4
gpt4 key购买 nike

我正在完成 Andre Loh 在 haskell 练习中的确定性并行编程的练习。我尝试使用策略将 N-Queens 顺序代码转换为并行代码,但我注意到并行代码的运行速度比顺序代码慢得多,并且还会因堆栈空间不足而出错。

这是并行 N 皇后的代码,

import Control.Monad
import System.Environment
import GHC.Conc
import Control.Parallel.Strategies
import Data.List
import Data.Function

type PartialSolution = [Int] -- per column, list the row the queen is in
type Solution = PartialSolution

type BoardSize = Int

chunk :: Int -> [a] -> [[a]]
chunk n [] = []
chunk n xs = case splitAt n xs of
(ys, zs) -> ys : chunk n zs

-- Generate all solutions for a given board size.
queens :: BoardSize -> [Solution]
--queens n = iterate (concatMap (addQueen n)) [[]] !! n
queens n = iterate (\l -> concat (map (addQueen n) l `using` parListChunk (n `div` numCapabilities) rdeepseq)) [[]] !! n


-- Given the size of the problem and a partial solution for the
-- first few columns, find all possible assignments for the next
-- column and extend the partial solution.
addQueen :: BoardSize -> PartialSolution -> [PartialSolution]
addQueen n s = [ x : s | x <- [1..n], safe x s 1 ]

-- Given a row number, a partial solution and an offset, check
-- that a queen placed at that row threatens no queen in the
-- partial solution.
safe :: Int -> PartialSolution -> Int -> Bool
safe x [] n = True
safe x (c:y) n = x /= c && x /= c + n && x /= c - n && safe x y (n + 1)

main = do
[n] <- getArgs
print $ length $ queens (read n)

(\l -> concat (map (addQueen n) l using parListChunk (n div numCapability) rdeepseq)) 是我对原始代码所做的更改。我已经看过 Simon Marlow 的解决方案,但我想知道代码中速度缓慢和错误的原因。

提前致谢。

最佳答案

你引发了太多的工作。 parListChunk div n numCapabilities的参数您的系统上可能有 7 个(2 个核心,而您正在运行 n ~ 14 个)。该列表将很快变得很大,因此没有必要激发如此小的工作单元(而且我不明白为什么将其与 n 的值联系起来是有意义的)。

如果我增加十倍(在本例中使 Spark 单元为 70),那么我将获得明显优于单线程的性能。另外,我没有您提到的堆栈问题 - 如果它随着您的 parListChunk 的更改而消失值,然后我会将其报告为错误。

如果我每 800 进行一次分块,那么时间将分别为 5.375 秒和 7.9 秒。超过800,性能又开始变差了,ymmv。

编辑:

[tommd@mavlo Test]$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 7.0.4
[tommd@mavlo Test]$ ghc -O2 so.hs -rtsopts -threaded -fforce-recomp ; time ./so 13 +RTS -N2
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
73712
real 0m5.404s

[tommd@mavlo Test]$ ghc -O2 so.hs -rtsopts -fforce-recomp ; time ./so 13
[1 of 1] Compiling Main ( so.hs, so.o )
Linking so ...
73712
real 0m8.134s

关于haskell - 在 Haskell 中使用并行策略时速度变慢,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10009361/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com