並行樹搜索

Question

比方說，我有一個懶惰的Tree，葉子是可能的解決的一個問題

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

我需要找到只是一個溶液（或找出是沒有的）。

我有一個P核心機器。從時間和內存效率兩方面來考慮，並行搜索不同分支只是有意義的。

例如，假設你有大致相同的計算複雜度（對應於的T CPU時間秒）四個分所，他們每個人都有一個答案。

如果您在雙核機器上真正並行評估所有四個分支，那麼它們都將在大約012秒鐘內完成大約2T秒。

如果您只評估前兩個分支並推遲了其他兩個分支，那麼您將在僅有T秒的時間內得到答案，同時使用的內存也少兩倍。

我的問題是，是否有可能使用任何並行Haskell基礎設施（Par monad，並行策略...）來實現此目標，還是必須使用像async這樣的更低級別的工具？

Answer 1

如果有可用的CPU，Both Strategies和Par monad只會開始評估新的並行任務，因此在您的示例中，在雙核機器上有四個分支，只有兩個分支將被評估。此外，一旦你有答案，策略將GC的其他任務GC（雖然它可能需要一段時間）。但是，如果這兩個分支中的每一個都創建更多的任務，那麼您可能希望優先考慮較新的任務（即深度優先），但策略至少會優先考慮較早的任務。 Par monad我認爲優先考慮新的（但我必須檢查它），但Par monad會在返回答案之前評估所有任務，因爲這是它強制決定論的方式。

因此，可能唯一的方法就是爲Par monad編寫一個自定義調度程序。

Answer 2

至少Par單子和parallel包裝策略允許只建純，無條件的並行系統，看起來嬌滴滴這樣的圖片：

 
a 
/\ 
b c 
\ /\ 
d e 
\ ... 

雖然在一般情況下，你真的需要不純的線程間通信：

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 

P. S.我覺得我理解這個問題的領域並不比你（至少），所以你可能已經知道上述所有。我寫了這個答案來開展討論，因爲這個問題對我來說非常有趣。