用于并行计算机中的集体操作协议选择的方法和系统

技术领域

本发明的领域是数据处理，或者更具体地讲是用于并行计算机中的 集体操作协议选择的方法、设备和产品。

背景技术

1948年的EDVAC计算机系统的开发常被引述为计算机时代的开 启。从那时开始，计算机系统已经演化成极端复杂的装置。与例如 EDVAC的早期系统相比，今天的计算机更加精密复杂。计算机系统通 常包括硬件和软件组件的组合、应用程序、操作系统、处理器、总线、 存储器、输入/输出装置等。由于半导体加工和计算机架构的进步将计 算机的性能推升得越来越高，更加精密复杂的计算机软件已经进化为利 用硬件的更高性能，使得当今的计算机系统与仅仅几年前相比强大得 多。

并行计算是经历了进步的计算机技术的领域。并行计算是在多个处 理器上同时执行同一任务（该任务被分解并且被专门调整）以更快获得 结果。并行计算基于如下事实：求解一个问题的过程通常能够被划分成 多个更小的任务，这些更小的任务能够通过某种协调被同时执行。

并行计算机执行并行算法。并行算法能够被分解从而在许多不同处 理装置上每次执行一份，然后最终再次汇总在一起以获得数据处理结 果。一些算法易于分解成多个份。可以例如如下执行对检查从1到十万 的所有数字以查看哪些是质数的作业进行分解：向每个可用处理器分配 这些数字的子集并且然后将肯定结果的列表汇总在一起。在本说明书 中，执行并行程序的各个份的多个处理装置被称作“计算节点”。并行计 算机由计算节点以及例如包括输入/输出（I/O）节点和服务节点的其它 处理节点构成。

并行算法是有价值的，因为由于现代处理器工作的方式使得经由并 行算法执行某些大的计算任务与经由串行（非并行）算法相比更快。与 采用多个慢速处理器相比，采用单个快速处理器构造相同处理能力 （throughput）的计算机要困难得多。串行处理器的潜在速度也存在某 些理论限制。另一方面，每个并行算法具有串行部分并且因此并行算法 具有饱和点。在该点后，增加更多处理器不会产生任何更多的处理能力 而只会增加开销和开销。

并行算法还被设计为优化并行计算机的节点之间进行数据通信所要 求的又一个资源。存在两种并行处理器进行通信的方式：共享存储器或 者消息传递。共享存储器处理需要针对数据的额外锁定并且强加额外处 理器和总线周期的开销并且还将算法的某部分串行化。

消息传递处理利用高速数据通信网络和消息缓冲器，但是这种通信 增加了数据通信网络上的传送开销、以及消息缓冲器所需的额外存储器 和节点之间的数据通信的等待时间（latency）。并行计算机的设计利用 专门设计的数据通信链路以使得通信开销较小，然而正是并行算法决定 通信量。

许多数据通信网络架构用于并行计算机中的节点之间的消息传递。 例如，可以在网络中将计算节点组织为“环（torus）”或“网格 （mesh）”。另外，可以在网络中将计算节点组织为树。环网络通过缠 绕链路以三维网格连接节点。每个节点通过这种环网络连接到它的六个 邻居，并且每个节点按其在网格中的x、y和z坐标来表示地址。按照 这种方式，环网络将它自身用于点对点操作。在树网络中，节点通常连 接成二叉树：每个节点具有一个父辈和两个孩子（但是某些节点可以仅 具有零个孩子或一个孩子，这取决于硬件结构）。尽管树网络通常在点 对点通信中低效，但是树网络对所有计算节点同时参与的某些集体操 作、消息传送操作（例如，全收集（allgather）操作），提供高带宽和 低等待时间。在使用环网络和树网络的计算机中，这两个网络通常彼此 独立地实现，具有分离的路由回路、分离的物理链路和分离的消息缓冲 器。

并行计算机中的计算节点还可以被组织成工作组以执行集体并行操 作。通过工作组的计算节点之间的数据通信实现集体操作。集体操作是 涉及一个工作组的所有计算节点的那些功能。集体操作是一种同时 （即，近似同一时间）由计算节点的工作组中的所有计算节点执行的操 作、消息传递计算机程序指令。“广播”是用于在工作组的计算节点之间 移动数据的集体操作的例子。“归约（reduce）”操作是对分布在工作组 的计算节点之中的数据执行算术或逻辑函数的集体操作的例子。用于集 体操作的协议可以针对特定操作参数（执行集体操作的参数）进行调整 或优化。这些参数的例子可以是：要执行的逻辑或者算术函数的类型、 数据类型、数据大小、节点的数目等。集体操作协议可以针对特定的操 作参数集合进行优化，因为本领域的读者可以想到，所述协议与其它协 议相比更高效，与其它协议相比在执行期间消耗更少功率，与其它协议 相比使用更少资源，与其它协议相比执行得更快等。因此，提高为集体 操作选择优化协议的准确度有利于并行计算系统中的数据处理。

发明内容

在本说明书中描述了用于并行计算机中的集体操作协议选择的方 法、设备和产品。并行计算机包括许多计算节点。这种集体操作协议选 择包括：调用具有一个或多个操作参数的集体操作，选择用于执行该集 体操作的多个协议之一，以及利用选择的协议执行该集体操作。在本发 明的实施例中，对于从第一预期协议开始直到满足预定性能标准的预期 协议，反复执行选择多个协议之一，选择多个协议之一包括：向用于该 预期协议的协议性能函数提供集体操作的操作参数；通过该性能函数 确定针对所述操作参数该预期协议是否满足预定性能标准，包括针对 该预期协议通过所述操作参数评估预定义性能拟合方程以及计算针对 所述操作参数的该预期协议的性能度量；以及仅当计算的性能度量大 于预定义最小性能阈值时，确定该预期协议满足预定性能标准并且选 择该预期协议作为用于执行集体操作的协议。

基于附图中所示的本发明的示例性实施例的下面更加具体的描述， 本发明的上述以及其它目标、特征和优点将变得清楚，在附图中相似标 号一般表示本发明的示例性实施例的相似部件。

附图说明

图1示出了根据本发明的实施例的用于并行计算机中的集体操作协 议选择的示例性系统。

图2阐述了用于并行计算机中的能够执行根据本发明的实施例的集 体操作协议选择的示例计算节点（102）的框图。

图3A阐述了用于根据本发明的实施例的并行计算机中的集体操作 协议选择的系统中的示例点对点适配器的框图。

图3B阐述了用于根据本发明的实施例的并行计算机中的集体操作 协议选择的系统中的示例全局组合网络适配器的框图。

图4阐述了示出用于能够执行根据本发明的实施例的并行计算机中 的集体操作协议选择的系统的针对点对点操作进行优化的示例数据通信 网络的线路图。

图5阐述了示出用于能够执行根据本发明的实施例的并行计算机中 的集体操作协议选择的系统的示例全局组合网络的线路图。

图6阐述了示出用于根据本发明的实施例的并行计算机中的集体操 作协议选择的示例方法的流程图。

图7阐述了示出用于根据本发明的实施例的并行计算机中的集体操 作协议选择的另一示例方法的流程图。

图8阐述了示出用于根据本发明的实施例的并行计算机中的集体操 作协议选择的另一示例方法的流程图。

具体实施方式

从图1开始，参照附图描述根据本发明的用于并行计算机中的集体 操作协议选择的示例性方法、设备和产品。图1示出了根据本发明的实 施例的用于并行计算机中的集体操作协议选择的示例性系统。图1的系 统包括并行计算机（100）、数据存储装置（118）形式的计算机的非易 失性存储器、打印机（120）形式的计算机的输出装置、和计算机终端 （122）形式的计算机的输入/输出装置。

图1的示例中的并行计算机（100）包括多个计算节点（102）。通 过多个独立的数据通信网络（包括高速以太网（174）、联合测试行动组 （JTAG）网络（104）、使用二叉树网络拓扑针对集体操作进行优化的 全局组合网络（106）和使用环网络拓扑针对点对点操作进行优化的点 对点网络（108）），计算节点（102）进行耦合以进行数据通信。全局组 合网络（106）是包括连接到计算节点（102）以把计算节点（102）组 织为二叉树的数据通信链路的数据通信网络。通过计算节点（102）之 间的数据通信链路实现每个数据通信网络。数据通信链路为并行计算机 （100）的计算节点（102）之间的并行操作提供数据通信。

并行计算机（100）的计算节点（102）被组织成用于并行计算机 （100）上的集体并行操作的计算节点的至少一个工作组（132）。计算 节点的每个工作组（132）是执行集体并行操作的计算节点的集合。工 作组（132）中的每个计算节点被分配唯一级别，用于识别工作组 （132）中的特定计算机节点。通过工作组的计算节点之间的数据通信 实现集体操作。集体操作是涉及一个工作组（132）的所有计算节点的 那些功能。集体操作是一种同时（即，近似同一时间）由计算节点的工 作组（132）中的所有计算节点执行的操作、消息传递计算机程序指 令。这种工作组（132）可以包括并行计算机（100）中的所有计算节点 （102）或者所有计算节点（102）的子集。常常围绕点对点操作建立集 体操作。集体操作要求工作组（132）内的所有计算节点上的所有处理 调用具有匹配参数的同一集体操作。“广播”是在工作组的计算节点之间 移动数据的集体操作的示例。“归约”操作是对分布在工作组（132）的 计算节点之中的数据执行算术或逻辑函数的集体操作的示例。例如，工 作组（132）可被实现为MPI“通信器”。

“MPI”是指“消息传递接口（Message Passing Interface）”、现有技 术的并行通信库、并行计算机上进行数据通信的计算机程序指令的模 块。可被改进以应用于根据本发明的实施例构造的系统中的现有技术并 行通信库的示例包括MPI和“并行虚拟机”（PVM）库。PVM是由田纳 西大学、Oak Ridge国家实验室和埃默里大学开发的。MPI由MPI论 坛进行发布，MPI论坛是一个具有来自定义并维护MPI标准的许多组 织的代表的开放群。撰写此文时的MPI是在分布式存储器并行计算机 上运行并行程序的计算节点之间进行通信的事实标准。为了易于进行解 释，本说明书有时使用MPI术语，但是这样使用MPI不是本发明的要 求或限制。

某些集体操作具有在工作组（132）中的特定计算节点上运行的一 个发起或接收过程。例如，在“广播”集体操作中，向所有其它计算节点 分发数据的计算节点上的过程是发起过程。在“收集（gather）”操作 中，例如，从其它计算节点接收所有数据的计算节点上的过程是接收过 程。运行这种发起或接收过程的计算节点被称作逻辑根。

大多数集体操作是如下四种基本操作的变型或组合：广播、收集、 分散和归约。用于这些集体操作的接口在由MPI论坛发布的MPI标准 中进行定义。然而，用于执行集体操作的算法没有在MPI标准中进行 定义。在广播操作中，所有过程指定其缓冲器内容将被发送的同一根过 程。除根之外的过程指定接收缓冲器。在该操作后，所有缓冲器包含来 自根过程的消息。

与广播操作一样，分散操作也是一对多集体操作。在分散操作中， 逻辑根将根上的数据划分成段并且将不同段分配给工作组（132）中的 各个计算节点。在分散操作中，所有过程通常指定相同接收计数。发送 参数只对其缓冲器实际包含给定数据类型的发送计数（sendcount）*N 个元素的根过程有意义，其中，N是给定的计算节点组中的过程的数 目。发送缓冲器被分割并且分散给所有过程（包括逻辑根上的过程）。 每个计算节点被分配称作“级别（rank）”的连续标识符。在该操作后， 根已经按照上升级别顺序向每个过程发送了sendcount个数据元素。级 别0从发送缓冲器接收前sendcount个数据元素。级别1从发送缓冲器 接收接下来的sendcount个数据元素，依此类推。

收集操作是多对一集体操作，即，分散操作的说明的完全逆转。也 就是说，收集是一种多对一集体操作，其中，一数据类型的元素被从分 级别的计算节点收集到根节点中的接收缓冲器中。

归约操作也是一种多对一集体操作，包括对两个数据元素执行的算 术或逻辑函数。所有过程指定相同“计数（count）”和相同算术或逻辑 函数。在归约后，所有过程已经将count个数据元素从计算节点发送缓 冲器发送到根过程。在归约操作中，来自对应发送缓冲器位置的数据元 素通过算术或逻辑运算被成对组合以在根过程的接收缓冲器中生成单个 对应元素。专用归约操作能够在运行时进行定义。并行通信库可以支持 预定义操作。例如，MPI提供下面的预定义归约操作：

MPI_MAX最大

MPI_MIN最小

MPI_SUM和

MPI_PROD乘积

MPI_LAND逻辑与

MPI_BAND位与

MPI_LOR逻辑或

MPI_BOR位或

MPI_LXOR逻辑异或

MPI_BXOR位异或

除了计算节点以外，并行计算机（100）包括经由全局组合网络 （106）与计算节点（102）耦合的输入/输出（I/O）节点（110、114）。 并行计算机（100）中的计算节点（102）可以被划分成多个处理组以使 得一个处理组中的每个计算节点为进行数据通信而连接到同一I/O节 点。因此，每个处理组由一个I/O节点和计算节点（102）的子集构 成。整个系统中的计算节点的数目与I/O节点的数目的比率通常取决于 并行计算机（102）的硬件结构。例如，在一些结构中，每个处理组可 由八个计算节点和一个I/O节点构成。在一些其它结构中，每个处理组 可由64个计算节点和一个I/O节点构成。这些示例仅仅用于说明，而 非用于限制。每个I/O节点在它的处理组的计算节点（102）与一组I/O 装置之间提供I/O服务。在图1的示例中，I/O节点（110、114）经由 使用高速以太网实现的局域网（LAN）(130)连接到I/O装置（118、 120、122）以进行数据通信。

图1的并行计算机（100）还包括经由网络之一（104）耦合到计算 节点的服务节点（116）。服务节点（116）提供对多个计算节点相同的 服务，管理计算节点的配置，向计算节点中加载程序，启动计算节点上 的程序执行，取回计算节点上程序操作的结果，等等。服务节点 （116）运行服务应用（124）并且经由在计算机终端（122）上运行的 服务应用接口（126）与用户（128）进行通信。

图1的并行计算机（100）通常采用根据本发明的实施例的许多计 算节点进行操作以进行集体操作协议选择。为了清楚地进行说明，在本 文中作为工作组中的一个计算节点的示例描述了计算节点（102a）。本 技术领域的读者应该明白，工作组中的其它计算节点将具有相似的级 别、数据元素、数据结构、过程、函数，并且将按照与该示例计算节点 （102a）相似的方式工作。

计算节点（102a）包括级别（212）-MPI通信器（即工作组 （132））中的过程。级别（212）调用具有一个或多个操作参数（214） 的集体操作（220）。作为在本说明书中使用的术语的操作参数可以是为 了执行集体操作的目的而被传递给该集体操作的任何参数。这些操作参 数的示例包括本技术领域的读者可以想到的消息大小、数据类型、目标 节点的数目和标识符等。

集体操作（220）（这里未示出的计算机程序指令的某其它模块）然 后可以选择用于执行集体操作的多个协议（222）之一。根据本发明的 实施例，对于从第一预期协议开始直到满足预定的性能标准的预期协议 的每个协议（222），反复地执行这种选择。预定的性能标准是可被预定 用于表示“性能”的可接受水平的任何值。各个性能标准类型的示例包括 本技术领域的读者可以想到的执行速度、执行中利用的资源的数目等。

协议选择的每次重复包括：向用于该预期协议的协议性能函数 （228）提供集体操作的操作参数（214），并且通过该性能函数（228） 确定该预期协议（222）针对所述操作参数是否满足预定义性能标准。 协议的性能函数是一个计算机程序指令的函数或者子例程，当被执行时 确定该协议针对一组特定操作参数是否生成优化性能结果。在一些实施 例中，例如，协议的性能函数的返回值是“良好拟合（good fit）”或“较 差拟合（bad fit）”结果。

在图1的示例中，集体操作根据用于预期协议的或者与预期协议关 联的元数据（224），识别并调用协议性能功能（228）。即，通过元数据 在图1的示例中描述可供选择的每个协议。这种元数据可描述协议的许 多不同属性。在本发明的实施例中，例如，每个协议的元数据（224） 可以包括指向协议的性能函数（228）的指针。

通过针对该预期协议利用操作参数（214）评估预定义性能拟合方 程（230）从而计算针对所述操作参数的预期协议的性能度量，性能函 数（228）可以确定针对所述操作参数，预期协议（222）是否满足预定 义性能标准。通过拟合方程描述、指定或定义通过该协议的性能函数 （228）的在图1的示例中的相对于操作参数组的每个协议的性能。可 以通过先前测量的性能数据的线性、二次或四次回归分析产生这种拟合 方程。即，利用多个不同的操作参数组，每个协议可以被执行许多次， 测量并存储每次执行所产生的性能数据。然后，可以采用测量和存储的 性能数据执行回归分析以建立近似描述协议的性能质量的拟合方程。每 个拟合方程然后返回针对一组特定操作参数的计算的性能度量（218）。

在实时协议选择期间，如果计算的性能度量（218）大于预定义的 最小性能阈值（图1的示例中的性能标准（216）），则集体协议（220） 确定该预期协议满足预定性能标准并且选择该预期协议作为用于执行集 体操作的协议。如果计算的性能度量（218）不大于预定义的最小性能 阈值，则选择过程针对另一个预期协议进行下一次重复。一旦被选择， 集体操作（220）利用所选择的协议执行。

组成图1中所示的示例设备的节点、网络以及I/O装置的布置只是 用于解释本发明而非进行限制。被构造为用于根据本发明的实施例的并 行计算机中的集体操作协议选择的系统可以包括本领域技术人员可想到 的图1未示出的另外的节点、网络、装置和架构。图1的示例中的并行 计算机（100）包括16个计算节点（102）；被构造为用于根据本发明的 实施例的集体操作协议选择的并行计算机有时候包括几千个计算节点。 除了以太网（174）和JTAG（104）以外，这种数据处理系统中的网络 可以支持许多数据通信协议，例如包括TCP（传输控制协议）、IP（互 联网协议）、以及本领域技术人员可想到的其它协议。还可以在图1所 示的硬件平台之外的各种硬件平台上实现本发明的各种实施例。

通常在包括通过至少一个数据通信网络组织用于集体操作的多个计 算节点的并行计算机上实现根据本发明的实施例的集体操作协议选择。 实际上，这些计算机可以包括成千个这种计算节点。每个计算节点自身 又是一种由一个或多个计算机处理核、它自己的计算机存储器和它自己 的输入/输出适配器组成的计算机。因此，为了进一步的说明，图2阐 述了用于能够进行根据本发明的实施例的集体操作协议选择的并行计算 机中的示例计算节点（102）的框图。图2的计算节点（102）包括多个 处理核（165）以及RAM（156）。可以在一个或多个集成电路芯片上构 造图2的处理核（165）。处理核（165）通过高速内存总线（155）连接 到RAM(156)并且通过总线适配器（194）和扩展总线（168）连接到计 算节点的其它部件。在RAM(156)中存储了应用程序（159），即，使用 并行算法执行并行、用户级数据处理的计算机程序指令的模块。

在RAM（156）中还存储了并行通信库（161），即，在计算节点之 间执行并行通信（包括点对点操作和集体操作）的计算机程序指令的 库。可以使用例如C编程语言的常规编程语言以及使用常规编程方法编 写在两个独立数据通信网络上在节点之间发送和接收数据的并行通信例 程，从头开发并行通信例程的库以用于根据本发明的实施例的系统中。 或者，可以改进现存的现有库以根据本发明的实施例进行工作。现有并 行通信库的示例包括“消息传递接口，Message Passing Interface” （MPI）库和“并行虚拟机，Parallel Virtual Machine”（PVM）库。

在RAM中还存储了级别（212），即MPI通信器中的过程。当级 别（212）和并行通信库（161）被执行时，使得计算节点（102）总体 上工作以进行根据本发明的实施例的集体操作协议选择。在图2的示例 中，级别（212）调用具有一个或多个操作参数（214）的集体操作 （220）并且并行通信库（161）开始针对该集体操作（220）的协议 （222）选择。并行通信库（161）可以在反复过程中选择用于执行该集 体操作的协议（222）之一，从第一预期协议开始，一直持续到满足预 定性能标准的预期协议。选择过程的每次重复包括向用于由存储在协议 的元数据（224）中的指针（226）引用的预期协议的协议性能函数 （228）提供所述集体操作（220）的操作参数（214）。通过针对预期协 议（222）采用所述操作参数（214）评估预定义性能拟合方程（230） 从而计算针对所述操作参数（214）的该预期协议（222）的性能度量 （218），性能函数（228）确定针对所述操作参数（214）该预期协议是 否满足预定义性能标准（216）。如果计算的性能度量（218）大于在性 能标准（216）中阐述的预定义最小性能阈值，则性能函数确定该预期 协议满足预定性能标准（216）并且选择该预期协议（222）作为用于执 行所述集体操作（220）的协议。并行通信库（161）然后利用所选择的 协议执行所述集体操作。

在RAM（156）中还存储了操作系统（162），即，用于应用程序访 问计算节点的其它资源的计算机程序指令和例程的模块。通常，并行计 算机的计算机节点中的应用程序和并行通信库在无用户登录且无安全问 题的情况下进行单线程执行，因为该线程被授权完全访问该节点的所有 资源。因此，要由并行计算机中的计算节点上的操作系统执行的任务的 数目和复杂度要比许多线程同时运行的串行计算机上的操作系统的情况 更少和更简单。此外，在图2的计算节点（102）上没有视频I/O，这是 降低对操作系统的需求的另一个因素。因此，与通用计算机的操作系统 （精简版本）或特别为特定并行计算机上的操作开发的操作系统相比， 操作系统（162）可以是非常轻载的。可有用地进行改进、简化以应用 于计算节点的操作系统包括UNIX^TM、Linux^TM、Windows XP^TM、 AIX^TM、IBM的i5/OS^TM以及本领域技术人员可想到的其它操作系统。

图2的示例计算节点（102）包括与并行计算机的其它节点进行数 据通信的几个通信适配器（172、176、180、188）。这些数据通信可以 通过RS-232连接、通过例如USB的外部总线、通过例如IP网络的数 据通信网络以及本领域技术人员可以想到的其它方式串行地执行。通信 适配器实现硬件水平的数据通信，通过该通信适配器，一个计算机直接 或通过网络向另一个计算机发送数据通信。可应用于能够执行并行计算 机中的集体操作协议选择的设备中的通信适配器的示例包括用于有线通 信的调制解调器、用于有线网络通信的以太网（IEEE 802.3）适配器和 用于无线网络通信的802.11b适配器。

图2的示例中的数据通信适配器包括吉比特以太网适配器（172）， 用于将示例计算节点（102）耦合到吉比特以太网（174）以进行数据通 信。吉比特以太网是在IEEE 802.3标准中定义的提供每秒十亿比特 （一吉比特）的数据率的网络传输标准。吉比特以太网是在多模光纤光 缆、单模光纤光缆或未屏蔽双绞线上工作的以太网的变型。

图2的示例中的数据通信适配器包括JTAG从电路（176），用于将 示例计算节点（102）耦合到JTAG主电路（178）以进行数据通信。 JTAG是用于使用边界扫描来测试印刷线路板的测试访问端口的、标题 为标准测试访问端口和边界扫描架构的IEEE 1149.1标准的常用名称。 JTAG的适用范围如此广泛以致此时边界扫描或多或少与JTAG同义。 JTAG不仅用于印刷线路板，还用于执行集成电路的边界扫描，并且还 用作用于调试嵌入式系统、在该系统中提供便利的另选接入点的机制。 图2的示例计算节点可以是所有这三个：它通常包括安装在印刷线路板 上的一个或多个集成电路并且可以被实现为具有它自己的处理核、它自 己的存储器和它自己的I/O能力的嵌入式系统。通过JTAG从（176） 的JTAG边界扫描可高效地配置计算节点（102）中的处理核寄存器和 存储器，用于动态地向用于根据本发明的实施例的并行计算机中的集体 操作协议选择的系统中的一批计算节点重分配连接的节点。

图2的示例中的数据通信适配器包括点对点网络适配器（180），用 于将示例计算节点（102）耦合到对于进行点对点消息传递操作最优的 网络（108）（例如，被构造为三维环或网格的网络）以进行数据通信。 点对点适配器（180）通过6个双向链路+x(181)、-x(182)、+y(183)、- y(184)、+z(185)和-z(186)，在三个通信轴x、y和z上的6个方向上提供 数据通信。

图2的示例中的数据通信适配器包括全局组合网络适配器（188）， 用于将示例计算节点（102）耦合到对于集体消息传递操作最佳的全局 组合网络（106）（例如被构造为二叉树的网络）以进行数据通信。全局 组合网络适配器（188）经由三个双向链路为全局组合网络适配器 （188）支持的每个全局组合网络（106）提供数据通信。在图2的示例 中，全局组合网络适配器（188）通过三个双向链路为全局组合网络 （106）提供数据通信：两个到达孩子节点（190），一个到达父节点 （192）。

示例计算节点（102）包括多个算术逻辑单元（ALU）。每个处理核 （165）包括ALU（166），并且单独的ALU（170）专用于全局组合网 络适配器（188）以用于执行包括allreduce操作的归约操作的算术和逻 辑函数。并行通信库（161）中的归约例程的计算机程序指令可以将算 术或逻辑函数的指令锁存到指令寄存器（169）。当归约操作的算术或逻 辑函数是“和”或“逻辑或”时，例如，集体操作适配器（188）可以通过 使用处理核（165）中的ALU（166）执行算术或逻辑操作或者通过使 用专用ALU（170）使用由全局组合网络（106）上的节点（190、 192）提供的数据和由计算节点（102）上的处理核（165）提供的数据 通常快得多地执行算术或逻辑操作。

然而，常常当在全局组合网络适配器（188）中执行算术操作时， 全局组合网络适配器（188）仅仅用于组合从孩子节点（190）接收的数 据并且将结果沿网络（106）向上传递给父节点（192）。类似地，全局 组合网络适配器（188）可以仅仅用于发送从父节点（192）接收的数据 并且将数据沿网络（106）向下传递给孩子节点（190）。即，计算节点 （102）上的处理核（165）都没有贡献改变ALU（170）的输出并且然 后被向上或向下通过全局组合网络（106）传递的数据。由于ALU （170）通常直到ALU（170）从处理核（165）之一接收到输入才在网 络（106）上输出数据，所以处理核（165）可以将身份元素注入专用 ALU（170）以用于在ALU（170）中执行特定算术操作以防止ALU （170）的输出被改变。然而，将身份元素注入ALU常常消耗大量处理 周期。为了进一步增强这些情况下的性能，示例计算节点（102）包括 专用硬件（171），用于将身份元素注入ALU（170）以减少防止ALU 输出的改变所需的处理核资源的量。专用硬件（171）注入与由ALU执 行的特定算术操作对应的身份元素。例如，当全局组合网络适配器 （188）对从孩子节点（190）接收的数据执行位或时，专用硬件 （171）可以将零注入到ALU（170）以提高整个全局组合网络（106） 的性能。

为了进一步进行解释，图3A阐述了用于根据本发明的实施例的并 行计算机中的集体操作协议选择的系统的示例点对点适配器（180）的 框图。点对点适配器（180）被设计用于针对点对点操作而优化的数据 通信网络、以三维环或网格组织计算机节点的网络。图3A的示例中的 点对点适配器（180）沿x轴经由四个单向数据通信链路，向以及自-x 方向（182）上的下一个节点提供数据通信，并且向以及自+x方向 （181）上的下一个节点提供数据通信。图3A的点对点适配器（180） 还沿y轴通过四个单向数据通信链路，向以及自-y方向（184）上的下 一个节点提供数据通信并且向以及自+y方向（183）上的下一个节点提 供数据通信。图3A的点对点适配器（180）还沿z轴通过四个单向数据 通信链路，向以及自-z方向（186）上的下一个节点提供数据通信并且 向以及自+z方向（185）上的下一个节点提供数据通信。

为了进一步解释，图3B阐述了用于根据本发明的实施例的并行计 算机中的集体操作协议选择的系统中的示例全局组合网络适配器 （188）的框图。全局组合网络适配器（188）被设计用于针对集体操作 进行优化的网络、以二叉树组织并行计算机的计算节点的网络。图3B 的示例中的全局组合网络适配器（188）通过四个单向数据通信链路 （190）提供去往和来自全局组合网络的孩子节点的数据通信，还通过 两个单向数据通信链路（192）提供去往和来自全局组合网络的父节点 的数据通信。

为了进一步解释，图4阐述了示出用于能够执行根据本发明的实施 例的并行计算机中的集体操作协议选择的系统的针对点对点操作进行优 化的示例数据通信网络（108）的线路图。在图4的示例中，点表示并 行计算机的计算节点（102），点之间的虚线表示计算节点之间的数据通 信链路（103）。通过与例如图3A所示相似的点对点数据通信适配器实 现所述数据通信链路，其中，所述数据通信链路在三个轴x、y和z上 并且在+x（181）、-x（182）、+y（183）、-y（184）、+z（185）和-z （186）这六个方向上往返。这些链路和计算节点被针对点对点操作进 行优化的这个数据通信网络组织成三维网格（105）。网格（105）具有 每个轴上的缠绕链路，用于连接网格（105）的相对侧的网格（105）中 的最外计算节点。这些缠绕链路形成环（107）。环中的每个计算节点在 环中的位置由一个x、y和z坐标组唯一指定。读者将明白，为了清 楚，y和z方向的缠绕链路已经被省去，但是以与在x方向上所示的缠 绕链路相似的方式构造。为了清楚地进行解释，图4的数据通信网络仅 仅示出了27个计算节点，但是读者应该明白，用于根据本发明的实施 例的并行计算机中的集体操作协议选择的针对点对点操作进行优化的数 据通信网络可以仅仅包含几个计算节点或者可以包含几千个计算节点。 为了易于进行解释，图4的数据通信网络仅仅以三维示出，但是读者应 该明白，用于根据本发明的实施例的并行计算机中的集体操作协议选择 的针对点对点操作进行优化的数据通信网络实际上能够以二维、四维、 五维等进行实现。几个超级计算机现在使用五维网格或环网络，例如包 括IBM的Blue Gene Q_TM。

为了进一步进行解释，图5阐述了示出用于能够执行根据本发明的 实施例的并行计算机中的集体操作协议选择的系统中的示例全局组合网 络（106）的线路图。图5的示例数据通信网络包括连接到计算节点以 将计算节点组织成树的数据通信链路（103）。在图5的示例中，点表示 并行计算机的计算节点（102），点之间的虚线（103）表示计算节点之 间的数据通信链路。通过与例如图3B中所示相似的全局组合网络适配 器实现所述数据通信链路，其中，除了一些例外情况，每个节点通常提 供去往和来自两个孩子节点的数据通信以及去往和来自父节点的数据通 信。全局组合网络（106）中的节点可以被刻画为物理根节点（202）、 分支节点（204）和叶节点（206）。物理根（202）具有两个孩子但没有 父辈并且之所以如此称呼是因为物理根节点（202）是在二叉树的顶部 物理构造的节点。叶节点（206）均具有父辈但叶节点没有孩子。分支 节点（204）均具有父辈和两个孩子。这些链路和计算节点由此被针对 集体操作进行优化的这个数据通信网络组织成二叉树（106）。为了清楚 地进行解释，图5的数据通信网络仅仅示出了31个计算节点，但是读 者应该明白，用于根据本发明的实施例的并行计算机中的集体操作协议 选择的针对集体操作进行优化的全局组合网络（106）可以仅仅包含几 个计算节点或者可以包含几千个计算节点。

在图5的示例中，树中的每个节点被分配称作“级别”（250）的单 元标识符。该级别实际上识别执行根据本发明的实施例的并行操作的任 务或过程。使用级别来识别节点假定了在每个节点上正在执行仅仅一个 这样的任务。在超过一个参与任务在一个节点上执行的程度上，该级别 如此识别任务而不是节点。级别唯一地识别用于树网络中的点对点操作 和集体操作两者的树网络中的任务的位置。这个示例中的级别被分配为 从0开始的整数，其中，0被分配给根任务或根节点（202），1被分配 给树的第二层中的第一节点，2被分配给树的第二层中的第二节点，3 被分配给树的第三层中的第一节点，4被分配给树的第三层中的第二节 点，依此类推。为了易于进行显示，这里仅仅示出了树的前三层的级 别，但是树网络中的所有计算节点都被分配一个唯一级别。

为了进一步进行解释，图6阐述了示出用于根据本发明的实施例的 并行计算机中的集体操作协议选择的示例方法的流程图。在例如与图1 所示的并行计算机（100）相似的包括多个计算节点的并行计算机中执 行图6的方法。

图6的方法包括调用（602）具有一个或多个操作参数的集体操 作。通过对由并行通信库提供的函数执行函数调用可以执行调用 （602）具有一个或多个操作参数的集体操作，其中，所述函数表示特 定类型的集体操作。集体操作的示例包括归约操作、广播操作、收集操 作等。

每个集体操作可以以各种方式执行。执行集体操作的每种方式被称 作协议。即，每个集体操作可以包括多个协议，其中，每个协议被构造 为实现或执行该集体操作。为此，图6的方法包括选择（604）用于执 行集体操作的多个协议之一。这种选择（604）是反复的过程，该反复 过程针对集体操作的每个预期协议执行一次，从第一预期协议开始并且 当一个预期协议满足预定性能标准时结束。

为此，图6的方法包括向用于预期协议的协议性能函数提供集体操 作的操作参数（606）。向用于预期协议的性能函数提供集体操作的操作 参数（606）可以通过传递操作参数作为对性能函数的函数调用的参数 来执行。考虑对归约集体操作的第一预期协议的性能函数进行下面的示 例函数调用：

bool ProtocolFit=(*Perf_Func_Reduce_Protocol1)(MsgSize,MsgType)； 在以上的示例函数调用中，指针*Perf_Func_Reduce_Protocol1是指向 归约操作的第一协议的性能函数的指针。这个指针可以存储在与该预期 协议关联并且描述该预期协议的元数据中。执行协议的选择（604）的 并行通信库可以从协议的元数据取回函数指针以执行函数调用。

向性能函数传递的参数包括MsgSize（即，在归约操作中传递的消 息的消息大小）和MsgType（即，在归约操作中传递的消息的类型）。 在这个示例中，MsgSize和MsgType是集体操作自身的相同操作参数。 性能函数的返回值是作为变量“ProtocolFit”进行存储的布尔值。 ProtocolFit的值为真指示针对该集体操作和参数组该协议满足预定义性 能标准，并且ProtocolFit的值为假指示针对该集体操作和参数组该协 议不满足预定义性能标准。

性能函数通过确定（608）针对所述操作参数该预期协议是否满足 预定义性能标准来确定是返回真值还是假值。预定义性能标准可以是表 示特定协议的优选最小性能水平的任何标准。可使用的性能的类型的示 例是包括集体操作的执行时间、执行集体操作的网络带宽利用率、执行 集体操作的存储器资源利用率、执行集体操作的处理器资源利用率等的 标准。

预定义性能标准的值可以被提供给性能函数，作为对性能标准的函 数调用的参数。即，对于协议选择，每个集体操作或者每个集体操作的 每个实例可以具有要满足的独立的不同的性能标准。或者，预定义性能 标准可以是所有集体操作的所有协议的性能函数可用的单个全局可访问 值。

在图6的方法中，针对操作参数确定（608）预期协议是否满足预 定义性能标准包括通过所述操作参数评估预期协议的预定义性能拟合方 程。预定义性能拟合方程是定义在一定范围的不同操作参数组上的协议 的性能度量的方程。该拟合方程可以是通过回归分析（即，实际性能的 近似）建立的方程。在图6的方法中评估（610）这种拟合方程包括计 算（612）针对所述操作参数的该预期协议的性能度量。

通过确定（614）计算的性能度量是否大于预定义最小性能阈值， 确定（608）针对所述操作参数该预期协议是否满足预定义性能标准的 操作继续。预定义最小性能阈值是由预定性能标准指定的值。即，在大 多数实施例中，预定性能标准是预定义最小性能阈值。

如果计算的性能度量不大于预定义最小性能阈值，则图6的方法在 选择（604）过程的另一次反复中利用另一个预期协议继续（616）。如 果计算的性能度量大于预定义最小性能阈值，则图6的方法通过选择 （618）该预期协议作为用于执行集体操作的协议并且利用选择的协议 执行（620）集体操作而继续。

为了进一步进行解释，图7阐述了示出用于根据本发明的实施例的 并行计算机中的集体操作协议选择的另一个示例方法的流程图。图7的 示例方法与图6的示例方法的相似之处在于也包括：调用（602）具有 操作参数的集体操作；选择（604）协议，包括：向协议性能函数提供 （606）操作参数，确定（608）预期协议是否满足预定义性能标准，评 估（610）预定义性能拟合方程，计算（612）性能度量，仅当计算的性 能度量大于预定义最小性能阈值才选择（618）该预期协议；以及利用 选择的协议执行（620）集体操作。

然而，图7的方法与图6的方法的不同之处在于，图7的方法包括 在实际协议选择之前（即，在调用集体操作之前）执行的协议性能确定 的缓存过程。换言之，在协议选择（604）之前针对集体操作的一组或 多组操作参数以及一个或多个预期协议执行图7的方法中的缓存过程。 对于每组操作参数和每个预期协议，图7的方法包括确定（702）预期 协议是否满足预定性能标准。在计算节点的工作组的建立（704）过程 中，图7的方法包括缓存（708）满足预定性能标准的预期协议的每个 确定，而不缓存（708）不满足预定性能标准的预期协议的确定。作为 示例考虑在建立（704）计算节点的工作组之前用户利用10组操作参数 针对单个集体操作（即，归约操作）启动缓存过程。对于归约操作的每 个协议以及对于10组操作参数中的每一组，图7的缓存过程将确定针 对该组操作参数该协议是否满足预定义性能标准。对于每个肯定确定 （即，协议针对一组特定操作参数满足预定义性能标准的确定），在建 立（704）计算节点的工作组时，缓存过程将缓存该确定。可以通过各 种方式执行缓存确定，这些方式例如包括，将每个确定存储在存储器中 并且将指向该确定的指针插入到对应协议的元数据中，将确定插入存储 在公知的存储位置的表或其它数据结构中，以及本技术领域的读者可以 想到的其它等等。

一旦计算节点的工作组被建立（704）并且满足性能标准的集体操 作的协议的肯定确定已经被缓存，选择（604）用于执行集体操作的协 议的过程包括针对集体操作的操作参数确定是否存在缓存的满足预定性 能标准的预期协议的确定。如果存在缓存的满足预定性能标准的预期协 议的确定，则选择（604）选择（712）该预期协议作为用于执行集体操 作的协议，而不在协议选择过程中计算针对操作参数的预期协议的性能 度量。即，不是完成向性能函数提供（606）操作参数、评估性能函 数、计算性能度量等这样的一个个反复，图7的方法包括基于缓存的确 定选择协议（绕开这些反复）。当缓存的确定可用时，这里在图7中阐 述的缓存确定可以通过绕开一次或多次反复而提高选择（604）用于执 行集体操作的协议的速度和效率。

为了进一步进行解释，图8阐述了示出根据本发明的实施例的并行 计算机中的集体操作协议选择的另一个示例方法的流程图。图8的示例 方法与图6的示例方法的相似之处在于也包括：调用（602）具有操作 参数的集体操作；选择（604）协议，包括：向协议性能函数提供 （606）操作参数，确定（608）预期协议是否满足预定义性能标准，评 估（610）预定义性能拟合方程，计算（612）性能度量，仅当计算的性 能度量大于预定义最小性能阈值才选择（618）该预期协议；以及利用 选择的协议执行（620）集体操作。

然而，图8的方法与图6的方法不同，在图8的方法中包括为集体 操作的每个协议建立（802）预定义性能拟合方程。在图8的方法中， 建立（802）预定义性能拟合方程包括：对于多组操作参数中的每一组 执行一次该协议，对每次执行记录（806）性能度量，以及针记录的性 能度量计算（808）拟合方程。可以通过各种方式执行针对记录的性能 度量计算（808）拟合方程，这些方式例如包括计算线性近似拟合方 程、立方近似拟合方程和四次近似拟合方程。可以执行回归分析以计算 拟合方程。

本技术领域的读者将认识到，当特定协议的性能有些可变时，这种 通过拟合方程的近似是有用的。与之相比，在一些情形下，可以确切地 知道特定协议的性能。即，一些协议的性能实质上是确定性的。在这种 实施例中，针对记录的性能度量计算（808）拟合方程可以包括针对所 有可能的操作参数计算确切函数。

本领域技术人员应该明白，本发明的各方面可以被实施为系统、方 法或计算机程序产品。因此，本发明的各方面可以采取完全硬件实施 例、完全软件实施例（包括固件、驻留软件、微码等）或组合软件和硬 件方面的实施例的形式，在这里它们全部总体上可以被称作“电路”、 “模块”或“系统”。另外，本发明的各方面可以采取计算机程序产品的形 式，该计算机程序产品在一个或多个计算机可读介质中实施，在该计算 机可读介质上实施有计算机可读程序代码。

可以利用一个或多个计算机可读介质的任何组合。计算机可读介质 可以是计算机可读传输介质或计算机可读存储介质。计算机可读存储介 质例如可以是但不限于电子、磁性、光学、电磁、红外或半导体系统、 设备、或装置或者上述的任何合适组合。计算机可读存储介质的更具体 示例（非穷尽性列表）将包括如下：具有一个或多个导线的电连接、便 携式计算机盘、硬盘、随机存取存储器（RAM）、只读存储器 （ROM）、可擦除可编程只读存储器（EPROM或闪存）、光纤、便携 式紧凑盘只读存储器（CD-ROM）、光存储装置、磁存储装置或者上述 的任何合适组合。在本文的上下文中，计算机可读存储介质可以是能够 包含或存储由指令执行系统、设备或装置使用或者与它们结合使用的程 序的任何有形介质。

计算机可读传输介质可以包括例如在基带中或者作为载波的一部分 传播的数据信号，在该数据信号内实施了计算机可读程序码。这种传播 的信号可以采用各种形式的任何一种，包括但不限于电磁、光学、或者 它们的任何合适组合。计算机可读传输介质可以是并非计算机可读存储 介质并且能够传送、传播或传输由指令执行系统、设备或装置使用或与 它们结合使用的程序的任何计算机可读介质。

可以使用任何适合的介质发送在计算机可读介质上实施的程序码， 该介质包括但不限于无线、有线、光纤、RF等或者上述的任何合适组 合。

可以通过一种或多种编程语言的任何组合编写用于执行本发明的各 方面的操作的计算机程序码，这些编程语言包括诸如Java、 Smalttalk、C++等的面向对象编程语言和诸如“C”编程语言或相似编程 语言的传统过程编程语言。该程序码可以完全在用户的计算机上、部分 在用户的计算机上、作为单机软件包、部分在用户的计算机上且部分在 远程计算机上或者完全在远程计算机或服务器上执行。在后者的情形 下，远程计算机可以通过包括局域网（LAN）或广域网（WAN）的任 何类型的网络连接到用户的计算机，或者可以连接到外部计算机（例 如，使用互联网服务提供商通过互联网）。

在上文中参照根据本发明的实施例的方法、设备（系统）和计算机 程序产品的流程图和/或框图描述本发明的各方面。应该明白，流程图 和/或框图的每个块以及流程图和/或框图中的块的组合能够由计算机程 序指令实现。这些计算机程序指令可以提供给通用计算机、专用计算机 或者其它可编程数据处理设备的处理器以生成一机器，从而经由计算机 或其它可编程数据处理设备的处理器执行的指令建立实现在流程图和/ 或框图块中指定的功能/动作的装置。

这些计算机程序指令还可以存储在计算机可读介质中以能够引导计 算机、其它可编程数据处理设备或其它装置以特定方式工作，从而存储 在计算机可读介质中的指令生成包括实现在流程图和/或框图块中指定 的功能/动作的指令的制品。

计算机程序指令还可以加载到计算机、其它可编程数据处理设备或 其它装置上以使得在计算机、其它可编程设备或其它装置上执行一系列 操作步骤以生成计算机实现的过程，从而在计算机或其它可编程设备上 执行的指令提供用于实现在流程图和/或框图块中指定的功能/动作的过 程。

附图中的流程图和框图示出了根据本发明的各种实施例的系统、方 法和计算机程序产品的可能实现方式的架构、功能和操作。关于此，流 程图或框图中的每个块可以表示包括用于实现指定的逻辑功能的一个或 多个可执行指令的代码的模块、段或部分。还应该注意，在一些另选实 施方式中，块中注释的功能可以不按附图中注释的顺序发生。例如，接 连示出的两个块实际上可以基本上同时执行，或者这些块有时候可以以 相反顺序执行，这取决于涉及的功能。还应注意，框图和/或流程图的 每个块以及框图和/或流程图中的块的组合能够由执行指定功能或动作 的基于专用硬件的系统或者专用硬件和计算机指令的组合进行实现。

从上述描述应该明白，在不脱离本发明的真实精神的情况下可以在 本发明的各种实施例中执行变型和改变。本说明书中的说明仅仅用于例 示的目的而非以限制意义进行解释。本发明的范围仅由权利要求的语言 进行限制。