5

私が怠け者Treeで、その葉が問題の可能な解決策であるとしましょう

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

解決策を 1 つだけ見つける必要があります(または、解決策がないことを確認する必要があります)。

私はPコアマシンを持っています。時間とメモリ効率の両方を考慮すると、 P 個の異なる分岐に沿って並列に検索することだけが理にかなっています。

たとえば、計算量がほぼ同じ ( CPU 時間のT秒に相当) の 4 つのブランチがあり、それぞれに答えがあるとします。

デュアル コア マシンで 4 つの分岐すべてを真に並列に評価すると、それらはすべて約2T秒で終了します。

最初の 2 つのブランチだけを評価し、残りの 2 つを延期すると、わずかT秒で答えが得られ、メモリの使用量も 2 倍少なくなります。

私の質問は、これを達成するために並列 Haskell インフラストラクチャ (Par モナド、並列戦略など) を使用することは可能ですか、それとも async のような低レベルのツールを使用する必要がありますか?

4

2 に答える 2

1

少なくともパッケージParのモナドと戦略は、parallel純粋で無条件の並列システムのみを構築することを可能にします。

a
/ \
紀元前
\ /\
 で
 \ ...

一般的に、不純なスレッド間通信が本当に必要ですが、次のようになります。

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

ただし、単一の葉の計算が十分かつ同等に高価である場合、unsing 戦略はパフォーマンスに大きな影響を与えるべきではありません(よくわかりません):

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 に答える