MULTITHREADING AND PARALLEL PROGRAMMING - Introduction to Java Programming: Comprehensive Version - page 1130

ForkJoinTask is the abstract base class for tasks. A ForkJoinTask is a thread-like
entity, but it is much lighter than a normal thread because huge numbers of tasks and sub-
tasks can be executed by a small number of actual threads in a ForkJoinPool . The tasks are
primarily coordinated using fork() and join() . Invoking fork() on a task arranges asyn-
chronous execution, and invoking join() waits until the task is completed. The invoke()
and invokeAll(tasks) methods implicitly invoke fork() to execute the task and join()
to wait for the tasks to complete, and return the result, if any. Note that the static method
invokeAll takes a variable number of ForkJoinTask arguments using the ... syntax,
which is introduced in Section 7.9.
The Fork/Join Framework is designed to parallelize divide-and-conquer solutions, which
are naturally recursive. RecursiveAction and RecursiveTask are two subclasses of
ForkJoinTask . To define a concrete task class, your class should extend RecursiveAction
or RecursiveTask . RecursiveAction is for a task that doesn't return a value, and
RecursiveTask is for a task that does return a value. Your task class should override the
compute() method to specify how a task is performed.
We now use a merge sort to demonstrate how to develop parallel programs using the Fork/
Join Framework. The merge sort algorithm (introduced in Section 25.3) divides the array into
two halves and applies a merge sort on each half recursively. After the two halves are sorted,
the algorithm merges them. Listing 30.10 gives a parallel implementation of the merge sort
algorithm and compares its execution time with a sequential sort.

RecursiveAction
RecursiveTask

L ISTING 30.10

ParallelMergeSort.java
1 import java.util.concurrent.RecursiveAction;
2 import java.util.concurrent.ForkJoinPool;
3
4 public class ParallelMergeSort {
5 public static void main(String[] args) {

6 final int SIZE = 7000000 ;

7 int [] list1 = new int [SIZE];

8 int [] list2 = new int [SIZE];

9
10 for ( int i = 0 ; i < list1.length; i++)
11 list1[i] = list2[i] = ( int )(Math.random() * 10000000 );
12
13 long startTime = System.currentTimeMillis();
14 parallelMergeSort(list1); // Invoke parallel merge sort
15 long endTime = System.currentTimeMillis();
16 System.out.println( "\nParallel time with "
17 + Runtime.getRuntime().availableProcessors() +
18

invoke parallel sort

" processors is " + (endTime - startTime) + " milliseconds" );

19
20 startTime = System.currentTimeMillis();
21 MergeSort.mergeSort(list2); // MergeSort is in Listing 23.5
22 endTime = System.currentTimeMillis();
23 System.out.println( "\nSequential time is " +
24 (endTime - startTime) + " milliseconds" );
25 }
26
27

invoke sequential sort

public static void parallelMergeSort( int [] list) {

28 RecursiveAction mainTask = new SortTask(list); create a ForkJoinTask

create a ForkJoinPool
execute a task

29 ForkJoinPool pool = new ForkJoinPool();

30 pool.invoke(mainTask);

31 }
32
33 private static class SortTask extends RecursiveAction { define concrete

ForkJoinTask

34 private final int THRESHOLD = 500 ;