Leveraging Multicore CPU architecture with fork-join framework in Java

Introduction

Hardware trends drive programming idioms. The Java language has had support for threads and concurrency from day 1; the language includes synchronization primitives such as synchronized and volatile, and the class library includes classes such as Thread. However, the concurrency primitives that were sensible in 1995 reflected the hardware reality of the time: most commercially available systems provided no parallelism at all, and even the most expensive systems provided only limited parallelism. In those days, threads were used primarily for expressing asynchrony, not concurrency, and as a result, these mechanisms were generally adequate to the demands of the time.

Going forward, the hardware trend is clear; Moore's Law will not be delivering higher clock rates, but instead delivering more cores per chip. As we enter the multi-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 includes a framework for representing a certain class of finer-grained parallel algorithms: the fork-join framework.

Fork-Join

The fork-join framework is an implementation of the ExecutorService interface that helps speed up parallel processing by attempting to use all available processor cores. This is accomplished through a divide and conquer approach. The fork/join framework is distinct because it uses a work-stealing algorithm. Worker threads that run out of things to do can steal tasks from other threads that are still busy. [1]

The center of the fork-join framework is the ForkJoinPool class which implements the core work-stealing algorithm and can execute ForkJoinTask processes. [1]

Divide and conquer

The standard technique for attacking exploitable parallelism is called recursive decomposition, or divide and conquer. In this approach, we repeatedly divide the problem into subproblems until the subproblems are small enough that it makes more sense to solve them sequentially; we then solve the subproblems in parallel, and combine the partial results of the subproblems to derive a total result.

Listing 1 illustrates a typical divide-and-conquer solution in pseudocode, using a hypothetical CONCURRENT primitive for concurrent execution.

Listing 1. Recursive decomposition

R solve(Problem<R> problem) {
    if (problem.isSmall())
        return problem.solveSequentially();
    R leftResult, rightResult;
    CONCURRENT {
        leftResult = solve(problem.leftHalf());
        rightResult = solve(problem.rightHalf());
    }
    return problem.combine(leftResult, rightResult);
}


Wrap this code in a ForkJoinTask subclass, typically using one of its more specialized types, either RecursiveTask (which can return a result) or RecursiveAction [1].

Workshop

Now let us implement Merge Sort algorithm using this approach. Multithreaded Merge Sort algorithm is given below.



The array is divided into two parts initially, and then the two sub arrays are sorted. This can be made in parallel. Once the two parallel tasks completed, merge is performed. Notice the sync point here. Now let us see the code using the fork-join framework to implement the Multi threaded Merge Sort algorithm.



Our client code should now look like this.
Two additional algorithmic steps are introduced by divide-and-conquer — dividing the problem, and combining the partial results.

Our problem Merge sort, admits decomposition nicely. The partitioning step of a problem like this is O(1)— "find the average of the top and bottom indices." Moreover since the two sub problems are almost equal in size, we can explore more exploitable parallelism. Merge sort has O(n log n) worst-case and average-case performance. But because the merging is difficult to do in place, generally, it has higher memory requirements than in-place sort algorithms, such as quick-sort. But because the sorting of the subproblems can be done in parallel, it parallelizes better than quick-sort. [3]

Given a fixed number of processors, parallelization still can't turn an O(n log n) problem into an O(n) one, but the more amenable the problem to parallelization, the closer to a factor of ncpus by which parallelization can reduce the total runtime. Reducing the total runtime means that the user gets the result sooner — even if it takes more total CPU cycles to do the work in parallel than it does sequentially.

The principal benefit of using the fork-join technique is that it affords a portable means of coding algorithms for parallel execution. The programmer does not have to be aware of how many CPUs will be available in deployment; the runtime can do a good job of balancing work across available workers, yielding reasonable results across a wide range of hardware. [4]

When the source data is split into two, each node in the computation tree corresponds to a binary split, forming a binary tree. Ideally, this tree would be balanced — with each leaf node representing exactly the same amount of work. This ideal is not achievable in practice, but some sources come much closer than others. Arrays are the best case. We can describe a segment of an array by using a reference to the array base and integral offsets of the start and end of the segment. The cost of splitting this segment into two equal segments is cheap: We compute the midpoint of the segment, create a new descriptor for the first half, and move the starting index for the current segment to the first element in the in the second half [5].

The invokeAll() method is the most convenient way to submit a sequence of ForkJoinTasks to the ForkJoinPool. It takes tasks as parameters (two tasks, var args, or a collection), forks them returns a collection of Future objects in the order in which they were produced [2].

Benchmark Results

Here’s the benchmark of Multi threaded merge sort implemented using fork-join approach against the imperative naive approach suitable for mono core CPUs. I have chosen a large array of size 108 elements. To sort such an array Multi threaded fork-join based approach takes 2828 milliseconds on my machine. The same input array takes 9339 milliseconds to be sorted using the sequential counterpart on my machine. Also notice that here on my machine refers to a core i7 which has 4 physical cores and 4 logical cores.


Conclusion

Use fork-join approach only if you need to solve extremely large computational problems while leveraging multi core CPU architecture. If you have several thousands of elements to sort, it is counter intuitive to use this approach. For an instance Oracle tutorial [1], gives a nice example of blurring an image while representing it as an array of pixels. For a smaller problem, imperative approach may be suitable and sometimes outperforms the fork-join approach because of the startup costs imposed by parallel execution.


References

[1] https://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html
[2] http://www.baeldung.com/java-fork-join
[3] https://www.ibm.com/developerworks/java/library/j-java-streams-4-brian-goetz/index.html?ca=drs-
[4] https://www.ibm.com/developerworks/java/library/j-jtp03048/
[5] https://www.ibm.com/developerworks/java/library/j-java-streams-5-brian-goetz/index.html?ca=drs-

Comments

Post a Comment

Popular posts from this blog

Introducing Java Reactive Extentions in to a SpringBoot Micro Service

Image
Introduction Today we are going to take a look at Reactive Programming using Java8 and RxJava, which is a library for composing asynchronous and event-based programs by using observable sequences. RxJava stands for Reactive Extensions for the JVM. It extends the observer pattern [Gamma95] to support sequences of data/events and adds operators that allow you to compose sequences together declaratively while abstracting away concerns about things like low-level threading, synchronization, thread-safety and concurrent data structures [1]. Pre-Requisites : Having a good knowledge about Java8, Functional Programming and spring boot microservices. What is Reactive programming? In essence, Reactive programming is an asynchronous programming paradigm concerned with data streams. The system time, a list of entries from the DB/API, user clicks, everything can be a stream of data. Data from different streams can easily be combined and transformed, and in the end processed/observed by the
Read more

Optimal binary search trees

Image
Suppose that we are designing a program to translate text from English to French. For each occurrence of each English word in the text, we need to look up its French equivalent. We could perform these lookup operations by building a binary search tree with $n$ English words as keys and their French equivalents as satellite data. Because we will search the tree for each individual word in the text, we want the total time spent searching to be as low as possible. We could ensure an $Θ(log_2 \;n)$ search time per occurrence by using a red-black tree or any other balanced binary search tree. Words appear with different frequencies, however, and a frequently used word such as the may appear far from the root while a rarely used word appears near the root. Such an organization would slow down the translation, since the number of nodes visited when searching for a key in a binary search tree equals one plus the depth of the node containing the key. We want words that occur frequently in the t
Read more

Edit distance

Image
Biological applications often need to compare the DNA of two (or more) different organisms. A strand of DNA consists of a string of molecules called bases, where the possible bases are adenine, guanine, cytosine, and thymine. Representing each of these bases by its initial letter, we can express a strand of DNA as a string over the finite set $\{A, C, G, T\}$. For example, the DNA of one organism may be $S1 = ACCGGTCGAGTGCGCGGAAGCCGGCCGAA$, and the DNA of another organism may be $S2 = GTCGTTCGGAATGCCGTTGCTCTGTAAA$. One reason to compare two strands of DNA is to determine how “similar” the two strands are, as some measure of how closely related the two organisms are. We can, and do, define similarity in many different ways. For example, we can say that two strands are similar if the number of changes needed to turn one into the other is small. [1] We formalize this notion of similarity in our Edit distance problem. 15-5 Edit distance - Problem Statement In order to transform one sour
Read more