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:
ParallelArraystudents = new ParallelArray (fjPool, data);
double bestGpa = students.withFilter(isSenior)
.withMapping(selectGpa)
.max();
public class Student {
String name;
int graduationYear;
double gpa;
}
static final Ops.PredicateisSenior = new Ops.Predicate () {
public boolean op(Student s) {
return s.graduationYear == Student.THIS_YEAR;
}
};
static final Ops.ObjectToDoubleselectGpa = 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.
Community comments
API or Language Extensions?
by Per Olesen,
Re: API or Language Extensions?
by Ilya Sterin,
closures, when?
by serge ----,
Articles by Brian Goetz
by Matt Passell,
Grid Enabled Fork/Join
by Dmitriy Setrakyan,
API or Language Extensions?
by Per Olesen,
Your message is awaiting moderation. Thank you for participating in the discussion.
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
Re: API or Language Extensions?
by Ilya Sterin,
Your message is awaiting moderation. Thank you for participating in the discussion.
Yes, take a look at scala.
closures, when?
by serge ----,
Your message is awaiting moderation. Thank you for participating in the discussion.
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_...
Articles by Brian Goetz
by Matt Passell,
Your message is awaiting moderation. Thank you for participating in the discussion.
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.
Grid Enabled Fork/Join
by Dmitriy Setrakyan,
Your message is awaiting moderation. Thank you for participating in the discussion.
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