Monday, September 19, 2011

Parallelism in Frege employing the fork/join Java API

Yesterday I implemented some experimental support for the fork/join API that comes with JDK 7.

The base operation from a Frege point of view is par. An expression like

a `par` b

arranges for evaluation of a in another thread and returns b, like in Haskell.
For example, a parallel map can be implemented like this

pmap f [] = []
pmap f (x:xs) = a `par` as `par` (a:as) 
    where
        a  = f x
        as = pmap f xs

Unlike the ordinary map, pmap works only on finite lists, because construction of the tail implies immediate construction of the tail of the tail and so forth.

There is an example program in the distribution that implements different algorithms for computing the number of solutions to the n queens puzzle. I added a parallel version of the list based solution and measured the resulting run times. The parallel version constructs n different start out positions where the first queen is placed on a different column of the first row each time, and computes the solutions for the n start out positions in parallel. Then it adds the results.

I have a computer with 2 "hyperthreaded" cores. The JVM deduced from this that the parallelism must be 4 and starts 4 worker threads. During program execution, I saw a CPU utilization of around 75%. This already saved 50% of the run time in medium sized problems (up to n=13).

I then arranged it so that 2 threads will be created for every "CPU", and noticed an overall CPU utilization of 95%. The savings in run time tend to manifest themselves better the  greater the problem is and seem to approximate  2/3. But this numbers will most likely depend on the hardware and maybe the OS.

In small problems that take less than a second in the sequential version (i.e. n=8), the run time differences are barely noticeable.

There is also the possibility to prohibit the Frege run time from actually executing anything in parallel by passing a system property -Dfrege.parallel=false in the command line. The par operator will then effectively behave like

a `par` b =  snd (a,b)

The feature is included in the frege3.17.152.jar available from the download area.

No comments:

Post a Comment

Comments will be censored by me as I see fit, most likely if they contain insults or propaganda for ideologies I do not like. Comments that are on topic will not be censored. If I leave a comment uncensored this does not imply that I agree with the opinions expressed therein.