knuthBendix算法不能通過Control.Parallel並行化？

我想將knuthBendix應用於大量的重寫規則。因此，我試着讓它在不同的平行上工作。knuthBendix算法不能通過Control.Parallel並行化？

，因爲en例子，我嘗試運行：

import Control.Parallel 
import Control.Parallel.Strategies 
import Math.Algebra.Group.StringRewriting 

knuthBendixOptimized rs = as' `par` bs' `pseq` as' ++ bs' where 
    (as, bs) = splitAt 3000 rs 
    as' = knuthBendix as 
    bs' = knuthBendix bs

我編譯使用ghc -threaded和我通過+RTS -N執行。如果我並行運行其他算法，它會起作用。但對於knuthBendix來說，它並不是。

有人知道解決方案嗎？

感謝，弗朗茨

來源

2013-07-15 H. Askell

我相信問題是您打電話給as' `pseq`。這將評估as'爲WHNF，這意味着它僅確定列表是否爲空。但您需要的名單進行充分評估：

import Control.Parallel.Strategies  

forceList :: [a] -> [a] 
forceList = withStrategy (evalList rseq) 
-- or use rdeepseq to force the evaluation of everything 

knuthBendixOptimized rs =  forceList as' 
          `par` forceList bs' 
          `pseq` as' ++ bs' 
    where 
    (as, bs) = splitAt 3000 rs 
    as' = knuthBendix as 
    bs' = knuthBendix bs

_{注意，Haskell的這個通常期限爲並行。和併發用於IO與線程及其通信的顯式工作。見the GHC manual。}

來源

2013-07-15 18:05:16

謝謝！我想你是對的。我明天會測試它......順便說一下：與並行性有關的動詞是什麼。（對不起，我的英文;） –

謝謝，現在它工作！（我現在已經測試過了。） –

我不認爲knuthBendix並行化，天真這樣。該文件說：

knuthBendix :: Ord a => [([a], [a])] -> [([a], [a])] 

Implementation of the Knuth-Bendix algorithm. Given a list of relations, return a 
confluent rewrite system. The algorithm is not guaranteed to terminate.

在我看來，分裂你所做的方式將改變語義。你可能需要一些更具侵入性的並行性。

來源

2013-07-15 15:37:13 sclv

你是對的。但是，應該可以在子集上執行knuthBendix，然後在整個列表上執行。這不是我的觀點。我的問題是，爲什麼'as''和'bs''不是並行計算的...... –

@ user2583983你的意思是_parallelize_？ –

是的，但我不確定這個動詞。謝謝！ –

knuthBendix算法不能通過Control.Parallel並行化？

回答

相關問題