Java Reference
In-Depth Information
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
;
Search WWH ::
Custom Search