Tuesday 21 July 2015

Java: Fork Join framework

Fork Join frame work works on the principle of divide and conquer. Fork join framework recursively divide the tasks into small sub tasks, and then combine the result of subtasks to get final result.

Following are the two steps involved in using fork join framework.

1.   First we need to define a recursive task by extending RecursiveTask class.
2.   Submit task to ForkJoinPool.

Before going to explain application using ForkJoinPool, I want to explain fork join framework.

Fork
Fork split the tasks into subtasks, which can be executed parallel. Usually each subtask is executed by separate thread.

Join
When a task split itself up into subtasks, the task waits until the subtasks have finished executing. Once the task finished execution, result is merged with all sub tasks.
ForkJoinPool
It is a special thread pool, designed to work with fork join framework. You can execute given task using invoke method.

Following application computes sum of  numbers in array using Fprk join framework.
import java.util.concurrent.RecursiveTask;

public class SumCalculator extends RecursiveTask<Long> {
 long[] input;
 int start;
 int end;
 int tasksize = 10000;

 SumCalculator(long[] numbers) {
  this.input = numbers;
  this.start = 0;
  this.end = numbers.length - 1;
 }

 SumCalculator(long[] numbers, int start, int end) {
  this.input = numbers;
  this.start = start;
  this.end = end;
 }

 @Override
 protected Long compute() {
  int length = end - start;
  if (length < tasksize) {
   return computeSequentially();
  }

  SumCalculator leftTask = new SumCalculator(input, start, start + length
    / 2);
  leftTask.fork();

  SumCalculator rightTask = new SumCalculator(input, start + length / 2,
    end);
  rightTask.fork();

  long leftResult = leftTask.join();
  long rightResult = rightTask.join();

  return leftResult + rightResult;
 }

 public long computeSequentially() {
  long sum = 0;
  for (int i = start; i < end; i++) {
   sum = sum + input[i];
  }
  return sum;
 }

}


import java.util.concurrent.ForkJoinPool;
import java.util.stream.LongStream;

public class ForkJoinEx {
 public static long forkJoinSum(long n) {
  long[] input = LongStream.rangeClosed(1, n).toArray();
  SumCalculator task = new SumCalculator(input);
  return new ForkJoinPool().invoke(task);
 }

 public static void main(String args[]) {
  System.out.println(forkJoinSum(1000000));
 }
}


Output

499999500000


Prevoius                                                 Next                                                 Home

No comments:

Post a Comment