How to write parallel abbreviations using strategies in Haskell?

Question

In high-performance computing, amounts, products, etc. often computed using "parallel reduction", which takes n elements and ends in O (log n) time (assuming enough parallelism). At Haskell, we usually use bending for this calculation, but the evaluation time is always linear along the length of the list.

Data Parallel Haskell has some of these built-in functions, but what is the general outline of the list? Can we do this with Control.Parallel.Strategies ?

So, if f associative, as we write

parFold :: (a -> a -> a) -> [a] -> a

so parFold f xs only needs a logarithmic time in time length xs ?

Answer 1

I don’t think the right data type is needed for this. Since this is only a linked list, the data will necessarily be available sequentially. Despite the fact that you can evaluate elements in parallel, you will not get much at the reduction stage. If you really need a List, I think the best feature would be just

 parFold f = foldl1' f . withStrategy (parList rseq) 

or maybe

 parFold f = foldl1' f . withStrategy (parBuffer 5 rseq) 

If the recovery step is difficult, you can get a win by dividing the list as follows:

 parReduce f = foldl' f mempty . reducedList . chunkList . withStrategy (parList rseq) where chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls reducedList = parMap rseq (foldl' f mempty) 

I took the liberty of assuming that your data is Monoid for mempty, if this is not possible, you can either replace mempty with your own empty type, or worse use foldl1' .

Two operators from Control.Parallel.Strategies are used here. parList evaluates all list items in parallel. After that, chunkList divides the list into pieces of 1000 elements. Each of these fragments is then reduced in parallel using parMap .

You can also try

 parReduce2 f = foldl' f mempty . reducedList . chunkList where chunkList list = let (l,ls) = splitAt 1000 list in l : chunkList ls reducedList = parMap rseq (foldl' f mempty) 

Depending on how the work is distributed, one of them may be more effective than the others.

If you can use a data structure that has good indexing support (Array, Vector, Map, etc.), you can make binary divisions for the reduction phase, which is likely to be better overall.

Answer 2

This seems like a good start:

 parFold :: (a -> a -> a) -> [a] -> a parFold f = go where strategy = parList rseq go [x] = x go xs = go (reduce xs `using` strategy) reduce (x:y:xs) = fxy : reduce xs reduce list = list -- empty or singleton list 

It works, but parallelism is not so great. Replacing parList with something like parListChunks 1000 helps a little, but the acceleration is still limited to 1.5x on an 8-core machine.

Answer 3

Not sure if your parFold function should execute. If this is assumed to be a parallel version of foldr or foldl, I think its definition is incorrect.

 parFold :: (a -> a -> a) -> [a] -> a // fold right in haskell (takes 3 arguments) foldr :: (a -> b -> b) -> b -> [a] -> b 

Fold applies the same function to each element of the list and accumulates the result of each application. I believe that, based on the parallel version, this will require that the application function to the elements be executed in parallel - a bit like parList does.

  par_foldr :: (NFData a, NFData b) => (a -> b -> b) -> b -> [a] -> b par_foldr fz [] = z par_foldr fz (x:xs) = res `using` \ _ -> rseq x' `par` rdeepseq res where x' = par_foldr fz xs res = x `f` x'