用于在数据通信网络中执行集合通信操作的装置、方法和计算机程序产品

摘要

本发明涉及数据处理领域，更具体地，涉及一种用于在数据通信网络中的多个计算节点上执行集合通信操作的方法、装置和计算机程序产品。具体地，所述集合通信操作是根据调度执行的，所述调度根据网络参数、进行所述集合通信操作的数据阵列的大小，以及构成所述数据阵列的数据项在所述计算节点上的分布确定。所述调度定义了所述集合通信操作所涉及的所述计算节点之间所述数据项的某些循环排列。因此，通过改变所述循环排列的数量，所述集合通信操作的执行适应所述网络参数和所述数据阵列的所述大小。

说明书

技术领域

本发明涉及数据处理领域，更具体地，涉及一种用于在数据通信网络中的多个计算节点上执行集合通信操作的方法、装置和计算机程序产品。

背景技术

高性能并行计算(high-performance parallel computing，HPPC)与使用多个计算节点或进程以更快或更高的准确度解决感兴趣的任务有关。具体地，HPPC基于以下事实：感兴趣的任务通常可以分为更小的子任务，这些子任务可以根据一些协调规则在多个计算节点上同时执行。计算节点的这种参与也称为集合通信操作，指多个计算节点在解决感兴趣的任务时相互通信。

为了执行集合通信操作，制定了不同的标准，包括消息传递接口标准(messagepassing interface，MPI)。通常，MPI为计算节点之间的通信提供了标准化的手段，支持点对点和集合通信。这种支持可以实现不同类型的集合通信操作，在这些集合通信操作中，Allreduce操作非常重要，因为已证明Allreduce操作是MPI中最常用的操作之一。

更具体地，Allreduce操作是所有计算节点的数据项被组合成一个结果，然后将结果分发回每个计算节点的集合通信操作。数据项的这种组合可以通过使用加法运算符、乘法运算符、最大运算符、最小运算符等特定运算符来执行，并且结果可以分别由所有数据项的总和、所有数据项的乘积、最大数据项、最小数据项等表示。

最近提出了许多不同的算法，以在不同的平台和网络架构上实现Allreduce操作。具体地，OpenMPI和MPICH标准是MPI标准的两种独立的实现，它们在执行Allreduce操作时需要使用两种算法，即递归倍增算法和环算法。但是，递归倍增算法和环算法存在以下缺点：前者对小数据项和数量是2的幂的计算节点是最优的，后者对大数据项是最优的，同时适用于任何数量的计算节点。因此，根据OpenMPI和MPICH标准，Allreduce操作的执行涉及根据数据项的大小和计算节点的数量在这两种算法之间切换，从而增加了Allreduce操作的执行时间。

Allreduce操作中使用的对大数据项最优的另一种算法是递归减半算法。但是，与递归倍增算法类似，递归减半算法只有在计算节点的数量是2的幂时才效果良好。

因此，仍然需要一种新的方案，可以减少甚至消除现有技术特有的上述缺点。

发明内容

发明内容简单介绍了一些概念，在具体实施方式中会进一步描述这些概念。发明内容并非旨在确定所要求保护的主题的关键特征或必要特征，也并非旨在用于限制所要求保护的主题的范围。

本发明的目的是提供一种最优的技术方案，用于对任何大小的数据项和任何数量的计算节点有效地执行集合通信操作。

上述目的通过所附权利要求书中独立权利要求的特征来实现。其它实施例和示例从从属权利要求、说明书和附图中显而易见。

根据第一方面，提供了一种在数据通信网络中执行集合通信操作的方法。所述方法从接收在所述集合通信操作中待使用的数据阵列开始。所述数据阵列包括数据项，并具有预定义的大小。所述方法还包括：获取所述数据项在所述计算节点上的分布；获取所述数据通信网络的网络参数；根据所述数据阵列的所述大小、所述网络参数和所述数据项的所述分布，确定所述集合通信操作的调度。所述方法以根据所述集合通信操作的所述调度对所述数据阵列执行所述集合通信操作结束。同时，所述数据项的所述分布和所述集合通信操作的所述调度都基于所述计算节点之间所述数据项的循环排列。从而通过改变所述循环排列的数量，使所述集合通信操作的执行适应所述网络参数和所述数据阵列的大小。

在第一方面的一种实现方式中，所述网络参数包括网络带宽和网络延迟。这些网络参数的使用使该方法可以同样适用于小数据项和大数据项。

在第一方面的一种实现方式中，所述数据通信网络是对等网络。这可以提高循环排列的效率，每个循环排列由计算节点之间数据项的点对点通信组成，因为由计算节点的单个对执行的点对点通信不会相互影响。

在第一方面的一种实现方式中，所述获取所述数据通信网络的所述网络参数包括：接收包括所述网络参数的用户输入；使用网络分析器实时计算所述网络参数；或从预先存储所述网络参数的存储器中检索所述网络参数。这可以实现方法的灵活使用。

在第一方面的一种实现方式中，所述集合通信操作包括Allreduce操作。这可以使该方法的使用更加灵活，因为它可以应用于依赖常用的Allreduce操作的多个HPPC应用程序。

在第一方面的一种实现方式中，所述Allreduce操作包括ReduceScatter操作和Allgather操作的组合。这可以简化Allreduce操作的执行。

在第一方面的一种实现方式中，所述Allreduce操作的调度中使用的所述循环排列的数量在

根据第二方面，提供了一种用于在包括多个计算节点的数据通信网络中执行集合通信操作的装置。所述装置包括至少一个处理器，以及与所述至少一个处理器耦合并存储计算机可执行指令的存储器。所述指令由所述至少一个处理器执行，使所述至少一个处理器接收在所述集合通信操作中待使用的数据阵列。所述数据阵列包括数据项，并具有预定义的大小。所述至少一个处理器还用于：获取所述数据项在所述计算节点上的分布；获取所述数据通信网络的网络参数；根据所述数据阵列的所述大小、所述网络参数和所述数据项的所述分布，确定所述集合通信操作的调度。所述至少一个处理器最终用于根据所述集合通信操作的所述调度对所述数据阵列执行所述集合通信操作。同时，所述数据项的所述分布和所述集合通信操作的所述调度都基于所述计算节点之间所述数据项的循环排列。从而通过改变所述循环排列的数量，使所述集合通信操作的执行适应所述网络参数和所述数据阵列的大小。

在第二方面的一种实现方式中，所述网络参数包括网络带宽和网络延迟。这些网络参数的使用使该方法可以同样适用于小数据项和大数据项。

在第二方面的一种实现方式中，所述数据通信网络是对等网络。这可以提高循环排列的效率，每个循环排列由计算节点之间数据项的点对点通信组成，因为由计算节点的单个对执行的点对点通信不会相互影响。

在第二方面的一种实现方式中，所述至少一个处理器用于通过以下方式获取所述数据通信网络的所述网络参数：接收包括所述网络参数的用户输入；从对所述网络参数进行实时计算的网络分析器接收所述网络参数；或从预先存储所述网络参数的所述存储器中检索所述网络参数。这可以实现装置的灵活使用。

在第二方面的一种实现方式中，所述集合通信操作包括Allreduce操作。这可以使该装置的使用更加灵活，因为它可以应用于依赖常用的Allreduce操作的多个HPPC应用程序。

在第二方面的一种实现方式中，所述Allreduce操作包括ReduceScatter操作和Allgather操作的组合。这可以简化Allreduce操作的执行。

在第二方面的一种实现方式中，所述Allreduce操作的调度中使用的所述循环排列的数量在

根据第三方面，提供了一种计算机程序产品，包括存储计算机程序的计算机可读存储介质。至少一个处理器执行所述计算机程序，使所述至少一个处理器执行根据第一方面所述的方法。因此，根据第一方面的方法可以以计算机程序的形式体现，从而提供了其使用的灵活性。

通过阅读以下详细描述并查阅附图，本发明的其它特征和优点是显而易见的。

附图说明

下面结合附图说明本发明的本质，其中：

图1-图6示出了现有技术已知的不同的集合通信操作；

图7示出了在每个集合通信操作中实现的点对点通信的说明性表示；

图8示出了通过使用递归倍增算法实现Allreduce操作的示例性调度；

图9示出了在环算法中使用的示例性对等网络拓扑；

图10示出了在环算法中实现的ReduceScatter操作的示例性调度；

图11示出了环算法中Allgather操作的示例性调度；

图12示出了在使用递归减半算法的情况下Allreduce操作的示例性调度；

图13示出了本发明的一个方面提供的用于在数据通信网络中执行集合通信操作的装置的框图；

图14示出了本发明的另一方面提供的用于在数据通信网络中执行集合通信操作的方法的框图；

图15示出了在图14的方法期间获取的每节点数据分布和基于排列的数据分布；

图16示出了在图14的方法中使用的循环排列的一些示例；

图17示出了用于获取基于排列的数据分布的基础数据分布的一个示例；

图18示出了Allreduce操作的带宽优化实现的调度；

图19解释了如何减少Allreduce操作的调度中使用的循环排列的数量；

图20解释了如何进一步减少Allreduce操作的调度中使用的循环排列的数量；

图21示出了Allreduce操作的延迟优化实现的调度；

图22示出了列出Allreduce操作的调度中使用的不同数量的循环排列的不同延迟-带宽比的表；

图23示出了列出Allreduce操作的调度中使用的循环排列的不同最优数的表；

图24示出了说明现有技术算法和图14的方法的比较的表；

图25-图28示出了使用OpenMPI标准和图14的方法获得的实验结果，考虑了两种不同的网络介质：Linux操作系统中的进程间通信和万兆以太网。

具体实施方式

结合附图进一步详细描述了本发明的各种实施例。但是，本发明可以以许多其它形式体现，并且不应解释为限于在以下描述中公开的任何特定结构或功能。相反，提供这些实施例是为了详细和完整地描述本发明。

根据本发明，对本领域技术人员显而易见的是，本发明的范围涵盖了本文公开的任何实施例，无论该实施例是独立实现的还是与本发明的任何其它实施例共同实现的。例如，本文公开的装置和方法可以通过使用本文提供的任何数量的实施例来实现。此外，应当理解，本发明的任何实施例都可以使用所附权利要求书中提出的一个或多个元件或步骤来实现。

本文使用的术语“集合通信操作”也简单地称为“集合通信”或“集合操作”，是指HPPC中数据以某种方式同时发送到多个计算节点或从多个计算节点接收的概念。换句话说，执行每个集合通信操作涉及计算节点的协作。每个集合通信操作由计算节点之间并发执行的多个点对点通信组成。

术语“计算节点”定义为参与作为集合通信操作一部分的特定点对点(或节点对节点)通信的模块。相应地，多个计算节点并行执行多个点对点通信，从而作为一个整体执行集合通信操作。需要说明的是，术语“计算节点”和“计算过程”在本发明所涉及的领域中可互换使用。

已经开发了许多不同类型的标准，尝试简化这种计算节点之间数据的并行点对点通信。其中一个标准是消息传递接口标准(message passing interface，MPI)。MPI标准实质上是一个核心例程库，可以通过使用不同的编程语言(例如，FORTRAN、C和C++)调用。需要说明的是，MPI标准是规范而不是实现方式；MPI标准有多种实现方式，例如OpenMPI和MPICH标准。MPI标准的每种实现方式都严格定义了自己的核心例程库和所有MPI函数或操作的应用程序编程接口(application programming interface，API)。虽然本发明是参照MPI标准进一步描述的，但它不应解释为本发明的任何限制，并且本领域技术人员应理解，MPI标准仅出于说明目的而选择，并且可以被任何其它合适的标准取代。

参考图1-图6，现在更详细地描述不同的集合通信操作。每个集合通信操作都是根据如MPI标准等某种标准，根据最简单的点对点通信执行的。在图中，参与点对点通信的计算节点和数据项分别示意性地示为外部框和内部框，点对点通信本身示意性地示为单头箭头。此外，每个计算节点都有自己的秩，表示范围从0到P–1的整数。

具体地，图1示出了用于广播操作的通信模式100，其中，一个计算节点将相同的数据发送到单独的通信空间中的所有计算节点，或者换句话说，通信器。根据通信模式100，计算节点N0是根节点，并具有初始数据项D0。作为广播操作的结果，所有其它计算节点N1至NP–1接收同一数据项D0的副本。

图2示出了用于Reduce操作的通信模式200，其中，所有计算节点的数据项被组合成某个结果，然后将结果分配给根节点。根据通信模式200，计算节点N0至NP–1分别具有数据项D0至DP–1，计算节点N0作为根节点。如图2所示，数据项D0至DP–1的组合使用加法运算符Σ进行，使得计算节点N0最终包括数据项D0至DP–1的和，即说明文字“D012…P–1＝DΣ”是“D0+D1+D2+…+DP–1＝DΣ”的缩写表示。在其它示例中，加法运算符可以替换为任何其它运算符，如乘法运算符、最大运算符、最小运算符等。

图3示出了用于Allgather操作的通信模式300，其中，由每个计算节点提供的数据项被集中到所有其它计算节点，其中，数据项根据接收它们的其它计算节点的秩在每个计算节点中排序。根据通信模式300，计算节点N0至NP–1最初根据它们的秩0至P–1布置，使得Allgather操作的结果是计算节点N0至NP–1的每个计算节点中的有序集合D0至DP–1。

图4示出了用于ReduceScatter操作的通信模式400，其中，每个计算节点的数据项以类似于Reduce操作的方式组合成一个结果，但结果随后分散在所有计算节点上。因此，每个计算节点具有结果的一部分1/P。根据通信模式400，数据项D0至DP–1中的每一个数据项被划分为相同数量的基本块a、b、c、……、x，数据项D0至DP–1通过使用加法运算符Σ组合，使得不同数据项的相似名称的块被加在一起。另外，加法运算符仅作为示例给出。所得到的和DΣ由新块A、B、C、……、X表示，其中，A等于数据项的所有块“a”的和，B等于数据项的所有块“b”的和，依此类推。最后，所得到的和DΣ分散在计算节点N0至NP–1上，使得每个计算节点包括块A、B、C、……、X中的相应一个块。

图5-图6分别示出了Allreduce操作的通信模式500和600，其中，所有计算节点的数据项以类似于Reduce操作的方式组合成某个结果，但结果的副本随后被分发回每个计算节点。通信模式500和600之间的唯一区别是，数据项D0至DP–1中的每一个数据项由图5中的块a、b、c、……、x表示，而图6示出了更简单的情况，其中，数据项D0至DP–1呈现为单个数据项。根据图5，计算节点N0到NP–1的块a、b、c、……、x以与上文参考图4描述的相同的方式进行加法运算，并且所得到的和DΣ进一步存储在每个计算节点中。根据图6，将单个数据项D0到DP–1相加，然后将它们的和存储在每个计算节点中。

如上所述，Allreduce操作是基于MPI的HPPC应用程序中最常用的集合通信操作之一。具体地，已发现，基于MPI的HPPC应用程序将大约20％的操作时间精确地花费在Allreduce操作上(有关更多详细信息，参见Rolf Rabenseifner的“使用硬件性能计数器自动分析MPI应用程序(Automatic profiling of MPI applications with hardwareperformance counters)”，见PVM/MPI，第35-42页，1999年)。因此，结合Allreduce操作进一步描述本发明。同时，需要再次说明的是，本发明并不限于Allreduce操作，其方面可应用于任何其它集合操作，如上文讨论的操作。

图7是在每个集合通信操作中实现的点对点通信的说明性表示。粗线702a-702e对应参与点对点通信的不同对象使用的带宽，长度704a-704d对应每个点对点通信之间的不同延迟，从带宽702a的开始计数。更具体地，假设第一点对点通信在第一用户应用程序706a与发送器操作系统(operating system，OS)708a之间执行，第二点对点通信在发送器OS708a与网络710之间执行，第三点对点通信在网络710与接收器OS 708b之间执行，最后第四点对点通信在接收器OS 708b与第二用户应用程序706b之间执行。在该示例中，用户应用程序706a、706b和OS 708a、708b起到通过网络710连接的计算节点的作用。每个点对点通信或传输可以表示为以下等式：T＝a+b·D，其中，a是延迟项，b是带宽系数，b·D是带宽项。从等式中可以看出，当数据或消息的大小足够小时，带宽项变得可以忽略不计，点对点通信的时间主要由延迟项定义(见第一点对点通信)。在相反的情况下，即，当数据或消息的大小足够大时，点对点通信的时间主要由带宽项定义(例如，见第四点对点通信)。因此，数据的大小直接影响点对点通信。

为了尝试优化Allreduce操作的实现，OpenMPI和MPICH标准建议根据Allreduce操作中使用的数据大小，在递归倍增算法和环算法之间切换。现在参考图8-图11更详细地公开递归倍增算法和环算法。

图8示出了用于通过使用递归倍增算法实现Allreduce操作的示例性调度800。具体地，假设计算节点的数量等于7，因此计算节点的佚从0到6。鉴于此，每个计算节点根据秩包括初始分布数据项D0至D6中的一个。调度800中的行表示构成Allreduce操作的不同中间点对点通信。更具体地，每个中间点对点通信定义如下：数据项从一个计算节点发送(参见图8中的“snd”)，并在另一个计算节点接收(参见图8中的“rcv”)，从而提供了一定的部分组合(参见图8中的“res”)。当大写字母“D”附近有几个数字时，这意味着对应的数据项由对应计算节点的数据项的部分组合(例如由加法运算符提供)表示。在该示例中，假设每个计算节点在Allreduce操作结束时具有“D0123456”。

需要说明的是，只有当计算节点的数量是2的幂时，递归倍增算法才会对延迟进行优化。在图8所示的示例中，有七个计算节点N0到N6，这使得递归倍增算法不是最优的。为了克服这一缺点并实现Allreduce操作，递归倍增算法应按以下方式执行：

递归倍增算法的上述方法的复杂度由以下等式定义：

其中，

至于环算法，它需要构建连接所有计算节点的逻辑环，如图9中的箭头示意性所示，其中使用对等网络拓扑900。利用这种网络拓扑，计算节点N0至N6严格按照逻辑环通过网络交换机902相互通信。Allreduce操作的环算法可以通过随后执行ReduceScatter和Allgather操作来实现，如下所述。

图10示出了环算法中ReduceScatter操作的示例性调度1000。调度1000具有与递归倍增算法的调度800相同的表格结构。唯一的补充是，数据项D0至D6各自被划分为相同数量(P＝7)的不同基本块“a、b、c、d、e、f、g”。在这种情况下，ReduceScatter操作包括步骤0到步骤5，在每个步骤中，每个计算节点将数据项的1/P，即“a、b、c、d、e、f、g”的一个块，发送到逻辑环中的下一个计算节点，如从计算节点N0到计算节点N1的调度中的箭头所示。从上一个计算节点接收的块与本地数据项的对应块一起累积，即，例如，块“a”只能与对应的本地块“a”一起累积。在ReduceScatter操作结束时，每个计算节点将拥有减少结果的1/P(例如，在调度1000中，计算节点N0拥有块“a”)。

图11示出了环算法中Allgather操作的示例性调度1100。另外，调度1100具有与调度1000相同的表格结构，唯一的区别是它不需要执行任何累积，并且只涉及连接接收到的块以获得更大的结果。Allreduce操作可以在逻辑环上与调度1100所示的方向相同的方向，或相反的方向上执行。

环算法的复杂度由以下定义：

鉴于上文，可以得出结论，与递归倍增算法不同，环算法对任何数量的计算节点都实现带宽优化，并且在带宽项方面具有恒定的复杂度。但是，环算法的主要缺点是它在延迟项方面的线性-它需要2×(P-1)个步骤(具体地，图9-图11所示的示例需要2×(7-1)＝12个步骤)。因此，OpenMPI和MPICH标准中的大数据项使用环算法。

实现Allreduce操作的另一种算法是递归减半算法(有关更多详细信息，参见以下信息来源：R.Thakur、R.Rabenseifner、W.Gropp.MPICH中集体通信操作的优化(Optimization of Collective Communication Operations in MPICH)，国际高性能计算应用杂志，第19卷，2005年第1期)。但是，与递归倍增算法类似，递归减半算法只有对数量是2的幂的计算节点才是最优的。如果计算节点的数量不是2的幂，则递归减半算法将不是最优的，因为它需要与递归倍增算法相同的额外准备和最终确定步骤。

图12示出了在使用递归减半算法的情况下Allreduce操作的示例性调度1200。在此，再次假设计算节点的数量等于7，并且调度1200本身具有与上文讨论的调度800、1000和1100相同的结构。为了克服数量不是2的幂的计算节点的缺点并实现Allreduce操作，递归减半算法应按以下方式执行。

第1部分：

第2部分：

对于不是2的幂的情况，递归减半算法的复杂度定义为

其中，

因此，以下主要问题是上述现有技术算法特有的。

1.现有的MPI库，如OpenMPI和MPICH标准提供的库，将Allreduce操作实现为不同算法的集合，在操作中根据数据项的大小在这些算法之间切换。每种算法都是极小的网络和数据参数集的最佳算法。因此，如此实现的allreduce操作表现出的性能通常不是最优的。

2.对于数量不是2的幂的计算节点，没有通用方案使得在延迟方面实现最优。

3.对于数量不是2的幂的计算节点，没有通用方案使得在带宽方面实现最优，并且只需要2log(P)个步骤。

下文讨论的本发明考虑了现有技术的上述缺点，并旨在提供一种技术方案，用于有效地执行集合通信操作，特别是Allreduce操作，而不考虑所涉及的数据项的大小和计算节点的数量。

图13示出了本发明的一个方面提供的装置1300的示例性框图，该装置1300用于在包括多个计算节点的数据通信网络中执行集合通信操作。如图13所示，装置1300包括存储器1302和与存储器1302耦合的处理器1304。存储器1302存储可执行指令1306，该可执行指令1306由处理器1304执行以执行感兴趣的集合通信操作。数据通信网络应具有如图9所示的对等网络拓扑，但该网络拓扑不应解释为本发明的任何限制。还假设计算节点与网络交换机之间的所有信道都是全双工的，即可以通过每个信道进行双向点对点通信。换句话说，例如，从计算节点N1到计算节点N3的点对点通信不影响从计算节点N3到计算节点N1的点对点通信。

存储器1302可以实现为现代电子计算机中使用的易失性或非易失性存储器。非易失性存储器的示例包括只读存储器(read-only memory，ROM)、闪存、铁电式随机存取存储器(random-access memory，RAM)、可编程ROM(programmable ROM，PROM)、电可擦除PROM(electrically erasable PROM，EEPROM)、固态驱动器(solid state drive，SSD)、磁盘存储器(如硬盘和磁带)、光盘存储器(如CD、DVD和蓝光光盘)等。至于易失性存储器，其示例包括动态RAM、同步DRAM(synchronous DRAM，SDRAM)、双数据速率SDRAM(double data rateSDRAM，DDR SDRAM)、静态RAM等。

处理器1304可以实现为中央处理单元(central processing unit，CPU)、通用处理器、单用途处理器、微控制器、微处理器、专用集成电路(application specificintegrated circuit，ASIC)、现场可编程门阵列(field programmable gate array，FPGA)、数字信号处理器(digital signal processor，DSP)。还需要说明的是，处理器1304可以实现为上述一个或多个的任何组合。作为示例，处理器1304可以是两个或多个微处理器的组合。

存储在存储器1302中的可执行指令1306可以配置为使处理器1304执行本发明各方面的计算机可执行代码。用于执行本发明各方面的操作或步骤的计算机可执行代码可以用Java、C++等一种或多种编程语言的任何组合编写。在一些示例中，计算机可执行代码可以是高级语言的形式或预编译的形式，并由解释器(也预存储在存储器1302中)动态生成。

图14示出了本发明的另一方面提供的用于执行感兴趣的集合通信操作的方法1400的示例性框图。具体地，当装置1300的处理器1304执行装置1300的存储器1302中的指令1306时，处理器1304执行方法1400。如图14所示，方法1400从步骤S1402开始，在该步骤中，处理器1304首先接收要用于感兴趣的集合通信操作的数据阵列。为了方便起见，还假设Allreduce操作由处理器1304执行。所述数据阵列包括数据项，并具有预定义的大小。在步骤S1404中，处理器1304还用于获取数据项在计算节点上的分布。之后，方法1400进入步骤S1406，在该步骤中，处理器1304获取数据通信网络的网络参数。接下来，在步骤S1408中，处理器1304根据数据阵列的大小、网络参数和数据项的分布确定Allreduce操作的调度。在步骤S1410中，至少一个处理器最终用于根据Allreduce操作的调度对数据阵列执行Allreduce操作。同时，所述数据项的所述分布和所述集合通信操作的所述调度都基于所述计算节点之间所述数据项的循环排列。

上述网络参数可以包括网络带宽和网络延迟，在一个实施例中，步骤S1406可以由处理器1304借助任何用户输入模块(图13中未示出)执行。用户输入模块可以实现为装置1300的一部分，或者作为通过有线或无线连接耦合到装置1300的单个设备。例如，装置1300可以是移动设备，如笔记本电脑或平板电脑，并且用户输入模块可以实现为耦合到装置1300的触摸屏或有线或无线鼠标或键盘。在另一个示例中，用户输入模块可以由语音识别模块和耦合到装置1300或另外包括在装置1300中的麦克风的组合来表示，从而可以通过用户语音将网络参数馈送到处理器1304中。在另一个实施例中，步骤S1406可以包括处理器1304从远程服务器下载网络参数，并在执行Allreduce操作之前将这些网络参数存储在存储器1302中。在另一个实施例中，可行的是步骤S1406涉及处理器1304直接从安装在作为移动设备实现的装置1300上的一个或多个专用用户应用程序接收网络参数。但是，本领域技术人员应该清楚的是，本发明并不限于上述实施例，并且例如，可以根据特定应用使用任何其它实施例或上文列举的实施例和/或其它实施例的组合。

步骤S1406的另一个实施例涉及使用网络分析器(图13未示出)实时计算网络参数。网络带宽和延迟测量可以使用任何现有方法以令人满意的准确度执行。但是，这些方法不在本发明的范围内，因此本文省略它们的描述。

需要说明的是，Allreduce操作可以作为其它不同的集合通信操作的组合来呈现。例如，实现Allreduce操作的最简单方式是将图2所示的Reduce操作与图1所示的广播操作组合。如上所述，在某个计算节点中，Reduce操作产生所有数据项的组合，如DΣ＝D0+D1+D2+…+DP，然后将结果分发到广播操作中的所有计算节点。实现Allreduce操作的另一种方式是将图4所示的ReduceScatter操作与图3所示的Allgather操作组合。在这种情况下，ReduceScatter操作的结果由分散在所有计算节点上的数据项表示，Allgather操作用于集中每个计算节点中的所有分散数据项。

参考图15更详细地解释方法1400的步骤S1404。具体地，再次假设计算节点的数量等于7，并且计算节点N0至N6通过相同的网络交换机902相互通信，该网络交换机902实现了在计算节点之间提供全双工信道的对等网络拓扑。步骤S1404可以分为两个子步骤，每个子步骤导致获取计算节点N0至N6上的特定数据分布。在这种情况下，所述获取数据分布不应解释为在计算节点上执行数据项的任何物理或实际分布。相反，所述获取数据分布仅与以适当方式描述数据项的方式有关。更具体地，步骤S1404的第一子步骤产生每节点数据分布，在该数据分布下，在步骤S1402中接收的数据阵列的数据项D0至D6中的每个数据项被分配给计算节点N0至N6中的相应一个计算节点。步骤S1404的第二子步骤产生基于排列的数据分布，在该数据分布下，通过使用循环排列来修改每节点数据分布。

每个循环排列实际上描述了某个逻辑环。图16给出了循环排列的一些示例。具体地，图16示出了分别表示为c

回到图15，在步骤S1404的第二子步骤中，通过将数据项D0至D6中的每个数据项划分为P个基本块，并将循环排列应用于计算节点N0到N6的块，获取基于排列的数据分布。在图15所示的示例中，在所述划分之后，每个计算节点中存在7个基本块“a、b、c、d、e、f、g”。需要说明的是，分配给不同计算节点的类似名称的块不一定相同。为了将循环排列应用于计算节点N0至N6的块，首先需要固定包括每个计算节点的一个不同名称的块的基础数据分布。图17示出了一个示例，其中，基础数据分布包括来自计算节点N0的块“a”、来自计算节点N1的块“b”、来自计算节点N2的块“c”，……，以及来自计算节点N6的块“g”。通过将基础数据分布与图16所示的不同循环排列组合，可以以图15所示的基于排列的数据分布的形式呈现初始数据阵列。例如，c

此外，在方法1400的步骤S1408中，由处理器1304确定的调度可以根据感兴趣的集合通信操作为所述循环群定义特定的点对点通信集。同时，所述循环群的点对点通信也通过使用上文讨论的循环排列来执行。这种点对点通信的一个示例如下：

–假设初始循环群如下所示：c

–假设点对点通信包括将循环排列c

–在点对点通信之后，应该如下所示：c

因此，在点对点通信之后，块“a”从计算节点N3到计算节点N0，块“b”从计算节点N4到计算节点N1，块“c”从计算节点N5到计算节点N2，依此类推。最后，将有两个具有相同排列的集合d

参考图18，现在描述如应用于分配给计算节点N0至N6的上述循环群c

更具体地，ReduceScatter操作包括三个步骤S1802至S1806。调度1800的每个步骤涉及使用特定的循环排列。换句话说，术语“步骤”和“循环排列”在调度的上下文中可以互换使用。在步骤S1802中，循环群或计算节点的总数减少到最接近的2的幂。由于图18中存在7个循环群，步骤S1802需要减少3个(例如，最后三个)循环群。这种减少可以通过使用循环排列c

Allgather操作包括三个步骤S1808至S1812。在Allgather操作开始时，只有一个循环群，在步骤S1808和S1810中的每个步骤中，循环群的数量分别通过使用循环排列c

图19示出了另一个实施例，其中，调度1900包括与调度1800相同的步骤，但依赖于在ReduceScatter操作期间同时使用循环群的两个分布。循环群的第二分布是相同的，但所有指数都移位1。需要说明的是，使用循环群的第二分布不会导致计算工作加倍，因为一些循环群可以在两个分布之间共享(这些循环群在调度1900中以灰色着色)。同时，使用这两个分布必定会存储和通信一些额外的循环群，但它也提供了一个优势-在这种情况下，步骤的数量，或者，换句话说，Allreduce操作中涉及的点对点通信减少(具体地，步骤S1808被消除，如调度1900中的删除线象征性地示出)。

另一个实施例涉及将步骤S1802至S1812的数量或表征Allreduce操作的循环排列减少2，如图20所示。具体地，在该实施例中，从Allreduce操作中排除调度2000中的步骤S1808和S1810。为此，有必要在减少ReduceScatter操作之后有4个循环群，通过循环排列c

最后，在另一个实施例中，可行的是表征Allreduce操作的步骤数量减少到

给定图18-图21所示的实施例，可以得出结论，Allreduce操作的调度可以定义

表1：Allreduce操作的带宽优化方法的复杂度比较

表2：Allreduce操作的延迟优化方法的复杂度比较

要了解在带宽和延迟方面，Allreduce操作的最优循环排列数量，可以计算延迟-带宽比，如下所示：

其中，D是在方法1400的步骤S1402中接收的数据阵列的大小。该比率不仅因不同的网络而异，而且因数据阵列的不同大小而异。根据该比率，可以计算Allreduce操作的调度中使用的循环排列的最优数量。

图22表示表2200，该表列出Allreduce操作的调度中使用的不同数量的循环排列的不同时间估计ω。已为计算节点的数量P＝255绘制表2200。以粗体示出每个循环排列数量的最佳估计性能。在延迟-带宽比为最小值的情况下，即当带宽项主导延迟项时，上文参考图18讨论的、涉及16个循环排列的带宽优化实施例效果良好。在延迟-带宽比为最大值的情况下，即当延迟项主导带宽项时，上文参考图21讨论的、涉及8个循环排列的延迟优化实施例示出最佳性能。至于延迟-带宽比的中间值，Allreduce操作的最佳性能通过使用循环排列的某个中间数来提供。

Allreduce操作的调度中使用的循环排列的最优数量取决于计算机节点的数量，可以根据以下公式估计：

具体地，图23示出了列出循环排列的不同最优数量n

图24表示表2400，示出了用于Allreduce操作的上述现有技术算法和方法1400的比较。具体地，通过循环排列的数量和针对固定数量的计算节点P＝255每个计算节点要发送的数据项的大小来比较现有技术算法和方法1400。要发送的每个数据项的大小除以数据阵列的总大小，以便具有用于比较的归一化值。表2400突出显示了方法1400的主要区别-它能够在

已将方法1400与以下信息源中描述的OpenMPI标准进行了实验比较：EdgarGabriel等人，Open MPI：下一代MPI实现的目标、概念和设计(Open MPI:Goals,Concept,and Design of a Next Generation MPI Implementation)，Proceedings，第11届欧洲PVM/MPI用户小组会议，第97-104页，匈牙利布达佩斯，2004年9月。如上所述，OpenMPI标准具有Allreduce操作的两种主要算法：小数据项的递归倍增算法和大数据项的环算法。在真实硬件上对两种不同的网络介质进行了实验：Linux操作系统中的进程间通信(见图25和图26)和万兆以太网(见图27和图28)。为了提供可靠的比较，方法1400已经基于OpenMPI内部点对点通信器实现。OpenMPI集合操作使用相同的通信器。实验结果以不同依赖关系的形式在图25和图26中针对Linux操作系统中的进程间通信以及在图27和图28中针对万兆以太网示出。需要说明的是，实线表示的实验依赖关系通过方法1400获取，而虚线表示的实验依赖关系通过OpenMPI标准获取。

更具体地，图25示出了Allreduce操作的执行时间对其中涉及的计算节点的数量的两个依赖关系。如图25所示，Allreduce操作的执行时间随着计算节点数量的增加而增加，并且上层依赖的这种增加比底层依赖的增加更快，从而证实了方法1400比OpenMPI标准的性能更好。

相对的，图26示出了Allreduce操作的执行时间对固定数量的计算节点P＝255的数据阵列大小的两个依赖关系。从图26可以看出，随着数据阵列大小的增加，依赖关系变得发散。在大数据阵列的情况下，OpenMPI标准切换到用于Allreduce操作的环算法，因此需要更多数量的循环排列。同时，底部依赖关系的增长较小，因此意味着方法1400需要较少数量的循环排列，因此，Allreduce操作的执行时间较短。

图27示出了与图25中相同的依赖关系，但最大数量的计算节点P＝7，因为在万兆以太网的情况下，很难找到大型对等网络。尽管如此，图27示出了随着计算节点数量的增加，依赖关系增长的相同特征-计算节点越多，增长就越大。同样，方法1400的性能优于OpenMPI标准。

最后，图28示出了与图26中相同的依赖关系，即在Allreduce操作中使用的数据阵列的不同大小下，OpenMPI标准和方法1400的比较。图28的依赖关系表明，绝对增益值不取决于数据阵列的大小。换句话说，在大数据阵列的情况下，增益值仅由根据OpenMPI标准(即P-1个步骤)和方法1400(即2logP个步骤)执行Allreduce操作所需的步骤数量的差异确定，与数据阵列的大小无关。

本领域技术人员应该理解，方法1400的每个块或步骤，或块或步骤的任何组合，可以通过硬件、固件和/或软件等各种手段实现。作为示例，上述块或步骤中的一个或多个可以由计算机可执行指令、数据结构、程序模块和其它合适的数据表示来体现。此外，体现上述块或步骤的计算机可执行指令可以存储在对应的数据载体上，并由至少一个处理器(如装置1300的处理器1304)执行。该数据载体可以实现为配置为可由所述至少一个处理器读取以执行计算机可执行指令的任何计算机可读存储介质。这种计算机可读存储介质可以包括易失性介质和非易失性介质、可移动介质和不可移动介质。作为示例而非限制，计算机可读介质包括以任何适合存储信息的方法或技术实现的介质。更详细地，计算机可读介质的实践示例包括但不限于信息传递介质、RAM、ROM、EEPROM、闪存或其它存储器技术、CD-ROM、数字多功能光盘(digital versatile disc，DVD)、全息介质或其它光盘存储器、磁带、磁带盒、磁盘存储器和其它磁存储设备。

虽然本文描述了本发明的示例性实施例，但需要说明的是，在不偏离由所附权利要求书所定义的法律保护范围的情况下，可以在本发明的实施例中进行任何各种更改和修改。在所附权利要求书中，词语“包括”不排除其它元件或步骤，术语“一”或者“一个”不排除多个。在互不相同的从属权利要求中列举某些措施并不表示这些措施的组合不能被有效地使用。