我发现了在Java 8中引入的Arrays.parallePrefix。
这种重载方法以累积的方式对输入数组的每个元素执行操作。例如，来自文档：
并行地累积给定数组的每个元素，使用所提供的功能。例如，如果数组最初保持[2，1，0，3]，并且操作执行加法，然后在返回数组保持[2，3，3，6]。并行前缀计算通常更多对于大型阵列，比顺序循环更有效。
那么，当对一个术语的运算取决于对上一术语的运算结果时，Java如何在parallel中实现这项任务，以此类推？
我试着自己浏览代码，他们确实使用了ForkJoinTasks，但他们如何合并结果以获得最终数组并不那么简单。
要点是操作员是
无副作用，关联功能
这意味着
(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实现所使用的方法。您可以在这里进一步阅读有关解决该问题的并行算法。
正如Eran的回答中所解释的，此操作利用了函数的关联性属性。
然后，有两个基本步骤。第一个是实际的前缀操作(在需要前面的元素进行评估的意义上)，并行应用于数组的各个部分。每个部分运算的结果(与最后一个元素相同)是剩余数组的偏移量。
例如，对于以下数组，使用和作为前缀操作，以及四个处理器
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
我们看到，即使我们使用更简单的策略来保持两个步骤的工作块相同，也会有明显的好处，换句话说，在第二阶段接受一个空闲的工作线程。我们需要大约⅛n表示第一阶段，以及⅛第二个是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，如果阵列足够大，这仍然是一个好处。
另外，您可能会注意到，在准备第二阶段时计算的偏移量与块的最后一个元素的结果相同。因此，您可以通过简单地分配该值，将每个区块所需的操作数量减少一个。但典型的场景是只有几个块(随着处理器的数量而扩展)和大量的元素，因此每个块保存一个操作是不相关的。
我读了这两个答案，仍然不能完全理解是如何做到的，所以决定画一个例子。以下是我想到的，假设这是我们开始使用的阵列(有3个CPU)：
7, 9, 6, 1, 8, 7, 3, 4, 9
因此，这3个线程中的每一个都将获得要处理的块：
Thread 1: 7, 9, 6
Thread 2: 1, 8, 7
Thread 3: 3, 4, 9
由于文档要求使用关联函数，我们可以在第一个线程中计算和，在其他线程中计算部分和，当第一个线程已知时，所有线程都会计算。让我们看看7, 9, 6会变成什么：
7, 9, 6 -> 7, 16, 22
因此，第一个线程中的总和是22，但其他线程还不知道这一点，所以他们所做的是作为x来对抗它。因此线程2将是：
1, 8, 7 -> 1 (+x), 9 (+x), 16(+x)
因此，来自第二个线程的和将是x + 16，因此在Thread 3中，我们将有：
3, 4, 9 -> 3 (+ x + 16), 7 (+ x + 16), 16 (+ x + 16)
3, 4, 9 -> x + 19, x + 23, x + 32
这样，只要我知道x，我就知道所有其他结果。
免责声明：我不确定它是如何实现的(我试着看了一下代码，但它太复杂了)。