Java 8中新引入的Arrays.parallelPrefix(...)如何工作？

Question

我遇到了Java 8中引入的Arrays.parallelPrefix.

此重载方法以累积方式对输入数组的每个元素执行操作.例如来自docs:

使用提供的函数并行地累积给定数组的每个元素.例如,如果数组最初保持[2,1,0,3]并且操作执行加法,则在返回时数组保持[2,3,3,6].对于大型数组,并行前缀计算通常比顺序循环更有效.

那么,parallel当一个术语的操作依赖于前一个术语的操作结果时,Java如何实现这个任务,等等？

我尝试自己完成代码并且他们确实使用了ForkJoinTasks,但是它们如何合并结果以获得最终数组并不是那么简单.

Answer 1

重点是运营商是一个

无副作用的联想功能

这意味着

(a op b) op c == a op (b op c)

因此,如果将数组拆分为两半并parallelPrefix在每一半上递归应用该方法,则稍后可以通过对数组后半部分的每个元素应用对上半部分的最后一个元素的操作来合并部分结果.

考虑[2, 1, 0, 3]附加示例.如果将阵列分成两半并对每一半执行操作,则会得到:

[2, 3]    and    [0, 3]

然后,为了合并它们,你将3(前半部分的最后一个元素)添加到后半部分的每个元素,并得到:

[2, 3, 3, 6]

编辑:这个答案提出了一种并行计算数组前缀的方法.它不一定是最有效的方式,也不一定是JDK实现使用的方式.您可以在此处进一步阅读有关解决该问题的并行算法.

Answer 2

正如Eran的回答所解释的,此操作利用了函数的关联性.

然后,有两个基本步骤.第一个是实际的前缀操作(在需要用于评估的前一个元素的意义上),并行地应用于阵列的部分.每个部分操作的结果(与得到的最后一个元素相同)是剩余数组的偏移量.

例如,对于以下数组,使用sum作为前缀操作,以及四个处理器

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  

我们得到

  4 ? 13 ? 18 ? 19    0 ?  5 ?  6 ? 12    6 ? 10 ? 16 ? 21    1 ?  7 ? 16 ? 19  
                 ?                   ?                   ?                   ?  
                19                  12                  21                  19  

现在,我们利用关联性首先将前缀操作应用于偏移量

                 ?                   ?                   ?                   ?  
                19         ?        31         ?        52         ?        71  

然后,我们进入第二阶段,即将这些偏移应用于下一个块的每个元素,这是一个完全可并行化的操作,因为不再依赖于前一个元素

                     19   19   19   19   31   31   31   31   52   52   52   52  
                      ?    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

当我们对八个线程使用相同的示例时,

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  

  4 ? 13    5 ?  6    0 ?  5    1 ?  7    6 ? 10    6 ? 11    1 ?  7    9 ? 12  
       ?         ?         ?         ?         ?         ?         ?         ?  
      13         6         5         7        10        11         7        12  

       ?         ?         ?         ?         ?         ?         ?         ?  
      13    ?   19    ?   24    ?   31    ?   41    ?   52    ?   59    ?   71  

           13   13   19   19   24   24   31   31   41   41   52   52   59   59  
            ?    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?    ?  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

我们看到有一个明显的好处,即使我们使用更简单的策略来保持两个步骤的工作块相同,换句话说,在第二阶段接受一个空闲工作线程.我们将需要约为第一阶段的andn和第二阶段的⅛n,操作总共需要¼n(其中n是整个数组的顺序前缀评估的成本).当然,只有粗略和最好的情况.

相比之下,当我们只有两个处理器

  4    9    5    1    0    5    1    6    6    4    6    5    1    6    9    3  


  4 ? 13 ? 18 ? 19 ? 19 ? 24 ? 25 ? 31    6 ? 10 ? 16 ? 21 ? 22 ? 28 ? 37 ? 40  
                                     ?                                       ?  
                                    31                                      40  

                                     ?                                       ?  
                                    31                   ?                  71  

                                         31   31   31   31   31   31   31   31  
                                          ?    ?    ?    ?    ?    ?    ?    ?  
  4   13   18   19   19   24   25   31   37   41   47   52   53   59   68   71  

当我们重新分配第二阶段的工作时,我们只能获益.如上所述,这是可能的,因为第二阶段的工作不再具有元素之间的依赖关系.因此我们可以任意拆分此操作,但它会使实现复杂化并可能引入额外的开销.

当我们在两个处理器之间分配第二阶段的工作时,第一阶段需要大约½n而第二阶段需要¼n,总共产生n,如果阵列足够大,这仍然是一个好处.

作为补充说明,您可能会注意到在准备第二阶段时计算的偏移量与块的最后一个元素的结果相同.因此,您可以通过简单地分配该值,将每个块所需的操作数减少一个.但典型的情况是只有少量块(使用处理器数量进行扩展)具有大量元素,因此每个块保存一个操作是不相关的.