在并行计算机的计算节点处处理非预期消息的方法和装置

摘要

本发明提供了用于在并行计算机的计算节点处处理非预期消息的方法、装置和计算机程序产品。实施例包括由计算节点接收来自所述并行计算机的另一计算节点的消息的一部分，所述消息包括多个分离的部分；响应于接收到所述消息的部分，由该计算节点确定在该计算节点上执行的应用之一是否已经指示该消息是预期的；如果在该计算节点上执行的应用之一没有指示该消息是预期的，则由该计算节点将所述消息的部分存储在该计算节点内的非预期消息缓冲器中；以及如果在该计算节点上执行的应用之一指示该消息是预期的，则由该计算节点将所述消息的部分存储在该消息所指示的存储目的地处。

说明书

技术领域

本发明的领域是数据处理，更具体地，是用于在并行计算机的计算节点 处处理非预期消息的方法、装置和计算机程序产品。

背景技术

1948年EDVAC计算机系统的开发通常被称为计算机时代的开始。自从 那时起，计算机系统已经发展为极其复杂的设备。当今的计算机比诸如 EDVAC的早期系统复杂得多。计算机系统通常包括硬件和软件组件、应用程 序、操作系统、处理器、总线、存储器、输入/输出设备等等的组合。随着半 导体处理和计算机架构的进步将计算机的性能推向越来越高，更复杂的计算 机软件已经发展为利用更高性能的硬件，得到比仅几年前强大得多的当今的 计算机系统。

现代的计算系统可以是整体并行的并且包括在计算系统内的许多计算节 点。并行计算是将算法分割或者划分为通常称为线程的单元，这些单元同时 或者并发地在多个处理器上执行。然后这些多线程的中间结果被组合为最终 结果。因此，并行计算是基于以下思想：解决问题的处理通常可以被划分为 更小的任务，这些更小的任务可以通过某些协调同时实行。并行算法是有价 值的，因为通过更小任务的并行执行来进行大的任务可以比经由一个串行（非 并行）算法进行大的任务更快。

并行线程通常在包括多个处理器的计算机系统上或者在多个包括处理器 的计算机系统（通常称为计算节点或者简称为节点）上实现，这些处理器运 行全局应用的并行线程或者本地实例以完成任务。对于具体节点而言处于本 地的一个或多个并行线程需要与其他并行线程通信的方式，这通常经由已知 为消息传递的技术来实现。为了确保各节点之间的适当通信，已经开发了已 知为消息传递接口（MPI）的标准。

在MPI标准下，MPI程序由不需要等同的执行其自己的代码的自主处理 组成。通常，每个处理或者应用经由对于MPI通信基元（primitive）的调用 来通信，其中每个处理在其自己的并且共享的存储器中执行。这样的消息传 递允许包括节点以及在节点上运行的应用（全局应用或处理的线程或实例） 的本地处理器彼此协作。MPI可用在各种广泛的平台上，范围从工作站的网 络到整体并行的系统。计算节点接收的每个消息最终由该计算节点存储。在 具有几百个或者几千个计算节点的并行计算机中，其中每个计算节点连续存 储数千条消息，消息的有效存储在并行计算机的整体效率中起着重要作用。

发明内容

提供了用于在并行计算机的计算节点处处理非预期消息的方法、装置和 计算机程序产品。实施例包括由计算节点接收来自所述并行计算机的另一计 算节点的消息的一部分，所述消息包括多个分离的部分；响应于接收到所述 消息的部分，由该计算节点确定在该计算节点上执行的应用之一是否已经指 示该消息是预期的；如果在该计算节点上执行的应用之一没有指示该消息是 预期的，则由该计算节点将所述消息的部分存储在该计算节点内的非预期消 息缓冲器中；以及如果在该计算节点上执行的应用之一指示该消息是预期的， 则由该计算节点将所述消息的部分存储在该消息所指示的存储目的地处。

本发明的以上以及其他目标、特征和优点将从如在附图中例示的本发明 的示例实施例的以下更具体的描述而显而易见，附图中类似的参考标记一般 表示本发明的示例实施例的类似的部分。

附图说明

图1例示用于根据本发明的实施例在并行计算机的计算节点处处理非预 期消息的示例系统。

图2给出根据本发明的实施例在能够在并行计算机的计算节点处处理非 预期消息的并行计算机中有用的示例计算节点的框图。

图3A给出根据本发明的实施例在用于在并行计算机的计算节点处处理 非预期消息的系统中有用的示例点对点适配器的框图。

图3B给出根据本发明的实施例在用于在并行计算机的计算节点处处理 非预期消息的系统中有用的示例全局组合网络适配器的框图。

图4给出例示根据本发明的实施例在能够在并行计算机的计算节点处处 理非预期消息的系统中有用的对于点对点操作优化的示例数据通信网络的线 条图。

图5给出例示根据本发明的实施例在能够在并行计算机的计算节点处处 理非预期消息的系统中有用的示例全局组合网络的线条图。

图6给出例示根据本发明的实施例用于在并行计算机的计算节点处处理 非预期消息的示例方法的流程图。

具体实施方式

参考附图描述根据本发明的用于在并行计算机的计算节点处处理非预期 消息的示例方法、装置和计算机程序产品，以图1开始。

图1例示根据本发明的实施例的用于在并行计算机的计算节点处处理非 预期消息的示例系统。图1的系统包括并行计算机（100）、数据存储设备（118） 形式的用于该计算机的非易失性存储器、打印机（120）形式的用于该计算机 的输出设备以及计算机终端（122）形式的用于该计算机的输入/输出设备。

在图1的例子中的并行计算机（100）包括多个计算节点（102）。计算节 点（102）通过几种独立的数据通信网络耦接用于数据通信，该几种独立的数 据通信网络包括高速以太网络（174）、联合测试行动组（“JTAG”）网络（104）、 使用二叉树网络拓扑的对于集合操作优化的全局组合网络（106）、以及使用 环状网络拓扑的对于点对点操作优化的点对点网络（108）。全局组合网络 （106）是包括连接到计算节点（102）的数据通信链接以便将计算节点（102） 组织为二叉树的数据通信网络。每个数据通信网络利用在计算节点（102）之 间的数据通信链接实现。数据通信链接提供用于并行计算机（100）的计算节 点（102）之间的并行操作的数据通信。

并行计算机（100）的计算节点（102）被组织为用于并行计算机（100） 上的集合并行操作的计算节点的至少一个操作组（132）。计算节点的每个操 作组（132）是这样的计算节点的集合：集合并行操作在这些节点上执行。操 作组（132）中的每个计算节点被分配了标识该操作组（132）中的特定计算 节点的唯一秩（rank）。利用操作组的计算节点之间的数据通信实现集合操作。 集合操作是涉及操作组（132）的所有计算节点的那些功能。集合操作是由计 算节点的操作组（132）中的所有计算节点同时、即近似在相同时间执行的操 作、即消息传递型计算机程序指令。这样的操作组（132）可以包括并行计算 机（100）中的所有计算节点（102）或者所有计算节点（102）的子集。集合 操作通常围绕点对点操作而建立。集合操作需要在操作组（132）内的所有计 算节点上的所有处理利用匹配的变量调用相同的集合操作。“广播”是用于在 操作组的计算节点之间移动数据的集合操作的例子。“归约（reduce）”操作是 对分布在操作组（132）的计算节点之间的数据执行算术或逻辑功能的集合操 作的例子。操作组（132）可以实现为例如MPI“通信器”。

“MPI”指“消息传递接口”，即现有技术的并行通信库，即用于并行计 算机上的数据通信的计算机程序指令的模块。可以改进以用在根据本发明的 实施例而配置的系统中的现有技术的并行通信库的例子包括MPI和“并行虚 拟机”（“PVM”）库。PVM由田纳西(Tennessee)大学、橡树岭国家实验室(Oak Ridge National Laboratory)和埃默里(Emory)大学开发。MPI由MPI论坛公布， MPI论坛即具有来自定义和维护MPI标准的许多组织的代表的开放组。在撰 写本文时MPI是用于在分布式存储器并行计算机上运行并行程序的计算节点 之间通信的实际标准。为了易于说明，本说明书有时使用MPI术语，不过像 这样使用MPI不是本发明的要求或者限制。

一些集合操作具有在操作组（132）中的特定计算节点上运行的单个发起 或接收处理。例如，在“广播”集合操作中，在计算节点上的将数据分发到 所有其他计算节点的处理是发起处理。例如，在“聚集”操作中，在计算节 点上的接收来自其他计算节点的所有数据的处理是接收处理。这样的发起或 者接收处理在其上运行的计算节点被称为逻辑根。

大多数集合操作是四个基本操作的变型或组合：广播、聚集、散布和归 约。用于这些集合操作的接口在由MPI论坛公布的MPI标准中定义。但是， 在该MPI标准中未定义用于执行集合操作的算法。在广播操作中，所有处理 指定相同的根处理，其缓冲器内容将被发送。除了根之外的处理指定接收缓 冲器。在该操作之后，所有缓冲器包含来自该根处理的消息。

像广播操作那样，散布操作也是一对多集合操作。在散布操作中，逻辑 根将根上的数据划分为片段并且将不同的片段分发到操作组（132）中的每个 计算节点。在散布操作中，所有处理通常指定相同的接收计数。发送变量仅 对于根处理是重要的，该根处理的缓冲器实际上包含了给定数据类型的发送 计数*N元素，其中N是给定组的计算节点中的处理的数量。发送缓冲器被划 分并散发到所有处理（包括在逻辑根上的处理）。每个计算节点被分配了称为 “秩”的顺序标识符。在该操作之后，根已经按增加的秩的顺序向每个处理 发送了发送计数(sendcount)数据元素。秩0接收来自发送缓冲器的第一发送 计数数据元素。秩1接收来自发送缓冲器的第二发送计数数据元素，等等。

聚集操作是与散步操作的描述完全相反的多对一集合操作。即，聚集是 多对一集合操作，其中将来自排序了(ranked)的计算节点的某数据类型的元素 聚集到根节点中的接收缓冲器中。

归约操作也是多对一集合操作，其包括对两个数据元素进行的算术或逻 辑功能。所有处理指定相同的“计数”和相同的算术或逻辑功能。在该归约 之后，所有处理已将来自计算节点发送缓冲器的计数数据元素发送到根处理。 在归约操作中，来自相应的发送缓冲器位置的数据元素通过算术或逻辑操作 被成对地组合以产生根处理的接收缓冲器中的单个相应的元素。可以在运行 时定义专用归约操作。并行通信库可以支持预定操作。例如，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节点组成。在一些其 他配置中，每个处理集可以由六十四个计算节点和一个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）通常操作用于根据本发明的实施例在并行计算 机的计算节点处处理非预期消息。为了处理非预期消息，多个计算节点（102） 中的每个计算节点可以包括消息单元（199）。消息单元可以包括用于处理由 计算节点接收的消息并用于将消息从计算节点传送到并行计算机的其他计算 节点的硬件或软件。在一个具体实施例中，图1的消息单元（199）包括在由 该计算节点的处理器执行时致使该计算节点实行以下步骤的计算机程序指 令：由该计算节点接收来自并行计算机的另一计算节点的消息的一部分；响 应于接收到消息的该部分，由该计算节点确定在该计算节点上执行的应用之 一是否已经指示该消息是预期的；如果在该计算节点上执行的应用之一没有 指示该消息是预期的，则由该计算节点将该消息的该部分存储在该计算节点 内的非预期消息缓冲器中；以及如果在该计算节点上执行的应用之一已经指 示该消息是预期的，则由该计算节点将该消息的该部分存储在由该消息指示 的存储目的地处。

根据本发明的实施例在并行计算机的计算节点处处理非预期消息通常在 包括通过至少一个数据通信网络被组织用于集合操作的多个计算节点的并行 计算机上实现。事实上，这样的计算机可以包括几千个这样的计算节点。每 个计算节点本身又是一种由一个或多个计算机处理核、其自己的计算机存储 器以及其自己的输入/输出适配器组成的计算机。

为了进一步说明，图2给出在根据本发明的实施例能够在并行计算机的 计算节点处处理非预期消息的并行计算机中有用的示例计算节点（102）的框 图。图2的计算节点（102）包括多个处理核（165）以及RAM（156）。图2 的处理核（165）可以配置在一个或多个集成电路晶片上。处理核（165）通 过高速存储器总线（155）连接到RAM（156）并通过总线适配器（194）和 扩展总线（168）连接到计算节点的其他组件。

存储在RAM（156）中的是并行通信库（161），即在计算节点之中实行 并行通信、包括点对点操作以及集合操作的计算机程序指令的库。可以使用 诸如C编程语言的传统编程语言以及使用传统的编程方法编写在两个独立数 据通信网络上的节点之间发送和接收数据的并行通信例程来从头开发并行通 信例程的库以用在根据本发明的实施例的系统中。或者，可以改进已有的现 有技术库以根据本发明的实施例而操作。现有技术的并行通信库的例子包括 “消息传递接口”（“MPI”）库以及“并行虚拟机”（“PVM”）库。

还存储在RAM（156）中的是应用（270）。图2的例子中的每个应用（270） 可以配置为并行应用的一个实例，其他实例在被组织为操作组的多个计算节 点之间执行。即，应用（270）可以包括使用并行算法实行并行的用户级数据 处理的计算机程序指令的模块。

还存储在RAM（156）中的是操作系统（162），即用于应用程序对计算 节点的其他资源的访问的计算机程序指令和例程的模块。并行计算机的计算 节点中的应用程序和并行通信库典型地运行执行的单线程而不用用户登录并 没有安全问题，这是因为该线程被赋予对于该节点的所有资源的完全访问的 权利。因此并行计算机中的计算节点上的操作系统要执行的任务的数量以及 复杂性比具有同时运行的许多线程的串行计算机上的操作系统的任务更小并 且更不复杂。另外，在图2的计算节点（102）上没有视频I/O，即降低对操 作系统的要求的另一个因素。因此，与通用计算机相比，操作系统（162）可 以是非常轻量级的(lightweight)削减版本的操作系统或者专门为了具体的并 行计算机上的操作而开发的操作系统，。可以有用地改进、简化以用在计算节 点中的操作系统包括UNIX^TM、Linux^TM、Windows XP^TM、AIX^TM、IBM的i/OS^TM以及如本领域技术人员将想到的其他操作系统。

还存储在RAM（156）中的是非预期消息缓冲器（280）和投递接收队列 （posted receive queue）（282）。非预期消息缓冲器存储在计算节点上执行的 应用（270）之一指示消息是预期的之前由计算节点接收的消息的部分。使用 投递接收队列来跟踪哪些消息是预期的。也就是说，投递接收队列可以包括 标识接收请求的项（entry），该接收请求是响应于由在该计算节点上执行的应 用（270）进行的函数调用而产生的。这些接收请求是用于经由一个或多个数 据通信网络接收来自其他计算节点的数据的命令或请求。尽管非预期消息缓 冲器（280）和投递接收队列（282）被例示在RAM（156）中，但是非预期 消息缓冲器（280）和投递接收队列（282）两者可以存储在计算节点内的任 意数量的其他位置中，比如例如存储在消息单元（199）中。

图2的示例计算节点（102）包括用于实现与并行计算机的其他节点的数 据通信的几个通信适配器（172，176，180，188）。这样的数据通信可以通过 RS-232连接、通过诸如USB的外部总线、通过诸如IP网络的数据通信网络 以及按本领域技术人员将想到的其他方式串行地实行。通信适配器实现硬件 级的数据通信，通过该硬件级的数据通信，一个计算机直接地或者通过网络 向另一计算机发送数据通信。在能够在并行计算机的计算节点处处理非预期 消息的装置中有用的通信适配器的例子包括用于有线通信的调制解调器、用 于有线网络通信的以太网（IEEE802.3）适配器以及用于无线网络通信的 802.11b适配器。

图2的例子中的数据通信适配器包括为了数据通信而将示例的计算节点 （102）耦接到吉比特以太网（174）的吉比特以太网适配器（172）。吉比特 以太网是提供每秒十亿比特（一个吉比特）的数据速率的在IEEE802.3中定 义的网络传输标准。吉比特以太网是在多模光纤电缆、单模光纤电缆或者非 屏蔽双绞线上工作的以太网的变型。

图2的例子中的数据通信适配器包括为了数据通信将示例的计算节点 （102）耦接到JTAG主电路（178）的JTAG从电路（176）。JTAG是名为标 准测试访问端口和边界扫描架构的IEEE1149.1标准的普通名称，用于使用边 界扫描来测试印刷电路板的测试访问端口。JTAG如此广泛适用使得这时边界 扫描或多或少与JTAG意思相同。JTAG不仅用于印刷电路板，而且还用于进 行集成电路的边界扫描，并且作为用于调试嵌入系统、提供进入系统中的便 利的替换接入点的机制也是有用的。图2的示例的计算节点可以是这些中的 所有三个：其通常包括安装在印刷电路板上的一个或多个集成电路并且可以 实现为具有其自己的处理核、其自己的存储器以及其自己的I/O能力的嵌入 式系统。通过JTAG从属（176）的JTAG边界扫描可以有效地配置计算节点 （102）中的处理核寄存器和存储器以用于将连接的节点动态地再分配到在根 据本发明的实施例的为其开发集合操作的系统中有用的计算节点的块。

图2的例子中的数据通信适配器包括点对点网络适配器（180），该点对 点网络适配器（180）为了数据通信将示例的计算节点（102）耦接到诸如例 如配置为三维环状结构或者网状结构的网络的对于点对点消息传递操作最佳 的网络（108）。点对点适配器（180）提供通过以下六个双向链接在三个通信 轴x、y和z上的在六个方向上的数据通信：+x(181)、-x(182)、+y(183)、-y (184)、+z(185)和-z(186)。

图2的例子中的数据通信适配器包括全局组合网络适配器（188），该全 局组合网络适配器（188）为了数据通信将示例的计算节点（102）耦接到诸 如例如配置为二叉树的网络的对于集合消息传递操作最佳的全局组合网络 （106）。全局组合网络适配器（188）通过三个双向链接为该全局组合网络适 配器（188）支持的每个全局组合网络（106）提供数据通信。在图2的例子 中，全局组合网络适配器（188）通过以下三个双向链接为全局组合网络（106） 提供数据通信：两个到孩子节点（190）以及一个到双亲节点（192）。

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

但是，通常仅当在全局组合网络适配器（188）中进行算术操作时，全局 组合网络适配器（188）仅用于组合从孩子节点（190）接收的数据并将该结 果沿该网络（106）向上传递到双亲节点（192）。类似地，全局组合网络适配 器（188）可以仅用于传输从双亲节点（192）接收的数据并将该数据沿该网 络（106）向下传递到孩子节点（190）。也就是说，计算节点（102）上的处 理核（165）都不贡献(contribute)更改ALU（170）的输出的数据，该ALU（170） 的输出然后沿该全局组合网络（106）向上或向下传递。因为ALU（170）通 常在ALU（170）接收到来自处理核（165）之一的输入之前不输出任何数据 到网络（106）上，所以处理核（165）可以将身份元素注入到专用（ALU） 170中以在ALU（170）中进行特定算术操作，以便防止更改ALU（170）的 输出。但是将身份元素注入ALU中通常消耗多个处理循环。为了在这些情况 下进一步增强性能，示例的计算节点（102）包括用于将身份元素注入ALU （170）中以降低防止更改ALU输出所需的处理核资源量的专用硬件（171）。 该专用硬件（171）注入与该ALU进行的特定算术操作对应的身份元素。例 如，当全局组合网络适配器（188）对从孩子节点（190）接收的数据进行按 位或时，专用硬件（171）可以将0注入ALU（170）中以改进整个全局组合 网络（106）的性能。

为了进一步说明，图3A给出在根据本发明的实施例为其开发集合操作 的系统中有用的示例点对点适配器（180）的框图。该点对点适配器（180） 设计为用在对于点对点操作优化的数据通信网络、即按三维环状结构或网状 结构组织计算节点的网络中。图3A的例子中的点对点适配器（180）提供沿 着x轴通过四个单向数据通信链接的到-x方向上的下一节点（182）和来自该 下一节点（182）、以及到+x方向上的下一节点（181）和来自该下一节点（181） 的数据通信。图3A的点对点适配器（180）还提供沿着y轴通过四个单向数 据通信链接的到-y方向上的下一节点（184）和来自该下一节点（184）、以及 到+y方向上的下一节点（183）和来自该下一节点（183）的数据通信。图3A 的点对点适配器（180）还提供沿着z轴通过四个单向数据通信链接到的-z方 向上的下一节点（186）和来自该下一节点（186）、以及到+z方向上的下一 节点（185）以及来自该下一节点（185）的数据通信。

为了进一步说明，图3B给出在根据本发明的实施例为其开发集合操作的 系统中有用的示例的全局组合网络适配器（188）的框图。全局组合网络适配 器（188）设计为用在对于集合操作优化的网络、即按二叉树组织并行计算机 的计算节点的网络中。在图3B的例子中的全局组合网络适配器（188）提供 通过四个单向数据通信链接的到全局组合网络的孩子节点（190）以及来自这 些孩子节点（190）的数据通信，以及还提供通过两个单向数据通信链接的到 全局组合网络的双亲节点（192）以及来自该双亲节点（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 QTM。

为了进一步说明，图5给出例示在根据本发明的实施例的为其开发集合 操作的系统中有用的示例的全局组合网络（106）的线条图。图5的示例的数 据通信网络包括连接到计算节点以便将计算节点组织为树的数据通信链接 （103）。在图5的例子中，点表示并行计算机的计算节点（102），并且点之 间的虚线（103）表示计算节点之间的数据通信链接。利用类似于例如图3B 中例示的全局组合网络适配器的全局组合网络适配器来实现数据通信链接， 除了一些例外，每个节点通常提供到两个孩子节点和来自两个孩子节点的数 据通信以及到双亲节点以及来自该双亲节点的数据通信。全局组合网络（106） 中的节点可以被刻画为物理根节点（202）、分支节点（204）以及叶子节点 （206）。物理根（202）具有两个孩子但是没有双亲，并且之所以这样称呼是 因为物理根节点（202）是物理地配置在二叉树的顶部的节点。叶子节点（206） 每个具有双亲，但是叶子节点不具有孩子。分支节点（204）每个具有一个双 亲和两个孩子。链接和计算节点由此由对于集合操作优化的此数据通信网络 组织为二叉树（106）。为了清楚的说明，图5的数据通信网络被例示为仅具 有31个计算节点，但是读者将认识到用在根据本发明的实施例的为其开发集 合操作的系统中的对于集合操作优化的全局组合网络（106）可以仅包含几个 计算节点或者可以包含数千个计算节点。

在图5的例子中，树中的每个节点被分配了称为“秩”的单元标识符 （250）。秩实际上标识正执行根据本发明的实施例的并行操作的任务或处理。 使用秩来标识节点假定仅一个这样的任务正在每个节点上执行。至于多于一 个参与任务在单个节点上执行的情况，秩标识这样的任务而不是标识节点。 秩唯一地标识任务在树网络中的位置以供在树网络的点对点和集合操作两者 中使用。此例子中的秩被分配为整数，以0分配给根任务或根节点（202）、1 分配给树的第二层中的第一节点、2分配给树的第二层中的第二节点、3分配 给树的第三层中的第一节点、4分配给树的第三层中的第二节点等等而开始。 为了易于例示，在此仅示出了树的前三个层的秩，但是树网络中的所有计算 节点都被分配了唯一的秩。

为了进一步说明，图6给出例示根据本发明的实施例用于在并行计算机 的计算节点处处理非预期消息的示例方法的流程图。图6的方法包括由计算 节点（102a）接收（602）来自并行计算机（100）的另一计算节点（102b） 的消息（690）的一部分（650）。图6的消息（690）包括多个（691）部分。 也就是说，计算节点（102a）接收消息（690）的各个部分并将这些部分组合 以形成消息（690）。在一个具体实施例中，消息的每个接收的部分具有其自 己的头部以及不同于消息（690）的其他部分的有效负荷（payload）。由计算 节点（102a）接收（602）来自并行计算机（100）的另一计算节点（102b） 的消息（690）的一部分（650）可以通过在消息单元（199）内的接收缓冲器 处接收消息的一部分（650）来实行。消息单元可以使用接收缓冲器立即存储 任何到来的消息，之后在消息是非预期的情况下将消息的部分传送到非预期 消息缓冲器或者如果消息是预期的将消息传送到最终存储目的地。

图6的方法包括响应于接收到消息的部分（650），由计算节点（102a） 确定（604）在计算节点（102a）上执行的应用（270）之一是否已经指示消 息（690）是预期的。由计算节点（102a）确定在计算节点（102a）上执行的 应用（270）之一是否已经指示消息（690）是预期的可以通过针对消息是预 期的指示而检验一个或多个投递接收队列来实行。投递接收队列包括标识响 应于由在计算节点上执行的应用做出的函数调用而产生的接收请求的项。这 些接收请求是用于经由一个或多个数据通信网络从其他计算节点接收数据的 命令或请求。例如，由计算节点（102a）确定（604）在计算节点（102a）上 执行的应用（270）之一是否已经指示消息（690）是预期的可以通过针对在 计算节点上执行的应用（270）之一预期到消息（690）的指示而检查（605） 投递接收队列（282）的内容来实行。针对在计算节点上执行的应用（270） 之一预期到消息（690）的指示而检查（605）投递接收队列（282）的内容可 以通过将来自消息（690）的头部的信息与对应于投递接收队列（282）内存 储的接收请求的信息相比较来实行。

如果在计算节点（102a）上执行的应用（270）之一没有指示消息（690） 是预期的，则该方法通过由计算节点（102a）将消息（690）的部分（650） 存储（606）在计算节点（102a）内的非预期消息缓冲器（280）中而继续。 由计算节点（102a）将消息（690）的部分（650）存储（606）在计算节点（102a） 内的非预期消息缓冲器（280）中可以通过以下来实行：标识在非预期消息缓 冲器（280）内的与消息（690）的部分（650）内包含的源信息对应的位置； 以及将消息（690）的部分（650）存储在非预期消息缓冲器（280）内的标识 的位置处。

如果在计算节点（102a）上执行的应用（270）之一指示消息（690）是 预期的，则该方法通过由计算节点（102a）将消息（690）的部分（650）存 储（608）在由消息（690）指示的存储目的地（660）处而继续。由计算节点 （102a）将消息（690）的部分（650）存储（608）在由消息（690）指示的 存储目的地（660）处可以通过以下来实行：检查消息（690）的部分（650） 的内容以确定存储目的地的位置；以及将消息（690）的部分（650）存储在 所确定的存储目的地的位置处。存储目的地可以定位在并行计算机内的任意 位置处。例如，计算节点（102a）可以将消息（690）的部分（650）存储在 RAM（156）内。

响应于确定在计算节点（102a）上执行的应用（270）之一指示消息（690） 是预期的，图6的方法通过由计算节点（102a）将存储在非预期消息缓冲器 （280）中的消息（690）的任何其他部分（652）从非预期消息缓冲器（280） 复制到由消息（690）指示的存储目的地（660）而继续。因为在计算节点（102a） 上执行的应用（270）指示消息（690）是预期的之前接收的消息（690）的部 分被存储在非预期消息缓冲器（280）中，所以非预期消息缓冲器（280）可 以包括消息的多个部分。由计算节点（102a）将存储在非预期消息缓冲器（280） 中的消息（690）的任何其他部分（652）从非预期消息缓冲器（280）复制到 由消息（690）指示的存储目的地（660）可以通过以下来实行：标识存储在 非预期消息缓冲器（280）内的消息（690）的部分并将标识的部分复制到存 储目的地。

例如，可以首先并且在具体应用指示消息（690）是预期的之前接收消息 （690）的第一部分。在此例子中，计算节点（102a）将消息（690）的第一 部分存储在非预期消息缓冲器（280）中。继续此例子，其次并且在该具体应 用指示消息（690）是预期的之后，接收消息（690）的第二部分。因为在该 具体应用指示消息（690）是预期的之后接收第二部分，所以消息的第二部分 被存储在该消息中指示的存储目的地处而不是存储在非预期消息缓冲器中。 也就是说，仅在应用指示消息是预期的之前接收的消息（690）的部分被存储 在非预期消息缓冲器中，通过仅将在应用指示消息是预期的之前接收的消息 的部分被存储在非预期消息缓冲器中——而不是消息的所有部分，计算节点 （102a）可以节省非预期消息缓冲器内的空间。在一个具体实施例中，计算 节点并发地将消息（690）的部分（650）存储到存储目的地（660）中并且将 存储在非预期消息缓冲器（280）中的消息（690）的任何其他部分（652）复 制到存储目的地（660）。也就是说，计算节点可以将消息（690）的所有部分 存储在存储目的地（660）中而非首先将消息（690）的所有部分存储在非预 期消息缓冲器（280）中。

主要在用于在并行计算机的计算节点处处理非预期消息的全功能计算机 系统的上下文中描述了本发明的示例实施例。但是，具有本领域知识的读者 将认识到，本发明也可以实现为在用于与任何适当的数据处理系统一起使用 的计算机可读存储介质上布置的计算机程序产品。这样的计算机可读存储介 质可以是用于机器可读信息的任意存储介质，包括磁介质、光介质或者其他 适当的介质。这样的介质的例子包括硬盘驱动器中的磁盘或者磁碟、用于光 驱动器的紧凑盘、磁带以及本领域技术人员将想到的其他介质。本领域技术 人员将立即认识到，具有适当的编程手段的任意计算机系统将能够执行实现 为计算机程序产品的本发明的方法的步骤。本领域技术人员还将认识到，尽 管本说明书中描述的一些示例实施例面向安装在计算机硬件上并且在计算机 硬件上执行的软件，然而，实现为固件或者实现为硬件的替换实施例也在本 发明的范围内。

如本领域技术人员将认识到的，本发明的方面可以实现为系统、方法或 计算机程序产品。因此，本发明的方面可以采取完全硬件实施例、完全软件 实施例（包括固件、驻留软件、微代码等）或者组合了软件和硬件方面的实 施例的形式，它们可以在此统称为“电路”、“模块”或“系统”。此外，本发 明的方面可以采取体现在一个或多个计算机可读介质中的计算机程序产品的 形式，该计算机可读介质具有体现在其上的计算机可读的程序代码。

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

计算机可读传输介质可以包括在基带中或者作为载波的部分的传播的数 据信号，其中承载了计算机可读的程序代码。这种传播的信号可以采用多种 形式的任意形式，包括但不限于电磁信号、光信号或上述的任意合适的组合。 计算机可读传输介质可以是计算机可读存储介质以外的任何计算机可读介 质，该计算机可读介质可以发送、传播或者传输用于由指令执行系统、装置 或者器件使用或者与其结合使用的程序。

计算机可读介质上包含的程序代码可以使用任何适当的介质来传输，包 括但不限于无线、有线、光纤电缆、RF等等，或者上述的任意合适的组合。

可以以一种或多种编程语言的任意组合来编写用于执行本发明的方面的 操作的计算机程序代码，所述编程语言包括诸如Java、Smalltalk、C++等的面 向对象的程序设计语言以及诸如“C”编程语言或类似编程语言的传统过程编 程语言。程序代码可以完全地在用户的计算机上执行、部分地在用户计算机 上执行、作为独立的软件包执行、部分在用户的计算机上部分在远程计算机 上执行、或者完全在远程计算机或服务器上执行。在后一情形中，远程计算 机可以通过任意类型的网络、包括局域网(LAN)或广域网(WAN)连接到用户的 计算机，或者，可以使得（例如使用因特网服务提供商通过因特网）连接到 外部计算机。

参照根据本发明的实施例的方法、装置（系统）和计算机程序产品的流 程图和/或框图描述了本发明的方面。将理解，流程图和/或框图中的每个方框 以及流程图和/或框图中各方框的组合可以由计算机程序指令实现。这些计算 机程序指令可以提供给通用计算机、专用计算机或其它可编程数据处理装置 的处理器，从而生产出机器，以便经由计算机或其它可编程数据处理装置的 处理器执行的这些指令创建用于实现流程图和/或框图的方框中指定的功能/ 动作的部件。

也可以把这些计算机程序指令存储在可以使得计算机、其它可编程数据 处理装置或其它设备以特定方式工作的计算机可读介质中，以便存储在计算 机可读介质中的指令产生包括实现流程图和/或框图的方框中指定的功能/动 作的制造品(article of manufacture)。

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

附图中的流程图和框图例示根据本发明的各个实施例的系统、方法和计 算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框 图中的每个方框可以代表模块、程序段或代码的部分，所述模块、程序段或 代码的部分包含一个或多个用于实现指定的逻辑功能的可执行指令。也应当 注意，在有些作为替换的实现中，方框中所标注的功能可以以不同于附图中 所标注的顺序发生。例如，示出为连续的两个方框实际上可以基本并行地执 行，或者这些块有时可以按相反的顺序执行，这依赖于所涉及的功能而定。 也要注意的是，框图和/或流程图中的每个方框、以及框图和/或流程图中的方 框的组合可以由进行指定的功能或动作的专用的基于硬件的系统来实现，或 者可以由专用硬件与计算机指令的组合来实现。

根据以上描述将理解，在不偏离本发明的真正精神的情况下，可以在本 发明的各个实施例中做出修改和改变。本说明书中的描述仅仅是用于例示的 目的并且不应被解释为限制的意思。本发明的范围仅由以下权利要求的语言 限制。