knuthBendix algorithm cannot be parallelized by Control.Parallel?

Question

I am trying to apply knuthBendix to large sets of rewriting rules. Thus, I try to let it work on different sets in parallel.

As en example, I try to run:

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

I compile using ghc -threaded and I execute via +RTS -N. If I run other algorithms in parallel, it works. But for knuthBendix, it does not.

Does someone know a solution?

Thanks, Franz

Answer 1

I believe the problem is that you're calling as' `pseq`. This evaluates as' to WHNF, which means that it only determines whether the list is empty or not. But you want the lists to be fully evaluated:

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

_{Note that Haskell's usual term for this is parallelism. And concurrency is used for explicit work in IO with threads and their communication. See the GHC manual.}

Answer 2

I don't think knuthBendix parallelizes naively like that. The documentation says:

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.

It seems to me that splitting up the way you've done will change semantics. You probably need some more invasive parallelism.