3

我正在尝试将 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，它没有。

有人知道解决方案吗？

谢谢，弗兰兹

4

2 回答 2

5

我相信问题是你在打电话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 手册。

于 2013-07-15T18:05:16.763 回答
4

我不认为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-15T15:37:13.837 回答