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.}