Java8中新引入的arrays.ParallelPrefix(…)是如何工作的？

Question

我遇到了Java8中引入的arrays.ParallelPrefix。

这个重载的方法以累加的方式对输入数组的每个元素执行操作。对于例如来自文档：

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

那么，当对一个术语的操作依赖于对前一个术语的操作结果时，Java是如何在parallex中实现这一任务的，以此类推？

Answer 1

正如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  

我们看到将有一个明显的好处，即使我们使用更简单的策略，即在两个步骤中保持工作块相同，换句话说，在第二阶段中接受一个空闲的工作者线程。第一个阶段大约需要1·n，第二个阶段需要1·n，操作需要1/4 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  

只有重新分配第二阶段的工作，我们才能获得一个好处。如前所述，这是可能的，因为第二阶段的工作不再有元素之间的依赖关系。因此我们可以任意地拆分这个操作，尽管它会使实现复杂化并可能引入额外的开销。

当我们将第二阶段的工作分配给两个处理器时，第一阶段大约需要1/2N，第二阶段需要1/4N，总共需要3/N。如果阵列足够大，这仍然是一个好处。

另外一个注意事项是，您可能会注意到在准备第二阶段时计算的偏移量与块的最后一个元素的结果是相同的。因此，您可以通过简单地分配该值，将每个块所需的操作数减少一个。但典型的场景是只有几个包含大量元素的块（随处理器的数量缩放），因此为每个块节省一个操作是不相关的。