技术开发 频道

应用 fork-join 框架

  Divide and conquer

  合并排序是 divide-and-conquer 算法的一个例子,在这种算法中将一个问题递归分解成子问题,再将子问题的解决方案组合得到最终结果。 divide-and-conquer 算法也可用于顺序环境中,但是在并行环境中更加有效,因为可以并行处理子问题。

  典型的并行 divide-and-conquer 算法的形式如清单 1 所示:

  清单 1. 通用 divide-and-conquer 并行算法的伪代码。

 // PSEUDOCODE

  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. 从大型数组中选择最大元素

public class SelectMaxProblem {

  
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)。

0
相关文章