knuthBendix算法无法由Control.Parallel并行化

Question

我正在尝试将knuthBendix应用于大型重写规则集。因此，我试图让它在不同的集合上并行工作。

例如，我尝试运行：

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来说，情况并非如此。

有人知道解决方案吗？

谢谢，Franz

Answer 1

我认为问题在于您正在调用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中与线程及其通信的显式工作。请参阅GHC手册}

Answer 2

我不认为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.

在我看来，拆分你所做的方式会改变语义。你可能需要一些更具侵入性的并行性。