parallel Haskell

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

parallel Haskell

Dennis Raddle
I have a program which does backtracking search in a recursive function.  I followed the chapter in "Real World Haskell" to parallelize it.

Without Control.Parallel, it uses about 25% of the CPU, namely one core out of four. With the suggestions in RWH it runs faster but still uses only 35% of the CPU max. 

So I set about creating a MWE in order to experiment and reach out for help. For some reason, my stripped down program isn't working with parallelism at all! 

There's no effect from the R.W.H. ideas. Can I get some suggestions as to why? 

Here's the program:
--------------------------------------------
import qualified Data.List as L
import Text.Printf
import System.CPUTime
import Data.Function
import Control.Parallel

-- Run backtracking search for a list of doubles, optimizing a 
-- fitness function on the list, called 'evalFunc'. At each step, use 'stepFunc' 
-- to generate a list of possible next Doubles that can be added to the list. 
-- We are done when the list has 'finalSize' elements.
search1_par :: Int ->
  ([Double] -> Double) -> ([Double] -> [Double]) -> [Double] -> (Double,[Double])
search1_par finalSize evalFunc stepFunc listIn
  | length listIn == finalSize = (evalFunc listIn,listIn)
  | otherwise = 
      let steps = stepFunc listIn
          (steps1,steps2) = divideListInTwo steps
          f s = search1_par finalSize evalFunc stepFunc $ s:listIn
          results1 = map f steps1
          results2 = map f steps2
          results = force results1 `par` (force results2 `pseq` (results1++results2))
      in L.maximumBy (compare `on` fst) results
  
force :: [a] -> ()
force xs = go xs `pseq` ()
  where go (_:xs) = go xs
        go [] = 1

divideListInTwo :: [a] -> ([a],[a])
divideListInTwo [] = ([],[])
divideListInTwo xs = (take l xs,drop l xs) where l = length xs `div` 2

---------------------------------------------
-- some sample evaluation (fitness) functions and step generation functions.

eval1 :: [Double] -> Double
eval1 xs = v1 - v2 + v3
  where
    v1 = sum $ zipWith (*) (cycle [1]) xs
    v2 = sum . map (*2) $ zipWith (*) (cycle [1,0]) xs
    v3 = sum . map (*3)  $ zipWith (*) (cycle [1,0,0]) xs


step1 :: [Double] -> [Double]
step1 xs | l == 0 = take 8 $ xs
         | l == 1 = take 8 $ map (/2) xs
         | l == 2 = take 8 $ map (*3) xs
  where
    l = length xs `mod` 3
--------------------------------------------------------------------------------
-- main

main = do
  t1 <- getCPUTime
  let f :: Double -> String
      f x = printf "%5.1f" x
      (_,result) = search1_par 13 eval1 step1 [1,2,3]
  putStrLn $ concatMap f result
  t2 <- getCPUTime
  putStrLn $ printf "CPU time: %.3f" ((fromIntegral $ t2-t1) / 1000000000000 :: Double)


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: parallel Haskell

Dennis Raddle
Oh, I should clarify what I mean by "no effect from R.W.H. ideas." I wrote this first without parallelism and it took about 50 seconds to run and used about 20% of the CPU. After modifying it per the suggestions in R.W.H, it still takes about 50 seconds of wall clock time to run, and still uses no more than 20% CPU. 

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: parallel Haskell

Claude Heiland-Allen-3
In reply to this post by Dennis Raddle
Hi Dennis,

On 06/07/17 17:53, Dennis Raddle wrote:
> I have a program which does backtracking search in a recursive
> function.  I followed the chapter in "Real World Haskell" to parallelize it.
[snip]
> There's no effect from the R.W.H. ideas. Can I get some suggestions as
> to why?

You can get timing and other useful diagnostics by compiling with
-rtsopts and running with +RTS -s, no need to measure CPU time in your
own program.

> force :: [a] -> ()
> force xs = go xs `pseq` ()
>   where go (_:xs) = go xs
>         go [] = 1

This force doesn't do enough, it just walks the spine. Try this, which
forces the elements as well as the shape:

force :: [a] -> ()
force xs = go xs `pseq` ()
  where go (x:xs) = x `pseq` go xs
        go [] = 1

Thanks,


Claude
--
https://mathr.co.uk
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: parallel Haskell

Rein Henrichs
Please take a look at Simon Marlow's free book, Parallel and Concurrent Programming in Haskell (http://chimera.labs.oreilly.com/books/1230000000929). It will teach you a lot about... the things in the title.

On Thu, Jul 6, 2017 at 10:21 AM Claude Heiland-Allen <[hidden email]> wrote:
Hi Dennis,

On 06/07/17 17:53, Dennis Raddle wrote:
> I have a program which does backtracking search in a recursive
> function.  I followed the chapter in "Real World Haskell" to parallelize it.
[snip]
> There's no effect from the R.W.H. ideas. Can I get some suggestions as
> to why?

You can get timing and other useful diagnostics by compiling with
-rtsopts and running with +RTS -s, no need to measure CPU time in your
own program.

> force :: [a] -> ()
> force xs = go xs `pseq` ()
>   where go (_:xs) = go xs
>         go [] = 1

This force doesn't do enough, it just walks the spine. Try this, which
forces the elements as well as the shape:

force :: [a] -> ()
force xs = go xs `pseq` ()
  where go (x:xs) = x `pseq` go xs
        go [] = 1

Thanks,


Claude
--
https://mathr.co.uk
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: parallel Haskell

Dennis Raddle
thanks for the tip, that book is great... I'm reading it now, and it's an easy read, very clear explanations of laziness. I never understood laziness all that well before.

D

On Thu, Jul 6, 2017 at 10:34 AM, Rein Henrichs <[hidden email]> wrote:
Please take a look at Simon Marlow's free book, Parallel and Concurrent Programming in Haskell (http://chimera.labs.oreilly.com/books/1230000000929). It will teach you a lot about... the things in the title.

On Thu, Jul 6, 2017 at 10:21 AM Claude Heiland-Allen <[hidden email]> wrote:
Hi Dennis,

On 06/07/17 17:53, Dennis Raddle wrote:
> I have a program which does backtracking search in a recursive
> function.  I followed the chapter in "Real World Haskell" to parallelize it.
[snip]
> There's no effect from the R.W.H. ideas. Can I get some suggestions as
> to why?

You can get timing and other useful diagnostics by compiling with
-rtsopts and running with +RTS -s, no need to measure CPU time in your
own program.

> force :: [a] -> ()
> force xs = go xs `pseq` ()
>   where go (_:xs) = go xs
>         go [] = 1

This force doesn't do enough, it just walks the spine. Try this, which
forces the elements as well as the shape:

force :: [a] -> ()
force xs = go xs `pseq` ()
  where go (x:xs) = x `pseq` go xs
        go [] = 1

Thanks,


Claude
--
https://mathr.co.uk
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.


_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: parallel Haskell

Dennis Raddle
I'm looking into using rpar and rseq from Control.Parallel.Strategies. The issue is that most of my code executes in a monad stack including StateT and ExceptT. Can I use the Eval monad at the root of the stack safely? 

D

On Thu, Jul 6, 2017 at 10:06 PM, Dennis Raddle <[hidden email]> wrote:
thanks for the tip, that book is great... I'm reading it now, and it's an easy read, very clear explanations of laziness. I never understood laziness all that well before.

D

On Thu, Jul 6, 2017 at 10:34 AM, Rein Henrichs <[hidden email]> wrote:
Please take a look at Simon Marlow's free book, Parallel and Concurrent Programming in Haskell (http://chimera.labs.oreilly.com/books/1230000000929). It will teach you a lot about... the things in the title.

On Thu, Jul 6, 2017 at 10:21 AM Claude Heiland-Allen <[hidden email]> wrote:
Hi Dennis,

On 06/07/17 17:53, Dennis Raddle wrote:
> I have a program which does backtracking search in a recursive
> function.  I followed the chapter in "Real World Haskell" to parallelize it.
[snip]
> There's no effect from the R.W.H. ideas. Can I get some suggestions as
> to why?

You can get timing and other useful diagnostics by compiling with
-rtsopts and running with +RTS -s, no need to measure CPU time in your
own program.

> force :: [a] -> ()
> force xs = go xs `pseq` ()
>   where go (_:xs) = go xs
>         go [] = 1

This force doesn't do enough, it just walks the spine. Try this, which
forces the elements as well as the shape:

force :: [a] -> ()
force xs = go xs `pseq` ()
  where go (x:xs) = x `pseq` go xs
        go [] = 1

Thanks,


Claude
--
https://mathr.co.uk
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.



_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: parallel Haskell

Dennis Raddle
Oh, I think I realized why that won't work. I think that a program in the State monad, for instance, must execute its computations sequentially. There is no way to "split" a State monad into separate lines of execution from within the monad. I think the answer is that I have to split my computation before my code enters into the State monad. So I need to call runState four times for four cores, or whatever. Something like that.

D


On Fri, Jul 7, 2017 at 1:33 AM, Dennis Raddle <[hidden email]> wrote:
I'm looking into using rpar and rseq from Control.Parallel.Strategies. The issue is that most of my code executes in a monad stack including StateT and ExceptT. Can I use the Eval monad at the root of the stack safely? 

D

On Thu, Jul 6, 2017 at 10:06 PM, Dennis Raddle <[hidden email]> wrote:
thanks for the tip, that book is great... I'm reading it now, and it's an easy read, very clear explanations of laziness. I never understood laziness all that well before.

D

On Thu, Jul 6, 2017 at 10:34 AM, Rein Henrichs <[hidden email]> wrote:
Please take a look at Simon Marlow's free book, Parallel and Concurrent Programming in Haskell (http://chimera.labs.oreilly.com/books/1230000000929). It will teach you a lot about... the things in the title.

On Thu, Jul 6, 2017 at 10:21 AM Claude Heiland-Allen <[hidden email]> wrote:
Hi Dennis,

On 06/07/17 17:53, Dennis Raddle wrote:
> I have a program which does backtracking search in a recursive
> function.  I followed the chapter in "Real World Haskell" to parallelize it.
[snip]
> There's no effect from the R.W.H. ideas. Can I get some suggestions as
> to why?

You can get timing and other useful diagnostics by compiling with
-rtsopts and running with +RTS -s, no need to measure CPU time in your
own program.

> force :: [a] -> ()
> force xs = go xs `pseq` ()
>   where go (_:xs) = go xs
>         go [] = 1

This force doesn't do enough, it just walks the spine. Try this, which
forces the elements as well as the shape:

force :: [a] -> ()
force xs = go xs `pseq` ()
  where go (x:xs) = x `pseq` go xs
        go [] = 1

Thanks,


Claude
--
https://mathr.co.uk
_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.

_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.




_______________________________________________
Haskell-Cafe mailing list
To (un)subscribe, modify options or view archives go to:
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Only members subscribed via the mailman list are allowed to post.
Loading...