在Java理论和实践的最后一部分中 ，我们研究了fork-join库，该库将被添加到Java 7中的java.util.concurrent包中。Fork-join是一种可以轻松表达分而合一的技术。以允许在各种硬件上高效执行而无需更改代码的方式征服并行算法。
为了随着处理器数量的增加有效地利用可用的硬件，我们将不得不在程序中识别和利用更细粒度的并行性。 近年来，选择粗粒度的任务边界（例如在Web应用程序中处理单个请求）并在线程池中执行任务通常可提供足够的并行度，以实现可接受的硬件利用率。 但是，展望未来，我们将不得不更深入地研究以找到足够的并行度以保持硬件繁忙。 并行化的一个成熟领域是对大型数据集进行排序和搜索。 如上一部分中所述，使用fork-join可以轻松表达此类问题。 但是由于这些问题非常普遍，因此类库提供了一种更简单的方法ParallelArray 。
分叉体现了分而治之的技术。 解决一个问题并将其递归分解为子问题，直到子问题足够小，可以依次有效地解决它们。 递归步骤涉及将问题分为两个或多个子问题，将子问题排队以进行求解（ 派生步骤），等待子问题的结果（ 连接步骤），然后合并结果。 这种算法的一个示例是使用fork-join库的合并排序，如清单1所示：
合并排序不是固有的并行算法，因为它可以顺序执行，并且在数据集太大而无法放入内存且必须分段时很流行。 合并排序具有O（n log n）最坏情况和平均情况的性能。 但是，由于合并很难在原地完成，因此与快速排序等就地排序算法相比，它具有更高的内存要求。 但是，因为子问题的排序可以并行进行，所以它比快速排序更好地并行化。
在给定数量的处理器的情况下，并行化仍然无法将O（n log n）问题转化为O（n）问题，但是对并行化问题的解决越容易，并行化就可以使系数接近n cpus 。减少总运行时间。 减少总运行时间意味着用户可以更快地获得结果，即使并行执行工作所花费的总CPU周期比顺序进行的花费更多。
使用fork-join技术的主要好处是，它为并行执行提供了一种可移植的编码算法方法。 程序员不必知道部署中将有多少个CPU。 运行时可以很好地平衡可用工作者之间的工作，并在各种硬件上产生合理的结果。
在主流服务器应用程序中，最细粒度的并行性最易于访问（也是替代）的来源是数据集的排序，搜索，选择和汇总。 使用分而治之，这些问题中的每一个都可以轻松并行化，并且可以轻松地表示为fork-join任务。 例如，要并行处理大型数据集的平均值，您可以将其递归分解为较小的数据集（如在合并排序中所做的那样），以对子集求平均值，而合并步骤仅计算平均值的加权平均值。子集。
对于排序和搜索问题，fork-join库为您提供了一种更轻松的方式来表示数据集上可并行化的操作： ParallelArray类。 这个想法是， ParallelArray表示结构上相似的数据项的集合，并且您可以使用ParallelArray上的方法来创建有关如何对数据进行切片和切块的描述。 然后，您可以使用该描述实际并行执行数组操作（在后台使用fork-join框架）。 这种方法的效果是让您以声明方式指定数据选择，转换和后处理操作，并让框架找出合理的并行执行计划，就像数据库系统允许您在SQL中指定数据操作并隐藏其机制一样。如何执行操作。 ParallelArray几种实现可用于不同的数据类型和大小，包括对象数组和各种原语数组。
清单2显示了一个使用ParallelArray汇总学生成绩的示例，说明了选择，投影和汇总的基本操作。 Student班包含有关学生的信息（姓名，毕业年份，GPA）。 辅助对象isSenior用于仅选择今年毕业的学生，辅助对象getGpa从给定的学生中提取GPA字段。 列表开头的表达式创建了一个ParallelArray代表一组学生，然后使用它从今年应届毕业生中选择最佳GPA。
用于在并行数组上表达操作的代码具有欺骗性。 withFilter()和withMapping()方法实际上并不搜索或转换数据。 他们只是设置“查询”的参数。 实际工作在最后一步（在本例中为对max()的调用max() 。
ParallelArray支持的基本操作如下：
过滤：选择要包含在计算中的元素子集。 在清单2中，使用withFilter()方法指定了过滤器。 应用：对每个选定元素应用一个过程。 清单2没有显示这种技术，但是apply()方法允许您对每个选定的元素执行操作。 映射：将选定的元素转换为另一种形式（例如，从元素中提取数据字段）。 此转换在示例中通过withMapping()方法完成，在该方法中，我们将Student转换为学生的GPA。 结果是指定选择和映射结果的ParallelArray 。 替换：通过将每个元素替换为其派生的另一个元素来创建新的并行数组。 该技术类似于映射，但是会产生一个新的ParallelArray ，可以在其上执行进一步的查询。 替换的一种情况是排序，其中用不同的元素替换元素，以使结果数组按排序顺序进行（此操作提供了内置的sort()方法）。 另一个特殊情况是cumulate()方法，该方法根据指定的组合操作用运行中的累加替换每个元素。 替换还可以用于组合多个ParallelArray ，例如创建一个ParallelArray其元素是并行数组a和b的a[i]+b[i]的值。 汇总：将所有值组合为一个值，例如计算总和，平均值，最小值或最大值。 清单2中的示例使用max()方法。 使用更通用的reduce()方法构建了预定义的汇总方法，例如min() ， sum()和max() 。在清单2中 ，我们可以指定所有学生的最高GPA的计算，但是我们可能想要的是稍有不同的-哪个学生的GPA最高。 可以使用两种计算来完成此计算（一种计算最高的GPA，另一种选择具有该GPA的学生），但是ParallelArray提供了一种更容易的方法来获取通常所需的汇总统计信息，例如最大值，最小值，总和，平均值，以及最大和最小元素的索引。 summary()方法在单个并行操作中计算这些摘要统计信息。
清单3显示了summary()方法，该方法计算摘要统计信息，其中包括最小和最大元素的索引，以避免必须对数据进行多次传递：
ParallelArray既不是旨在用作通用内存数据库，也不是用于指定数据转换和提取的通用机制（例如，.NET 3.0中的语言集成查询LinQ）。 它仅旨在简化特定范围的数据选择和转换操作的表达，以便可以轻松，自动地并行化它们。 因此，它有几个局限性。 例如，必须在映射操作之前指定过滤器操作。 （虽然可以将多个过滤操作组合成一个复合过滤操作通常更为有效。但它的主要目的是使开发人员不必考虑如何并行化工作； 如果您可以根据ParallelArray提供的操作来表示转换，则应该毫不费力地获得合理的并行化。
为了评估ParallelArray的有效性，我编写了一个简单，不科学的程序，该程序针对各种大小的数组池和fork-join池运行查询。 结果在运行Windows的Core 2 Quad系统上运行。 表1显示了相对于基本案例（1000个学生，一个线程）的加速：
尽管结果相当嘈杂（受包括GC活动在内的多种因素所影响），但您可以看到，池大小等于可用核心数时，不仅获得了最佳结果（鉴于任务是完全受计算限制的），但与四个内核相比，我们在四个内核上的速度提高了2-3倍，这表明可以使用高级可移植机制在不进行调整的情况下获得合理的并行性。
ParallelArray提供了一种很好的方式来声明性地指定对数据集的过滤，处理和聚合操作，同时还促进了自动并行化。 但是，尽管语法比使用原始的fork-join库更易于表达，但语法仍然有些麻烦。 每个过滤器，映射器和简化器通常都指定为一个内部类，因此诸如“找到今年应届毕业生中最高的GPA”之类的简单查询仍然需要十几行代码。 在Java 7中添加Java语言的一种可能性是闭包。 支持闭包的理由之一是，它使表达小的代码片段（如ParallelArray过滤器，映射器和reducers）更加紧凑。
清单4显示了使用BGGA闭包建议重写的max-GPA查询。 （在使用函数类型扩展的ParallelArray版本中， withFilter()的参数类型不是Ops.Predicate<T> ，而是函数类型{ T => boolean } 。）闭包标记剥离了相关联的样板使用内部类，可以更紧凑（更重要的是，更直接）表示所需的数据操作。 现在，代码减少到三行，几乎所有代码都表达了我们试图实现的结果的一些重要方面。
随着可用处理器数量的增加，我们将需要在程序中找到更细粒度的并行性源。 聚合数据操作是最吸引人的候选方法之一-排序，搜索和汇总。 将在JDK 7中引入的fork-join库提供了一种“可移植地表达”某种类别的可并行化算法的方法，以便该程序可以在多种硬件平台上高效运行。 fork-join库的ParallelArray组件通过声明性地描述您要执行的操作并让ParallelArray找出如何有效执行它，可以使表达并行聚合操作更加容易。
翻译自: https://www.ibm.com/developerworks/java/library/j-jtp03048/index.html
相关资源：25个经典网站源代码