归约

归约需要一个可以在常量时间内被评估的，可结合的(但不一定可交换的)运算符  ，和包含  个向量且每个向量有  个元素的输入集合  ，即:  。整个归约操作的结果是所有这些元素的组合，这里标识为  ，即   ，且在执行结束时必须要被存储到指定的根处理器中。例如:  这个集合归约以后，所有向量会组合成为一个向量，最后向量值为:  。在计算完成后将最后结果   在每个处理器上都有效的过程，我们通常称为“Allreduce”。归约的最优串行线性时间算法可以是从前到后依次应用运算符，即一直用前一次的运算结果与下一个向量进行运算，最终需要  次运算获得最终结果  。由此可见，串行算法的时间复杂度是不可能低于线性时间的。然而并行算法在这方面有很大的优化空间。

关于并行算法，有两种主要的并行计算模型， 并行随机存取计算（PRAM）和 整体同步并行计算（BSP）。前者使用不同处理器之间扩展出来的共享内存进行存储，而后者使用分布式存储，需要将数据通讯和同步考虑在内。并且两种模型有着不同的时间复杂度。

2.1 PRAM算法

该算法是一种被广泛用于处理有二次幂个输入元素  的方法。其反向过程通常可被用于这些元素的数据广播。^[1][2][3]

for   to   do

for   to   do (并行)

if  是活动的 then

if  的第  个比特位已设置 then

设置   为非活动的

else if  

根据以上伪代码的描述，在整体开始之前会假设所有的  ，相当于元素的初始化。其中  必须是二次幂，且会用于标识各个处理单元  。相应向量的二元运算符的运用可理解为  。该算法的每一次迭代中，一半的处理单元将会变得不再运作，对进一步的计算没有更多的贡献。上面的动画演示了该算法使用加法作为运算符的执行过程。垂直线代表该处理单元上不同的元素的运算。八个输入元素位于底部，每个动画步骤对应于算法执行中的一个并行步骤。每一个运作的处理器  会通过给定的运算符  计算相关的两个元素（  和  ）。其中  是该处理单元自身所持有的，另一个  来自另一个处理单元，且  需要是满足  这个条件的最小的值。当前运算执行之后   会进入非活动状态。   和   不一定是输入集合  中的元素，因为这些元素会由于之前的执行而被覆盖并重用。每个处理单元使用   到  做为其数字索引，这样可以协调每个处理单元在每个步骤中的职能，避免彼此之间的额外通讯。每个处理器通过查看其第  个比特位(最低有效位)，来决定是进入非活动状态，还是执行相应的元素运算操作。该算法的底层通信模式就是这种二叉树，因此称为二叉树算法。

由于只有  具有最后的结果，因此称它为根处理器。对于一个"Allreduce"的操作，这个最后结果必须通过在  上附加一个广播操作来完成分发。此外，处理器的数量  被限制必须为二次幂。所以处理器数量的增长也必须是二次幂的方式来增加。对于这样的情况，还有一些其他算法会更加合适。^[4]

运行时分析

这个算法主循环会被执行   次。由于处理单元可能被复用或者进入非活动状态，在并行执行时，一个处理单元所需的时间可以表示为  。因此PRAM算法的整体并行时间为  。在选择处理读写冲突的策略时，可以选择与独占读写(EREW)一样严格的策略。整个算法的执行效率是   ，由此单个处理单元的效率是  。因为在每个步骤之后，一半的活动的处理单元会成不活动状态，所以整体运行效率并不高，仅有  个处理单元在步骤  后处于活动状态 。

2.2 分布式存储算法

与PRAM算法相反。在分布式存储模型中，内存不是在处理单元之间共享的。各个元素数据必须在处理单元之间进行显式交换，从而导致数据通信的开销。以下算法考虑了这一点。

for   to   do

for   to   do (并行)

if  是活动的 then

if  的第  个比特位已设置 then

发送  到  

设置   为非活动的

else if  

接收  

在分布式算法和PRAM算法之间，数据的操作原则是一样的，唯一区别是后者需要包含显式的通信原语。

运行时分析

一种简单分析该算法的方法是，使用了整体同步并行计算(BSP)模型，同时结合初始化元素数据所需的时间  和发送一个字节所需要的时间  。因此该算法的结果运行时间复杂度是  ，其中  是每次迭代时所需发送的相应向量的   个元素的大小总和。

对于分布式内存模型，使用流水线通信则是相当必要的。尤其是   比  小的情况下。线性流水线 将数据或任务分割成小块，并分阶段处理。与二叉树算法不同，流水线算法使用的向量不是不可分的，除非相应运算符可以对单个元素进行运算操作:^[5]

for   to   do

for   to   do (并行)

if  

发送   到  

if  

接收   来自  

需要注意的是，该算法中发送和接收操作必须同步执行。最后的结果会存储在  中。上面的动画演示了在五个处理单元中，进行四元向量加法的执行过程。动画的两个步骤相当于并行执行的一个步骤。并行执行的步骤总数为  ，其中第  步后，最后一个处理单元接收到第一个元素，然后再  步，接收到所有所需元素。因此，BSP模型中的运行时间复杂度是  ，这里  是一个向量的字节大小总和。

尽管   是固定值，仍然可以通过逻辑分组将这些向量元素合并在一起以减少  。例如，一个四元向量可以通过将向量分成前两个和后两个元素来处理，这两个元素会一起传输和计算。在这种情况下，每一步发送的数据量都是原来的两倍，但是步数却减少了大约一半。这意味着参数  减半，而总字节大小  保持不变。对应的运行时间复杂度   则直接依赖于  ，并且在   和   已知的情况下可以进行优化。假设有较小的  可以从原来划分出来，其中最优的情况是  。

二叉树和流水线各有利弊，对于并行通讯而言，取决于   和   。二叉树算法更适合少量的向量，流水线算法则受益于分布式的元素部署，使用更少的处理单元，并且处理单元中的每一个向量可以包含更多的元素。这两种方法组合则是流水线树算法^[6] ，即使用树作为其底层通信模式，并同时将运算符的计算拆分成多个部分。不同于二叉树， 斐波那契树的高度是以两个或一个子树为根搭建而成。它有助于平衡所有处理单元的负载，因为虽然每个单元在针对其中一个元素进行迭代时，只能进行一次运算符运算，但是它有两个子处理单元接收相应的值。

4.1 算法描述

侧边动画显示了在全双工的通讯模式下的斐波那契树的流水线算法。其中通信链路由元素向量之间的黑线表示，并构建了一个大小为7的斐波那契树。如果一个元素被发送到另一个处理单元，链接则会使用相应元素的颜色表示。处理器接收到的元素被加到已经存在的相同颜色的元素中(即向量中的相同索引处)。

这个算法按照从下向上的顺序传播运算的结果，直到所有元素都组合到顶部根处理器中。在执行的第一步，底层树中的叶子处理单元将它们的第一个元素发送给它们的父元素。这类似于二叉树算法的发送操作，其关键区别在于每个具有两个或以上元素的叶子单元都必须要发送。因此这些单元不会进入非活动状态，而是可以继续发送元素。这类似于流水线的方式，提高了效率。非叶子的处理单元一旦从子单元接收到元素，就开始按照向量中的索引顺序发送它们的元素。在本例中，他们按照绿色、蓝色和红色的顺序发送元素。如果两个处理器需要将它们的元素发送到同一个处理器，那么右边的子单元的元素会被优先处理。由于使用斐波那契树的结构，在流水线被填充时,所有处理单元可以同时发送或接收元素。整个流水线是从各个单元接收到第一个元素开始，直到叶子单元不再有要发送的元素结束。

4.2 运行时间

这个算法的每次迭代最多花费时间为  。树的高度会影响填充流水线所需要的时间，对于斐波那契树来说，填充时间是已知的，即  。并且当   时达到最优效率。一旦流水线被填满，在每个步骤中，所有处理器都是有效的。由于内部节点有两个子节点，所以它们必须接收   个元素。从而整体算法的运行时间复杂度是  。如果单个向量的元素数量  ，算法的时间复杂度达到最小值。

归约是主要的全局数据操作之一，通过消息传递接口实现，其中所用算法的性能非常重要，同时针对不同的实际用例需要不断进行评估。^[7]

MapReduce 的使用就高度依赖于高效的归约算法来处理大数据集，尤其是大型数据集群。^[8][9]

一些并行排序算法也会使用归约来处理非常大的数据集。^[10]