Parallelism with Fork/Join in Java 7

Posted by R.J. Lorimer on Mar 21, 2008

Community

Java

Topics

Programming ,

Performance & Scalability ,

JCP Standards

Tags

JCP ,

Concurrency ,

Closures

As the number of processor cores available on modern hardware increases, it's becoming ever more important for developers to develop in ways that take advantage of the new hardware. IBM Developerworks has posted a multi-part series on the Fork-Join concurrency library, which is shipping as part of the upcoming Java 7 release. InfoQ covered the initial fork/join proposal for Java 7 previously, with feedback from the original author, Doug Lea. The concept of fork/join with respect to Java was originally introduced by Doug Lea in his paper 'Fork/Join Parallelism in Java'. His util.concurrent package was the foundation of JSR-166, which was the java.util.concurrent library released in Java 5. Fork/Join is simply a revision of this JSR.

Part 1 of the series details the central concepts of the fork-join library, and the problem it attempts to solve:

Going forward, the hardware trend is clear; Moore’s Law will not be delivering higher clock rates, but instead delivering more cores per chip. It is easy to imagine how you can keep a dozen processors busy using a coarse-grained task boundary such as a user request, but this technique will not scale to thousands of processors — traffic may scale exponentially for short periods of time, but eventually the hardware trend wins out. As we enter the many-core era, we will need to find finer-grained parallelism or risk keeping processors idle even though there is plenty of work to do. As the dominant hardware platform shifts, so too must the software platform if we wish to keep up. To this end, Java 7 will include a framework for representing a certain class of finer-grained parallel algorithms: the fork-join framework.

Fork-join embodies the technique of divide-and-conquer; take a problem and recursively break it down into subproblems until the subproblems are small enough that they can be more effectively solved sequentially. The recursive step involves dividing a problem into two or more subproblems, queueing the subproblems for solution (the fork step), waiting for the results of the subproblems (the join step), and merging the results.

The article then shows an example of the merge-sort algorithm using fork/join.

The last component covered in this series is the ParallelArray class. ParallelArray is a fork/join-enabled data structure that provides a general-purpose API for performing searching, filtering, and transforming on data sets in a highly concurrent manner.

The team working on the BGGA Closures proposal for Java have adapted the fork-join framework to work with closures, and have a working implementation on their proposal site. This Developerworks article series shows two examples of using the ParallelArray class - one without the closures proposal, and one with:

Here is an example of searching for a max GPA in a group of students using the current Java 7 fork/join proposal:

ParallelArray students = new ParallelArray(fjPool, data);
double bestGpa = students.withFilter(isSenior)
                         .withMapping(selectGpa)
                         .max();

public class Student {
    String name;
    int graduationYear;
    double gpa;
}

static final Ops.Predicate isSenior = new Ops.Predicate() {
    public boolean op(Student s) {
        return s.graduationYear == Student.THIS_YEAR;
    }
};

static final Ops.ObjectToDouble selectGpa = new Ops.ObjectToDouble() {
    public double op(Student student) {
        return student.gpa;
    }
};

Here is the same example using the BGGA Closures proposal:

double bestGpa = students.withFilter({Student s => (s.graduationYear == THIS_YEAR) })
                         .withMapping({ Student s => s.gpa })
                         .max();

Currently, Java 7 is expected for an early 2009 release.

1. Back to top

   API or Language Extensions?

   Mar 22, 2008 3:10 AM by Per Olesen

   It is nice and interesting, that Java is coming with new concurrency constructs in APIs. But there are many out there (all the Erlang folks, e.g.), that think we are in need of a language, where the concurrency support is built into the language. Erlang is such a language, but I really do not think Erlang to become a widespread language, like Java is.
   
   
   
   Does anyone know of ongoing work somewhere, to extend Java with language constructs, that enable easy use of multicore CPUs? That is, language constructs, not merely new APIs and frameworks.
   
   
   
   
   Tech Per
   
   
   
   
   

   Reply

2. Back to top

   Re: API or Language Extensions?

   Mar 22, 2008 12:51 PM by Ilya Sterin

   Yes, take a look at scala.

   Reply

3. Back to top

   closures, when?

   Mar 22, 2008 2:55 PM by serge boulay

   I don't think we will be seeing any of this anytime soon. Especially the closure stuff, take a look at Neil Gafter's presentation from qCon, I suspect closures won't even be in java 7 (bgga). It looks like java 8 now, unless I missed something That means you'll be able to use the closure example in about 5 years. I think I need to start looking at Scala.
   
   
   www.eos1.dk/qcon-london-2008/slides/NealGafter_...

   Reply

4. Back to top

   Articles by Brian Goetz

   Mar 22, 2008 9:50 PM by Matt Passell

   The announcement above fails to mention that the author of these articles on IBM DeveloperWorks is Brian Goetz, lead author of the book Java Concurrency in Practice. Just thought I'd include that tidbit.

   Reply

5. Back to top

   Grid Enabled Fork/Join

   Mar 24, 2008 6:45 PM by Dmitriy Setrakyan

   I am hoping this proposal actually makes it into Java 7.
   

   
   GridGain has been providing fork/join type of processing on the Grid for ages, so once this proposal is out, we will make sure to grid-enable it right away ;-)
   

   
   Also, I particularly like the proposed "work stealing" paradigm within local JVM, as it also has a direct application on the grid. We have implemented this paradigm on the grid (we call it job stealing) where underloaded nodes steal jobs from overloaded nodes to provide even load distribution across grid nodes (you can see docs on the Wiki here).
   

   
   Best,
   
   Dmitriy Setrakyan
   
   GridGain - Grid Computing Made Simple
   
   

   Reply

• Older >