Over a million developers have joined DZone.

Testing Different Forms of Divide and Conquer

· Java Zone

Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code! Brought to you in partnership with ZeroTurnaround.

This post continues a series discussing the new fork/join features added to Java SE 7. Part 1 and part 2 introduced an example application that performs a Monte Carlo simulation of the Net Present Value of an investment with uncertain profits and discount rate. The example application is available on GitHub.

The previous post glossed over an important question: what is the “right” way to divide up the work? Of course, the answer is dependent on the type of work being performed and the machine on which it is run. But there are some alternatives that we can consider.

First, recall that we start with a large amount of work (in this case, many runs of a simulation that are independent). Below a certain size, we perform the “base case”, where we run like an ordinary sequential program. The size of the “base case” is itself a tunable parameter.

Above that minimum size, we operate by dividing the work, creating tasks to perform each piece of work, and collecting the results when the tasks are complete. Each sub-task may itself spawn tasks to divide the work further until the base case size is reached. It therefore makes sense to talk about how many levels there will be, what is known as the “depth” of the implementation.

The depth is specified using “Big O” notation since we are mostly interested in how the depth will grow as the size of the problem changes. Of course, the approach we choose for dividing up the work will affect this depth. In general, the flatter the depth, the higher the theoretical value we can gain from adding more processors, since the theoretical maximum speedup is the total work performed divided by the depth. (This is intuitive; if we had total work ofO(n) and we could perform all those steps in parallel, so that depth is O(1), we could in theory perform the whole calculation in one step if we had nprocessors.)

Actually getting linear speedup is generally not possible, but typical approaches do reasonably well for most problem sizes and machines.

The first approach divides up the work by a constant factor. A special case of this is dividing the work up based on the number of available processors.

Another approach is to choose the number of children based on the size of the input. This calculation is performed at each level of recursion. The common choice is to use sqrt(n) as the number of children, as this reduces the growth in

A third approach immediately divides the work into enough chunks that no further subdivision is necessary. In languages like Cilk Plus, there is a parallelfor statement to specify this. Of course, the number of tasks that can actually be performed in parallel is much less, so in implementation this is similar to dividing up the work based on the number of processors.

The example application provides the means to test the above approaches. Here is example output from a run on a quad-core i7 using 10 million iterations.

StopWatch 'Monte Carlo NPV': running time (millis) = 40192
-----------------------------------------
ms     %     Task name
-----------------------------------------
10149  025%  Sequential
02413  006%  DivideByTwo (children=2, min fork size=100)
02350  006%  DivideByTwo (children=2, min fork size=500)
02418  006%  DivideByTwo (children=2, min fork size=1000)
02448  006%  DivideByTwo (children=2, min fork size=2000)
02271  006%  DivideByP (children=8, min fork size=100)
02260  006%  DivideByP (children=8, min fork size=500)
02263  006%  DivideByP (children=8, min fork size=1000)
02281  006%  DivideByP (children=8, min fork size=2000)
02271  006%  Sqrt(n) (children=-1, min fork size=100)
02270  006%  Sqrt(n) (children=-1, min fork size=500)
02271  006%  Sqrt(n) (children=-1, min fork size=1000)
02268  006%  Sqrt(n) (children=-1, min fork size=2000)
02259  006%  Parfor (children=20000, min fork size=500)

The differences are mostly not significant; another run shows different outcomes, with not just the numbers changing but the order of fastest to slowest also different:

StopWatch 'Monte Carlo NPV': running time (millis) = 44836
-----------------------------------------
ms     %     Task name
-----------------------------------------
10162  023%  Sequential
02841  006%  DivideByTwo (children=2, min fork size=100)
02712  006%  DivideByTwo (children=2, min fork size=500)
02734  006%  DivideByTwo (children=2, min fork size=1000)
02839  006%  DivideByTwo (children=2, min fork size=2000)
02621  006%  DivideByP (children=8, min fork size=100)
02586  006%  DivideByP (children=8, min fork size=500)
02617  006%  DivideByP (children=8, min fork size=1000)
02620  006%  DivideByP (children=8, min fork size=2000)
02612  006%  Sqrt(n) (children=-1, min fork size=100)
02619  006%  Sqrt(n) (children=-1, min fork size=500)
02620  006%  Sqrt(n) (children=-1, min fork size=1000)
02639  006%  Sqrt(n) (children=-1, min fork size=2000)
02614  006%  Parfor (children=20000, min fork size=500)

The results allow us to develop some reasonable conclusions about using Java fork/join:

  1. Parallel is better than sequential. All of our parallel methods did significantly better. Note that the speedup was pretty close to 4x on a quad-core processor.
  2. Simple is better than complicated. At least for this kind of example, there isn’t a lot of real-world value to be gained from more complex calculations for how the work should be divided. There’s lots of good work in the high-performance computing literature, whether it’s dividing up problems, representing sparse matrices, or using custom-made parallel algorithms. Much of that work applies to really big problem sets or really big clusters. If you’re not working with trillions of rows or run times measured in days, readability is probably more important.
  3. Performance isn’t always intuitive. The “Parfor” implementation creates 20,000 tasks, which seems like a lot. But the “DivideByTwo” implementation with “base case” size of 100 creates 262,142 tasks, and runs in about the same amount of time.
  4. The Javadocs are telling the truth when they say that fork/join tasks are much lighter weight than a normal thread. It’s doubtful that a Java application that spawned 262,142 threads would be peformant (or still alive) on normal hardware.
  5. Off-by-one errors are the bane of parallel programming, and you willrun into them. My initial implementation of NpvTask had a bug that would spawn children if the number of requested iterations was equal to the “base case” size. This means each of the 20,000 tasks in my “Parfor” spawned 20,000 children, taking 15 seconds to run. I noticed it when I had the StatsCollector also keep track of how many total instances were spawned and wound up with 4 billion.

Hopefully this has been a beneficial introduction to fork/join in Java. The key is that for computations involving a large body of work that can be subdivided, fork/join can provide parallel speedup with compact code.

The Java Zone is brought to you in partnership with ZeroTurnaround. Check out this 8-step guide to see how you can increase your productivity by skipping slow application redeploys and by implementing application profiling, as you code!

Topics:

Published at DZone with permission of Alan Hohn, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}