5

假设我有一个懒惰Tree的人，他的叶子是解决问题的可能方法

data Tree a = Node [Tree a] | Leaf (Maybe a)

我只需要找到一种解决方案（或发现没有解决方案）。

我有一台P核机器。从时间和内存效率的考虑来看，只有沿着P个不同的分支并行搜索才有意义。

例如，假设您有四个计算复杂度大致相同的分支（对应于T秒的 CPU 时间），并且每个分支都有一个答案。

如果您在双核机器上真正并行评估所有四个分支，那么它们都将在大约2T秒内完成。

如果您只评估前两个分支并推迟其他两个分支，那么您将在T秒内得到答案，同时使用的内存也减少了两倍。

我的问题是，是否可以使用任何并行的 Haskell 基础架构（Par monad、并行策略……）来实现这一点，还是我必须使用像异步这样的低级工具？

4

2 回答 2

5

如果有可用的 CPU，则 Strategies 和 Par monad 都只会开始评估新的并行任务，因此在您的示例中，在 2 核机器上有四个分支时，只会评估两个。此外，一旦您有答案，策略将 GC 其他任务（尽管这样做可能需要一段时间）。

但是，如果这两个分支中的每一个都创建了更多任务，那么您可能希望优先考虑较新的任务（即深度优先），但策略至少会优先考虑较旧的任务。我认为 Par monad 优先考虑新的（但我必须检查），但是 Par monad 将在返回答案之前评估所有任务，因为这就是它如何强制执行确定性。

因此，目前，让它完全按照你的意愿工作的唯一方法可能是为 Par monad 编写一个自定义调度程序。

于 2013-06-28T08:57:48.553 回答
1

至少包中的Parmonad 和策略parallel只允许构建纯粹的、无条件的并行系统，这些系统看起来很漂亮：

一个
/ \
公元前
\ /\
 德
 \ ...

虽然在一般情况下，您确实需要不纯的线程间通信：

solve :: Tree a -> Maybe a

smartPartition :: Tree a -> Int -> [[Tree a]]
smartPartition tree P = ... -- split the tree in fairly even chunks,
                            -- one per each machine core

solveP :: Tree a -> IO (Maybe a)
solveP tree = do
    resRef <- newIORef Nothing
    results <- parallel (map work (smartPartition tree))
    return (msum results)
  where work [] = return Nothing
        work (t:ts) = do
            res <- readIORef resRef
            if (isJust res) then (return res) else do
                let tRes = solve t
                if (isNothing tRes) then (work ts) else do
                    writeIORef tRes
                    return tRes

但是，如果您的单叶计算足够且同样昂贵，则取消策略不应该（我不确定）会大大损害性能：

partitionLeafs :: Tree a -> Int -> [[Tree a]]

solveP :: Tree a -> Maybe a
solveP = msum . map step . transpose . partitionLeafs
  where step = msum . parMap rdeepseq solve

PS我觉得我对问题领域的理解并不比你好（至少），所以你可能已经知道以上所有内容。我写了这个答案来展开讨论，因为这个问题对我来说很有趣。

于 2013-06-26T19:12:04.247 回答