Divide and conquer
合并排序是 divide-and-conquer 算法的一个例子,在这种算法中将一个问题递归分解成子问题,再将子问题的解决方案组合得到最终结果。 divide-and-conquer 算法也可用于顺序环境中,但是在并行环境中更加有效,因为可以并行处理子问题。
典型的并行 divide-and-conquer 算法的形式如清单 1 所示:
清单 1. 通用 divide-and-conquer 并行算法的伪代码。
Result solve(Problem problem) {
if (problem.size < SEQUENTIAL_THRESHOLD)
return solveSequentially(problem);
else {
Result left, right;
INVOKE-IN-PARALLEL {
left = solve(extractLeftHalf(problem));
right = solve(extractRightHalf(problem));
}
return combine(left, right);
}
}
并行 divide-and-conquer 算法首先对问题进行评估,确定其大小是否更适合使用顺序解决方案;通常,可通过将问题大小与某个阙值进行比较完成。如果问题大到需要并行分解,算法会将其分解成两个或更多子问题,并以并行方式对子问题递归调用算法本身,然后等待子问题的结果,最后合并这些结果。用于选择顺序和并行执行方法的理想阙值是协调并行任务的成本。如果协调成本为 0,更多的更细粒度的任务会提供更好的并行性;在需要转向顺序方法之前,协调成本越低,就可以划分更细粒度的任务。
Fork-join
清单 1 中的示例使用了实际上并不存在的 INVOKE-IN-PARALLEL 操作;它的行为表现为当前任务是暂停的,并行执行两个子任务,而当前任务等待两个子任务的完成。然后就可以将两个子任务的结果进行合并。这种并行分解方法常常称作 fork-join,因为执行一个任务将首先分解(fork)为多个子任务,然后再合并(join)(完成后)。
清单 2 显示了一个适合使用 fork-join 解决方案的问题示例:在大型数组中搜索其中的最大元素。虽然这个示例非常简单,但是 fork-join 技术可用于各种各样的搜索、排序和数据分析问题。
清单 2. 从大型数组中选择最大元素
private final int[] numbers;
private final int start;
private final int end;
public final int size;
// constructors elided
public int solveSequentially() {
int max = Integer.MIN_VALUE;
for (int i=start; i
int n = numbers[i];
if (n > max)
max = n;
}
return max;
}
public SelectMaxProblem subproblem(int subStart, int subEnd) {
return new SelectMaxProblem(numbers, start + subStart,
start + subEnd);
}
}
注意 subproblem() 方法没有复制这些元素;它只是将数组引用和偏移复制到一个现有的数据结构中。这在 fork-join 问题实现中很常见,因为递归分解问题的过程将会创建大量的新 Problem 对象。 在这个例子中,搜索任务没有修改被搜索的数据结构,因此不需要维护每个任务的底层数据集的私有副本,也不会因复制而增加额外的开销。
清单 3 演示了使用 fork-join 包的 SelectMaxProblem 解决方案,Java 7 中已计划包含该包。JSR 166 Expert Group 正在公开开发这个包,使用的代码名称为 jsr166y,您可以单独下载它并在 Java 6 或更高版本中使用(它最终将会包含在包 java.util.concurrent.forkjoin 中)。invoke-in-parallel 操作是用 coInvoke() 方法来实现的,该操作同时调用多个动作并等待所有动作完成。ForkJoinExecutor 跟 Executor 类似,因为它也是用来运行任务的,但它是专门针对计算密集型任务而设计的。这种任务不会被阻塞,除非它在等待由相同 ForkJoinExecutor 处理的另一个任务。
fork-join 框架支持几种风格的 ForkJoinTasks,包括那些需要显式完成的,以及需要循环执行的。这里使用的 RecursiveAction 类直接支持 non-result-bearing 任务的并行递归分解风格;RecursiveTask 类解决 result-bearing 任务的相同问题(其他 fork-join 任务类包括 CyclicAction、AsyncAction 和 LinkedAsyncAction;要获得关于如何使用它们的更多细节,请查阅 Javadoc)。