Parallel Programming in Java (Part – 1)

Hello all, A huge welcome to my new article, which is about making optimal use of the super machines that are available to run our systems in the current world. It is really awesome that the computing and storage costs have gone down so much and we are able to achieve tons of things at the minimal cost.But, its really important at the same time that we make use of the resources optimally and not waste them. If you all agree to this and thinking about how to achieve this please go on and read the full article.

Let’s start with a quote from the great Steve Jobs :

“The way the processor industry is going, is to add more and more cores, but nobody knows how to program those things. I mean, two, yeah; four, not really; eight, forget it.”

While it is really important to understand how to write code to make full use of the resources, however doing it from the very beginning is equally important. Redesigning your application to run multithreaded programs is like learning to open a parachute after getting dropped off a plane , both may lead to FATAL errors.

Let’s spend some time understanding the difference between “Sequential” , “Concurrent” and “Parallel” execution of tasks.

Imagine you have arranged your birthday party at home and called up all your friends, colleagues, relatives etc. A lot of people are expected to come and you don’t have a lot of time. You call up two of your close friends and ask them for help in preparing for the party!!! . Fortunately your friends are really nice to join you in the preparation and you plan to prepare PIZZAAAS!!

Constraints : You have only one of each kitchen resource (oven, heating plate etc).

Now in this case sequential execution will work as follows :

1. You go to the kitchen.
2. Prepare pizza.
3. Put it for around 30mins to bake.
4. Meanwhile you and your friend just wait until pizza is ready.
5. Once you are done your friend goes to the kitchen and prepare his own pizza with special ingredients.

You can clearly observe that it is not efficient because it is taking more time if you prepare one after the other.

Concurrent execution comes to the rescue here, where you implement this great idea of starting the preparation of pizza and pasta together and kind of share the kitchen resources like the oven.If your pizza is being baked , your friend will still wait, but would have completed rest of the pizza preparation.

Now this was way better than the previous sequential approach where you were just preparing food one after the other and meanwhile doing nothing.

Do you think you can do better ? Probably not, if you only have one of each kitchen resource. But suddenly your friend says, “Hey! we have few more pizzas to bake and the process is still slow with one oven, but I can bring my oven and prepare pizzas using both of them.” “Thats awesome!!, you say”.

Guess what, now they have two resources (ovens) and ready to do a parallel execution of the plan. Now they both can enter the kitchen use both the ovens and prepare pizza very quickly.

Finally you prepare all the pizza pretty fast and ready for the party 😀 . Btw, don’t forget to give a special treat to your friend who helped you by sharing his oven and also efforts.

After the wonderful party, lets get back to business and form an analogy between the above scenario and programming.

Pizza -> Task in hand (Any executable task in Java)

Oven -> Processors on your machine.

You and your friend -> Two threads working on two tasks in parallel, and using the resources optimally.

Hopefully now we are on the same page in terms of understanding the concept and the need of parallel programming.

If yes, let’s start with a basic Java program to calculate sum of all the numbers in a given list.Below code should just work perfectly :

int sumAllNumbers_Seq(int[] nums){
  int sum=0;
  for(int i=0;i<nums.length;i++){
      sum+= nums[i];
  }
  return sum;
}

The above code just takes an integer array as input and loops over every element adding it to a sum variable.It works perfectly fine. In fact, it is quite performant for smaller input size. This is an easy example of what sequential programming looks like.

What if the input size is ~100 ? Should be fine.

What if the input size is ~1000 ? Should be fine as well.Not much difference.

But, wait if this reaches millions or even more this will be very slow. So how to fix this ? You guessed it right – Parallel programming is the answer. Why ? Because it is recursive in nature and can be executed in smaller chunks that don’t depend on each other.

Fork Join Framework – Java

The fork/join framework implements the ExecutorService, and is really helpful in taking advantage of the multi-processor machines. It is important to note that it is well suited for solving problems that are recursive in nature and can be broken into smaller chunks. There are set of workers (threads) in the pool that are assigned tasks to work on.

Each worker work on their tasks and don’t hesitate in taking tasks from other workers if they are busy. (Work-Stealing algorithm).

ForkJoinPool is the class which implements this algorithm and is able to execute ForkJoinTask processes.

So, how to implement something that is able to execute tasks in parallel using this framework ? Continue reading..

Let me introduce two classes here

•  RecursiveTask – That returns a result
• RecursiveAction. – That doesn’t return anything.

To refactor the above example in a parallel execution manner lets create a task which is recursive in nature. compute() method needs to be implemented, where the main logic goes. In case it is RecursiveAction – compute() method will populate the result.

public class MyForkJoinAction extends RecursiveAction {
    @Override
    protected void compute() {

    }
}

Lets now extend its functionality to solve the sum-of-array problem above.

public class MyForkJoinAction extends RecursiveAction {

    private int[] arr; //input array. (chunk)
    private int start; //start index of the array
    private int end; //end index of the array

    private int result; //result of the compute method will be stored here.

    public MyForkJoinAction(args...){
      //dumb constructor.
    }

    @Override
    protected void compute() {
       if(start > end) {
         result = 0;
       }else if(start == end){
         result = arr[start];
       }else{
          int mid = (start + end) / 2;
          //Create recursive action for the left chunk
          MyForkJoinAction leftChunkAction = new MyForkJoinAction(arr,start,mid);
          leftChunkAction.fork(); //Fork a new thread for the left chunk.
          //Create recursive action for the left chunk
          MyForkJoinAction rightChunkAction = new MyForkJoinAction(arr,mid+1,end);
          rightChunkAction.compute(); //Call compute of the right chunk
          leftChunkAction.join(); //Call join on the left action
          //Combine the result of both the chunks
          result = leftChunkAction.result + rightChunkAction.result;
       }
    }
}

If you closely observe, you will figure out that at each step the action will create two more actions recursively which will operate on a smaller chunk of data.  

Now that we have created a RecursiveAction we can simply invoke this using a ForkJoinPool.

public static int invokeActions(int[] num){
   // some validation...
   int sum = 0;
   MyForkJoinAction myAction = new MyForkJoinAction(num,0,num.length);
   ForkJoinPool.commonPool().invoke(myAction);
   sum = myAction.getResult();
   return sum;
}

And you are done! You just created a recursive task which can execute in parallel using the multiple processors available in your machine.

Note : “You can do some optimisations by providing a threshold instead of going up to (start==end), for bigger inputs it can become a game changer to provide a threshold. If the input size goes below the threshold then just use sequential execution. Because creating worker threads have overhead which might not be worth for smaller inputs.“

Thanks for reading the article, I hope you liked it. Please post comments on any improvements, corrections , good wishes etc.

Things which will be covered in Part – 2 of this article :

• Solving above problem using Java Streams (Parallel).
• Barriers
• Phasers
• More examples.

Cheers,

Kaivalya Apte