并行计算机和定位并行计算机中硬件故障的方法

摘要

定位并行计算机中的硬件故障，包含在并行计算机的树形网络内定义网络计算节点的两个或更多非重叠测试层次集合，所述非重叠测试层次集合一起包含网络的所有数据通信链路，其中由树的两个或更多相邻层组成每个非重叠测试层次；在每个非重叠测试层次内定义测试单元，其中每个测试单元包含树的子树，所述子树则包含非重叠测试层次内的子树根计算节点和该子树根计算节点的所有后代计算节点；分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行上行链路测试；以及分别从上行链路测试，并且分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行下行链路测试。

说明书

技术领域

本发明涉及数据处理，或更具体地，涉及用于定位并行计算机中的硬件故障的方法、装置和产品。

背景技术

1948的EDVAC计算机系统的出现经常被称作计算机时代的开始。从那以后，计算机系统已经发展成非常复杂的设备。现在的计算机比诸如EDVAC的早期系统要复杂得多。计算机系统通常包含硬件和软件部件、应用程序、操作系统、处理器、总线、存储器、输入/输出设备等等的组合。随着半导体加工和计算机结构的进步推动计算机的性能越来越高，更复杂的计算机软件已发展成利用硬件的更高性能，从而产生了比仅仅几年前强得多的当前的计算机系统。

并行计算是已经历了进步的计算机技术的领域。并行计算是为了更快地获得结果而在多处理器上同时执行(分割以及特别适配的)相同任务的技术。并行计算基于解决问题的过程通常可被分成较小任务的事实，其中可以某种协同同时执行这些较小任务。

并行计算机执行并行算法。并行算法可被分割以在许多不同处理设备上每次执行一段，然后最终再合到一起以得到数据处理结果。一些算法易于分割成段。例如，通过将数的子集分配到每个可用处理器，然后将肯定结果列表合到一起，能够将检查从一到十万的所有数以观察哪个数是素数的任务进行分割。在本说明书中，执行并行程序的各个段的多个处理设备被称为‘计算节点’。并行计算机由计算节点以及其它处理节点组成，所述其它处理节点例如包含输入/输出(‘I/O’)节点和服务节点。

因为通过并行算法执行某些大型计算任务比通过串行(非并行)算法(由于现代处理器的工作方式)更快，所以并行算法是有价值的。用单个快速处理器构造计算机比用多个具有相同吞吐率的慢速处理器构造计算机要难得多。串行处理器的可能速度还存在某些理论极限。另一方面，每个并行算法具有串行部分，因此并行算法具有饱和点。在该点之外增加更多的处理器不产生更多的吞吐率，而只是增加开销和费用。

并行算法也被设计成优化并行计算机的节点间数据通信所需的一或多个资源。并行处理器通信有两个方式，即共享存储器或消息传送。共享存储器处理需要数据的额外锁定，并且产生附加处理器和总线周期的开销，以及串行化算法的某部分。

消息传送处理使用高速数据通信网和消息缓冲器，但是该通信增加数据通信网络上的传送开销，以及消息缓冲器的附加存储器需要和节点间数据通信的时延。并行计算机的设计使用特别设计的数据通信链路，使得通信开销较小，但决定传输量的是并行算法。

许多数据通信网络结构被用于并行计算机中的节点间的消息传送。计算节点在网络中可被组织成例如‘环(torus)’或‘网格(mesh)’。并且，计算节点在网络中可被组织成树。环形网络用围绕链路的圈来连接三维网格中的节点。每个节点通过该环形网络被连接到其6个相邻节点，并且每个节点用其网格中的x，y，z坐标寻址。在树形网络中，节点通常被连接成二进制树：每个节点具有父节点，以及两个子节点(虽然取决于硬件配置，一些节点可能只具有零子节点，或一个子节点)。在使用环形和树形网络的计算机中，通常利用分立路由电路、分立物理链路和分立消息缓冲器，彼此独立地实现两个网络。

环形网络有助于点对点几何探知诊断，而树形网络在点对点通信中通常是低效的。然而，树形网络对于某些集群操作(collectiveoperation)、所有计算节点同时参加其中的消息传送操作提供高带宽和低时延。因为数千节点可参与并行计算机上的数据处理操作，所以定位并行计算机中的硬件故障是困难的。

发明内容

公开了用于定位并行计算机中的硬件故障的方法、设备和计算机程序产品。这种并行计算机包含多个计算节点和数据通信网络。数据通信网络包含连接到计算节点以便将计算节点组织成树的数据通信链路。树以根计算节点和多层计算节点为特征。根据本发明的实施例，定位硬件故障通常包含在树内定义网络的计算节点的两个或更多非重叠测试层次集合，所述非重叠测试层次集合一起包含网络的所有数据通信链路，每个非重叠测试层次包括树的两个或更多相邻层。根据本发明的实施例，定位硬件故障通常还包含在每个非重叠测试层次内定义测试单元，每个测试单元包括树的子树，所述子树包含非重叠测试层次内的子树根计算节点和该子树根计算节点的所有后代计算节点。根据本发明的实施例，定位硬件故障通常还包含分别在每个非重叠测试层次集合上对一个非重叠测试层次集合中的所有测试单元执行上行链路测试，以及分别从上行链路测试以及分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行下行链路测试。

从以下附图所示本发明的示范实施例的更多具体描述将明白本发明的前述和其它目的、特性和优点，其中类似参考标记通常代表本发明的示范实施例的类似部分。

附图说明

图1根据本发明的实施例图解了用于定位并行计算机中的硬件故障的示例性系统。

图2根据本发明的实施例示出了用于定位并行计算机中的硬件故障的示例性计算节点的模块图。

图3A根据本发明的实施例图解了用于定位并行计算机中的硬件故障的系统的示例性点对点适配器。

图3B根据本发明的实施例图解了用于定位并行计算机中的硬件故障的系统的示例性集群操作适配器。

图4图解了为点对点操作优化的示例性数据通信网络。

图5图解了为集群操作优化的示例性数据通信网络。

图6根据本发明的实施例示出了图解定位并行计算机中的硬件故障的示例性方法的流程图。

图7A图解了组织成树的网络，其中定义了计算节点的非重叠测试层次集合。

图7B图解了相同的网络，但是是用计算节点的第二非重叠测试层次集合定义的。

具体实施方式

根据本发明的实施例，参考从图1起的附图，描述用于定位并行计算机中的硬件故障的示例性方法、设备和计算机程序产品。图1根据本发明的实施例图解了用于定位并行计算机中的硬件故障的示例性系统。图1的系统包含并行计算机(100)，数据存储设备(118)形式的计算机非易失存储器，打印机(120)形式的计算机输出设备，以及计算机终端(122)形式的计算机输入/输出设备。图1的例子中的并行计算机(100)包含多个计算节点(102)。

通过包含高速以太网(174)、联合测试行动组(‘JTAG’)网络(104)、集群操作网络(106)和点对点操作网络(108)的若干独立的数据通信网络，连接计算节点(102)以进行数据通信。集群操作网络(106)是包含连接到计算节点以便将计算节点组织成树的数据通信链路的数据通信网络。利用计算节点(102)间的数据通信链路实现每个数据通信网络。数据通信链路为并行计算机的计算节点间的并行操作提供数据通信。如下面在说明书中详细描述的，根据本发明的实施例，图1的系统通常进行操作以通过以下方式来定位并行计算机中的硬件故障：在并行计算机的树形网络内定义网络计算节点的两个或更多非重叠测试层次集合，所述非重叠测试层次集合一起包含网络的所有数据通信链路，其中由树的两个或更多相邻层组成每个非重叠测试层次；在每个非重叠测试层次内定义测试单元，其中每个测试单元包含树的子树，所述子树则包含非重叠测试层次内的子树根计算节点和该子树根计算节点的所有后代计算节点；分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行上行链路测试；以及分别从上行链路测试，并且分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行下行链路测试。

除了计算节点之外，计算机(100)包含通过数据通信网络(174)中的一个连接到计算节点(102)的输入/输出(‘I/O’)节点(110，114)。I/O节点(110，114)提供计算节点(102)和I/O设备(118，120，122)之间的I/O服务。通过局域网(‘LAN’)(130)为数据通信I/O设备(118，120，122)连接I/O节点(110，114)。计算机(100)还包含通过网络(104)之一连接到计算节点的服务节点(116)。服务节点(116)提供公用于多个计算节点的服务，从而将程序加载到计算节点，在计算节点上开始程序执行，得到计算节点上程序操作的结果，诸如此类。服务节点(116)运行服务应用程序(124)，并且通过在计算机终端(122)上运行的服务应用程序接口(126)与用户(128)通信。

在有缺陷链路周围路由通信可以是点对点操作或集群操作的一部分，并且当在周围的路由发生时，在有缺陷链路周围路由通信数据所经过的第二网络对于有效操作可能是或可能不是优化的。如果在有缺陷链路周围的路由作为针对点对点操作而优化的网络，例如环形网络中的点对点操作的一部分而发生，则在有缺陷链路周围路由数据分组所经过的第二网络可以是针对集群操作而不是点对点操作优化的网络，例如集群树形网络。如果在有缺陷链路周围的路由作为针对集群操作而优化的网络，例如树形网络中的集群操作的一部分发生，则在有缺陷链路周围路由数据分组所经过的第二网络可以是针对点对点而不是集群操作优化的网络，例如环形网络。

集群操作是一种操作，即由‘多个’或‘一组’计算节点中的所有计算节点同时，即几乎同时执行的消息传送计算机程序指令。这样的多个或一组计算节点可包含并行计算机(100)中的所有计算节点，或所有计算节点的子集。在MPI术语中，这样‘多个’或‘一组’可被定义为‘通信者(communicator)’。

‘MPI’是指‘消息传送接口’，一种现有技术并行通信库，一种用于在并行计算机上进行数据通信的计算机程序指令的模块。根据本发明的实施例，可被改进用于定位并行计算机中的硬件故障的现有技术并行通信库的例子包括MPI和‘并行虚拟机’(‘PVM’)库。PVM是由田纳西大学，美国橡树岭国立实验室和埃默里大学开发的。MPI是由MPI论坛，一个拥有来自定义和维护MPI标准的许多组织的代表的开放组所公布的。在写本文的时候，MPI是在分布式存储器并行计算机上运行并行程序的计算节点之间的通信的事实标准。该说明书为便于说明有时使用MPI术语，尽管如此使用MPI不是本发明的要求或限制。

集群操作由或多或少并行执行(取决于操作和内部算法)的许多点对点消息组成，并且涉及在指定计算节点组，即指定MPI通信者中运行的所有进程。在该组中的每个计算节点上的每个进程必须几乎同时调用或执行相同的集群操作。因为在许多分立的物理计算节点上运行的许多进程不能说是完全同时一起做任何事情，所以所要求的同时性被描述为近似的。并行通信库提供支持同步的功能。在MPI例子中，这样的同步功能是‘barrier’程序。为进行同步，组内所有计算节点上的所有进程都调用例如MPI_barrier()，然后所有进程进行等待，直到所有进程达到相同执行点。于是执行基本同步地继续。

多数集群操作是四个基本操作的变型或组合：广播、收集、分散和归约。在广播操作中，所有进程指定相同的根进程，其缓冲器内容会被发送。除了根之外的进程指定接收缓冲器。操作之后，所有缓冲器含有来自根进程的消息。

分散操作，类似于广播操作，也是一对多集群操作。所有进程指定相同的接收计数。发送参数只对根进程有意义，其缓冲器实际包含发送计数*N个指定数据类型的单元，其中N是指定计算节点组中的进程的数量。发送缓冲器将被等分，并且被分散给所有进程(包含其本身)。每个计算节点被分配了称作‘等级(rank)’的顺序标识符。操作之后，根按照升高的等级次序已将发送计数数据单元发送给每个进程。等级0接收来自发送缓冲器的第一个发送计数数据单元。等级1接收来自发送缓冲器的第二发送计数数据单元，如此类推。

收集操作是多对一集群操作，其为分散操作的描述的完全相反情况。即，收集是多对一集群操作，其中一数据类型的单元被从排定等级的计算节点收集到根节点的接收缓冲器中。

归约操作也是多对一集群操作，其包含对两个数据单元执行的算术或逻辑功能。所有进程指定相同的‘计数’和相同的算术或逻辑功能。归约之后，所有进程已经将来自计算节点发送缓冲器的计数数据单元发送到根进程。在归约操作中，来自相应发送缓冲器位置的数据单元通过算术或逻辑操作被成对组合以在根进程的接收缓冲器中产生单个对应单元。专用归约操作可以在运行时刻定义。并行通信库可支持预定的操作。例如，MPI提供以下预先定义的归约操作：

MPI_MAX  最大

MPI_MIN  最小

MPI_SUM  和

MPI_PROD 乘积

MPI_LAND 逻辑与

MPI_BAND 逐位与

MPI_LOR  逻辑或

MPI_BOR  逐位或

MPI_LXOR  逻辑异或

MPI_BXOR  逐位异或

组成图1图解的示例性系统的节点、网络和I/O设备的布局只是为了说明，而不是对本发明的限制。根据本发明的实施例的能够定位并行计算机中的硬件故障的数据处理系统可包含图1中未示出的附加节点、网络、设备和结构，如那些本领域技术人员所想到的。图1的例子中的并行计算机(100)包含16个计算节点(102)；根据本发明的实施例的能够定位硬件故障的并行计算机有时包含数以千计的计算节点。除了以太网和JTAG之外，这样的数据处理系统中的网络可支持包含例如TCP(传输控制协议)、IP(网际协议)以及如那些本领域技术人员将想到的其它协议的许多数据通信协议。除了图1中图解的那些硬件平台之外，可在各种硬件平台上实现本发明的各种实施例。

根据本发明的实施例的定位硬件故障通常在包含多个计算节点的并行计算机上实现。事实上，这样的计算机可包含数以千计这样的计算节点。每个计算节点本身则是一种由一或多个计算机处理器、其自身计算机存储器和其自身输入/输出适配器组成的计算机。因此，为进一步说明，图2根据本发明的实施例示出了用于能够定位硬件故障的并行计算机中的示例性计算节点的模块图。图2的计算节点包含至少一个计算机处理器以及随机存取存储器(‘RAM’)(156)。处理器(164)通过高速存储器总线(154)被连接到RAM(156)，并且通过总线适配器(194)和扩展总线(168)连接到计算节点的其它部件。

存储在RAM(156)中的是诊断应用程序(158)，即利用并行算法执行并行、用户层数据处理的计算机程序指令的模块。诊断应用程序(158)包含计算机程序指令，根据本发明的实施例，所述计算机程序指令与并行计算机中的其它计算节点上的其它程序一起操作，以通过以下操作来定位硬件故障：在并行计算机的树形网络内定义网络计算节点的两个或更多非重叠测试层次集合，所述非重叠测试层次集合一起包含网络的所有数据通信链路，其中由树的两个或更多相邻层组成每个非重叠测试层次；在每个非重叠测试层次内定义测试单元，其中每个测试单元包含树的子树，所述子树则包含非重叠测试层次内的子树根计算节点和该子树根计算节点的所有后代计算节点；分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行上行链路测试；以及分别从上行链路测试，并且分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行下行链路测试。

存储在RAM(156)中的还有并行通信库(160)，即执行计算节点之间的并行通信的计算机程序指令的库，其包含点对点操作以及集群操作。应用程序(158)通过调用并行通信库(160)中的软件程序来执行集群操作。利用诸如C程序设计语言的常规程序语言，并且利用常规编程方法来编写在两个独立的数据通信网络上的节点之间发送和接收数据的并行通信程序，根据本发明的实施例，可从头开发用于定位并行计算机中的硬件故障的并行通信程序的库。或者，可使用存在的现有技术库。根据本发明的实施例，可被改进用于定位并行计算机中的硬件故障的现有技术并行通信库的例子包括‘消息传送接口’(‘MPI’)库和‘并行虚拟机’(‘PVM’)库。然而对其进行开发，根据本发明的实施例改进并行通信库(160)的并行通信程序以通过以下操作来定位硬件故障：在并行计算机的树形网络内定义网络计算节点的两个或更多非重叠测试层次集合，所述非重叠测试层次集合一起包含网络的所有数据通信链路，其中由树的两个或更多相邻层组成每个非重叠测试层次；在每个非重叠测试层次内定义测试单元，其中每个测试单元包含树的子树，所述子树则包含非重叠测试层次内的子树根计算节点和该子树根计算节点的所有后代计算节点；分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行上行链路测试；以及分别从上行链路测试，并且分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行下行链路测试。

存储在RAM(156)中的还有操作系统(162)，其为用于应用程序访问计算节点的其它资源的计算机程序指令和程序的模块。因为线程有资格完成对节点的所有资源的访问，所以并行计算机的计算节点中的应用程序和并行通信库通常不用用户登录以及不用安全提交就运行执行的单线程。因此，由操作系统在并行计算机中的计算节点上执行的任务的数量和复杂度比许多线程同时运行的串行计算机上的操作系统的任务的数量和复杂度要小并且复杂度要低。此外，图2的计算节点(152)上没有视频I/O，其为降低对操作系统要求的另一个因素。因此，与通用计算机的操作系统相比，操作系统可以是相当轻型的，是原来的缩减版本，或是针对特定并行计算机上的操作具体开发的操作系统。可为计算节点中的使用而改进、简化的操作系统包括UNIX^TM、LINUX^TM、Microsoft XP^TM、AIX^TM、IBM的i5/OS^TM，以及本领域的技术人员将想到的其他操作系统。

图2的示例性计算节点(152)包括若干用于实现与并行计算机的其他节点进行数据通信的通信适配器。此类数据通信可以通过RS-232连接、通过诸如USB的外部总线、通过诸如IP网络的数据通信网络以及本领域的技术人员将想到的其他方式串行地实现。通信适配器实现硬件级数据通信，计算机通过所述通信适配器直接或通过网络将数据通信发送给另一个计算机。根据本发明的实施例用于定位硬件故障的系统中可使用的通信适配器的例子包括用于有线通信的调制解调器、用于有线网通信的以太网(IEEE 802.3)适配器，以及用于无线网络通信的802.11b适配器。

图2的例子中的数据通信适配器包括千兆位以太网适配器(172)，其将用于数据通信的示例性计算节点(152)连接到千兆位以太网(174)。千兆位以太网是以IEEE 802.3标准定义的网络传输标准，其提供每秒千兆位的数据速率(一千兆位)。千兆位以太网是通过多模式光缆、单模光缆或非屏蔽双绞线工作的以太网的变型。

图2的例子中的数据通信适配器包括将用于数据通信的示例性计算节点(152)连接到JTAG主电路的JTAG从电路(176)。JTAG是用于IEEE 1149.1标准的常见名，该标准被称作标准测试访问端口以及边界扫描结构，其被用来利用边界扫描来测试印刷电路板的测试访问端口。JTAG被如此广泛地采用，使得此时边界扫描或多或少与JTAG同义。JTAG不仅被用于印刷电路板，而且还用于执行集成电路的边界扫描，并且还被用作调试嵌入式系统的机制，其提供进入系统的方便的“后门”。图2的示例性计算节点可以是所有的以下三种：其通常包括安装在印刷电路板上的一个或多个集成电路，并且可被作为具有其自己的处理器、其自己的存储器及其自己的I/O能力的嵌入式系统实现。根据本发明的实施例，通过JTAG从设备(176)的JTAG边界扫描可有效地配置用于定位硬件故障的计算节点(152)中的处理器寄存器和存储器。

图2的例子中的数据通信适配器包括将用于数据通信的示例性计算节点(152)连接到网络(108)的点对点适配器(180)，所述网络对于点对点消息传送操作是最优的，例如配置成三维环或网格的网络。点对点适配器(180)沿三个通信轴x，y和z上的6个方向，通过6个双向链路提供数据通信：+x(181)、-x(182)、+y(183)、-y(184)、+z(185)和-z(186)。

图2的例子中的数据通信适配器包括将用于数据通信的示例性计算节点(152)连接到网络(106)的集群操作适配器(188)，所述网络对于集群消息传送操作是最优的，例如配置成二进制树的网络。集群操作适配器(188)通过三个双向链路提供数据通信：两个到子节点(190)以及一个到父节点(192)。

示例性计算节点(152)包括两个算术逻辑单元(‘ALU”)。ALU(166)是处理器(164)的部件，而独立的ALU(170)专用于集群操作适配器的独占使用，用来执行归约操作的算术和逻辑功能。并行通信库(160)中的归约程序的计算机程序指令可将算术或逻辑功能的指令锁存到指令寄存器(169)中。例如，当归约操作的算术或逻辑功能为‘求和’或‘逻辑或’时，通过利用处理器(164)中的ALU(166)或通过利用专用ALU(170)(通常更快速地)，集群操作适配器可执行算术或逻辑操作。

为进一步说明，图3A根据本发明的实施例图解了用于定位硬件故障的系统的示例性点对点适配器(180)。点对点适配器(180)被设计成用于针对点对点操作而优化的数据通信网络，即将计算节点组织成三维环或网格的网络。图3A的例子中的点对点适配器(180)沿着x-轴通过四个单向数据通信链路提供数据通信，沿着-x方向(182)到达和来自下一节点，沿着+x方向(181)到达和来自下一节点。点对点适配器(180)还沿着y-轴通过四个单向数据通信链路提供数据通信，沿着-y方向(184)到达和来自下一节点，沿着+y方向(183)到达和来自下一节点。点对点适配器(180)还沿着z轴通过四个单向数据通信链路提供数据通信，沿着-z方向(186)到达和来自下一节点，沿着+z方向(185)到达和来自下一节点。

为进一步说明，图3B根据本发明的实施例图解了用于定位硬件故障的系统的示例性集群操作适配器(188)。集群操作适配器(188)被设计成用于针对集群操作而优化的网络，即将并行计算机的计算节点组织二进制树的网络。图3B的例子中的集群操作适配器(188)通过四个单向数据通信链路(190)提供到达和来自两个子节点的数据通信。集群操作适配器(188)还通过两个单向数据通信链路(192)提供到达和来自父节点的数据通信。

为进一步说明，图4图解了为点对点操作(106)优化的示例性数据通信网络。在图4的例子中，点代表并行计算机的计算节点(102)，而点之间的虚线代表计算节点之间的数据通信链路。利用类似于图3A中的例子所图解的点对点数据通信适配器，利用三个轴x，y和z上的数据通信链路，并且沿着6个方向+x(181)、-x(182)、+y(183)、-y(184)、+z(185)和-z(186)来回实现数据通信链路。由针对点对点操作优化的数据通信网络将链路和计算节点组织成环绕以形成环(107)的3维网格(105)。环中的每个计算节点在环中具有由一组x，y，z坐标唯一指定的位置。为清楚说明，图4的数据通信网络仅用27个计算节点来图解，但是读者将认识到，用于根据本发明的实施例定位硬件故障的针对点对点操作优化的数据通信网络可仅包含少数计算节点，或可包含数以千计的计算节点。

为进一步说明，图5图解了为集群操作(108)优化的示例性数据通信网络。图5的示例性数据通信网络包括连接到计算节点以便将计算节点组织成树的计算节点数据通信链路。在图5的例子中，点代表并行计算机的计算节点(102)，而点之间的虚线代表计算节点之间的数据通信链路。利用类似于图3B中的例子所图解的集群操作数据通信适配器，实现数据通信链路，例外的是，其中每个节点通常提供到达和来自两个子节点的数据通信和到达和来自父节点的数据通信。二进制树中的节点可以通过根节点(202)、分支节点(204)和叶节点(206)来表征。根节点(202)具有两个子节点，但是没有父节点。叶节点(206)每个具有父节点，但是叶节点没有子节点。分支节点(204)每个既具有父节点又具有两个子节点。从而，由该针对集群操作优化的数据通信网络将链路和计算节点组织成二进制树(108)。为清楚说明，图5的数据通信网络仅用31个计算节点来图解，但是读者将认识到，用于根据本发明的实施例定位硬件故障的针对集群操作优化的数据通信网络可仅包含少数计算节点或可包含数以千计的计算节点。

图5的例子中，树中的每个节点被分配称为‘等级’(250)的单元标识符。节点的等级唯一地标识树形网络中用于点对点和集群操作的树形网络中的节点的位置。该例子中的等级被分配为从分配给根节点(202)的0，分配给树的第二层中的第一个节点的1，分配给树的第二层中的第二节点的2，分配给树的第三层中的第一个节点的3，分配给树的第三层中的第二节点的4起的整数，如此类推。为便于说明，这里仅示出树的前三个层的等级，但是树形网络中的所有计算节点都被分配了唯一等级。

图5的例子中，树形网络(108)被表征为根计算节点(202)、以及层0、层1等等的多层计算节点。计算节点的层由层的计算节点与根计算节点(202)之间的数据通信链路的数量来定义。层0中的计算节点具有层0中的计算节点与根节点(202)之间的零个数据通信链路-其为层0中仅有的计算节点。层1中的每个计算节点具有其与根节点(202)之间的一个数据通信链路。层2中的每个计算节点具有其与根节点(202)之间的两个数据通信链路。如此类推。

图5的网络树的层被以从包含根节点的层(作为层0)开始的整数序列进行编号，并且继之以层1、层2，如此类推。以整数序列来对层进行编号的事实意味着图5的例子中的计算节点的层包括偶数层计算节点和奇数层计算节点。偶数层包括层0、层2，如此类推。奇数层包括层1、层3，如此类推。

为进一步说明，图6根据本发明的实施例示出了图解定位并行计算机中的硬件故障的示例性方法的流程图。图6的方法在包括多个计算节点和数据通信网络(108)的并行计算机(100)中实现，所述网络包含连接到计算节点以便将计算节点组织成树的数据通信链路。图6中的点代表计算节点，而点之间的虚线代表计算节点之间的数据通信链路。图6中的每个计算节点标有其等级，即从0起并继续至6的整数值。通过根计算节点(具有0等级的节点)以及多层计算节点(层0、层1和层2)来表征。为便于说明，这里仅示出树的前三个层，但是树形网络中的所有计算节点都被分配了唯一等级。为清楚说明，图6的数据通信网络(108)仅以6个计算节点和三个层进行说明，但是读者将认识到，根据本发明的实施例，用于能够定位硬件故障的并行计算机、组织成树的数据通信网络可包含任意数量的计算节点和任意数量的层，仅有少数或数千。

读者将注意到，利用二进制基数(binary radix)，即所谓的二进制树、根和具有两个子节点的每个分支节点，组织图6中图解的树形网络(108)。然而，这里使用二进制基数仅仅是为便于说明，而不作为本发明的限制。在根据本发明的实施例将计算节点组织成树的并行计算机的数据通信网络中，如本领域的技术人员可想到的，此类网络中的根节点和分支节点可以具有任意数量的子节点。如该说明书所使用的术语‘子节点’是指父节点的直接子节点-不是指孙节点、曾孙节点等。如该说明书所使用的术语‘后代’是指父节点的所有子节点、孙节点、曾孙节点等。

图6的方法包括在树内定义(302)网络的计算节点的两个或更多非重叠测试层次集合，所述非重叠测试层次集合一起包含网络的所有数据通信链路，其中每个非重叠测试层次包括树的两个或更多相邻层。图7A图解了组织成树的网络(108)，其中定义计算节点的一个非重叠测试层次集合(702，704)，其中每个非重叠测试层次(702，704)包括树的两个或更多相邻层。图7A中，点代表计算节点，而虚线代表连接到计算节点以便将计算节点组织成树的数据通信链路。测试层次(702)包括树的两个相邻层，层0和层1。测试层次(704)包括树的两个相邻层，层2和层3。测试层次(702，704)不相重叠，即两者都不包括任何还在另一个测试层次中的数据通信链路。测试层次(702，704)一起代表计算节点的一个非重叠测试层次集合(706)。

图7B图解了相同的网络(108)，这次利用计算节点的第二非重叠测试层次集合(718，720)来定义，其中每个非重叠测试层次(718，720)包括树的两个或更多相邻层。测试层次(718)包括树的两个相邻层，层1和层2。测试层次(720)包括树的两个相邻层，层3和层4。测试层次(718，720)不相重叠，即两者都不包括任何还在另一个测试层次中的数据通信链路。测试层次(718，720)一起代表计算节点的一个非重叠测试层次集合(722)。测试层次(702，704，718，720)代表网络(108)的计算节点的两个非重叠测试层次集合(706，722)，其一起包含网络的所有数据通信链路。

再次参考图6：图6的方法包括在每个非重叠测试层次内定义(304)测试单元，其中每个测试单元包含树的子树，所述子树包含非重叠测试层次内的子树根计算节点和该子树根计算节点的所有后代计算节点。图7A和7B图解了非重叠测试层次内所定义的测试单元。非重叠测试层次(702)具有在其内定义的测试单元(708)。非重叠测试层次(704)具有在其内定义的测试单元(710，712，714，716)。非重叠测试层次(718)具有在其内定义的测试单元(724，726)。以及非重叠测试层次(720)具有在其内定义的测试单元(728，730，732，734，736，738，740，742)。

读者的注意力被引到利用用于说明的附图标记被特别标记的测试单元(716)上。类似图7A和7B中的所有测试单元，测试单元(716)由代表树形网络(108)的子树的三个计算节点组成。测试单元(716)包含子树根计算节点(705)和两个分支节点(707)。分支节点(707)是子树根计算节点(705)的直接子节点。分支节点(707)也是非重叠测试层次内的子树根计算节点(705)的全部后代计算节点。类似地，测试单元(710，712，714)每个包含树(108)的子树，该子树则包含非重叠测试层次(704)内的子树根计算节点和子树根计算节点的所有后代计算节点。测试单元(708)包含树(108)的子树，该子树则包含非重叠测试层次(702)内的子树根计算节点和子树根计算节点的所有后代计算节点。测试单元(724，726)每个包含树(108)的子树，该子树则包含非重叠测试层次(718)内的子树根计算节点和子树根计算节点的所有后代计算节点。并且测试单元(728，730，732，734，736，738，740，742)每个包含树(108)的子树，该子树则包含非重叠测试层次(720)内的子树根计算节点和子树根计算节点的所有后代计算节点。

再次参考图6：图6的方法包含分别在每个非重叠测试层次集合上对一个非重叠测试层次集合中的所有测试单元执行上行链路测试。即，以两个阶段执行该例子中的上行链路测试：再次参考7A和7B，首先，对非重叠测试层次集合(706)中的所有测试单元执行上行链路测试。其次，对非重叠测试层次集合(722)中的所有测试单元执行独立的上行链路测试。

图7A的树形网络呈现了一个非重叠测试层次集合(706)的例子，其中每个非重叠测试层次(702，704)包含具有偶数层计算节点中的子树根计算节点的测试单元。测试层次(702)包含具有层0中的子树根计算节点的测试单元，并且测试层次(704)包含具有层2中的子树根计算节点的测试单元。因此，通过对一个非重叠测试层次集合中的所有测试单元执行上行链路测试，来实现对该例子中的一个非重叠测试层次集合中的所有测试单元的上行链路测试，其中每个非重叠测试层次包含具有偶数层计算节点中的子树根计算节点的测试单元。

图7B的树形网络呈现了一个非重叠测试层次集合(722)的例子，其中每个非重叠测试层次(718，720)包含具有奇数层计算节点中的子树根计算节点的测试单元。测试层次(718)包含具有层1中的子树根计算节点的测试单元，并且测试层次(720)包含具有层3中的子树根计算节点的测试单元。因此，通过对一个非重叠测试层次集合中的所有测试单元执行上行链路测试来实现对该例子中的一个非重叠测试层次集合中的所有测试单元的上行链路测试，其中每个非重叠测试层次包含具有奇数层计算节点中的子树根计算节点的测试单元。

在图6的方法中，对测试单元执行(306)上行链路测试可通过测试沿着从子树根计算节点的后代计算节点到子树根计算节点的方向传送通信数据的数据通信链路来实现。在该讨论的情况中，‘向上’是指从后代分支或叶节点到父节点或根节点的传送方向。类似地，‘向下’是指从父节点或根节点到父节点或根的后代的传送方向。图3B的例子中，上行链路(752)是能够向上，即从后代分支或叶节点向父节点或根节点传送通信数据的数据通信链路。如同图7A上的参考(705)所示的计算节点，如果计算节点(152)被当作子树根的后代计算节点，并且其父节点(192)被当作子树根计算节点，则上行链路(750)是能够沿着从子树根计算节点的后代计算节点到子树根计算节点的方向传送通信数据的数据通信链路。

在图6的方法中，执行(306)上行链路测试可包含测试一个非重叠测试层次集合中的所有测试单元中的每个子树根计算节点的ALU。树(108)的每个计算节点，并且因此每个子树根计算节点可包含专用于执行归约操作的算术和逻辑功能的独立的ALU-例如参考图2中的(170)如上所图解和所描述的独立专用的ALU。测试每个子树根计算节点的ALU可通过存储MPI收集指令的正确结果到每个子树根计算节点的存储器中来实现，MPI收集指令利用ALU来执行算术或逻辑功能，从而执行收集和将收集的结果与正确结果相比较。

图6的方法还包含分别从上行链路测试以及分别在每个非重叠测试层次集合上，对一个非重叠测试层次集合中的所有测试单元执行(308)下行链路测试。即，以两个阶段执行该例子中的下行链路测试：再次参考7A和7B，首先，对非重叠测试层次集合(706)中的所有测试单元执行下行链路测试。其次，对非重叠测试层次集合(722)中的所有测试单元执行独立的下行链路测试。分别执行上行链路测试和下行链路测试减少了下行链路测试期间死锁的风险，例如，当相关的上行链路有缺陷时。

图7A的树形网络呈现了一个非重叠测试层次集合(706)的例子，其中每个非重叠测试层次(702，704)包含具有偶数层计算节点中的子树根计算节点的测试单元。测试层次(702)包含具有层0中的子树根计算节点的测试单元，以及测试层次(704)包含具有层2中的子树根计算节点的测试单元。因此，通过对一个非重叠测试层次集合中的所有测试单元执行下行链路测试来实现对该例子中的一个非重叠测试层次集合中的所有测试单元的下行链路测试，其中每个非重叠测试层次包含具有偶数层计算节点中的子树根计算节点的测试单元。

图7B的树形网络呈现了一个非重叠测试层次集合(722)的例子，其中每个非重叠测试层次(718，720)包含具有奇数层计算节点中的子树根计算节点的测试单元。测试层次(718)包含具有层1中的子树根计算节点的测试单元，并且测试层次(720)包含具有层3中的子树根计算节点的测试单元。因此，通过对一个非重叠测试层次集合中的所有测试单元执行下行链路测试来实现对该例子中的一个非重叠测试层次集合中的所有测试单元的下行链路测试，其中每个非重叠测试层次包含具有奇数层计算节点中的子树根计算节点的测试单元。

在图6的方法中，对测试单元执行(308)下行链路测试可通过测试沿着从子树根计算节点到子树根计算节点的后代计算节点的方向传送通信数据的数据通信链路来实现。在图3B的例子中，下行链路(750)是能够向下，即从父节点或根节点向父节点或根的后代传送通信数据的数据通信链路。如同图7A上的参考(705)所示的计算节点，如果计算节点(152)被当作子树根的后代计算节点，并且其父节点被当作子树根计算节点，则下行链路(750)是能够沿着从子树根计算节点到子树根计算节点的后代计算节点的方向传送通信数据的数据通信链路。树形网络(108)中的所有数据通信链路可以是由类似参考图3B所图解和描述的那些链路(752，750)的上行链路和下行链路组成的双向链路。

在图6的方法中，执行(306)上行链路测试可包含测试一个非重叠测试层次集合中的所有测试单元中的每个子树根计算节点的后代计算节点的ALU。树(108)的每个计算节点，并且因此每个子树根计算节点的每个后代计算节点可包含专用于执行归约操作的算术和逻辑功能的独立的ALU-例如参考图2中的(170)如上所图解和描述的独立专用的ALU。测试后代计算节点的ALU可通过存储参数数值和并行计算广播指令的正确结果到每个后代计算节点的存储器中来实现，并行计算广播指令利用ALU对参数数值和广播值执行算术或逻辑功能，从而执行广播和将广播的结果与每个后代计算节点中的正确结果相比较。常规的MPI广播不执行算术或逻辑功能。因此，该例子中的广播功能被改进以用于此处所示的根据本发明的实施例的定位并行计算机中的硬件故障：

broadcast(void^*buf，int count，Datatype dtype，int root，Op op，Comm comm)；

该广播通信中，所有计算节点将子树根计算节点指定为功能‘root’，利用先前存储的参数数值，将通过ALU发送并且操作其缓冲器内容。后代计算节点在缓冲器指针‘buf’中指定其接收缓冲器。操作之后，所有后代计算节点包含由‘op’指定的操作的结果。如本领域的技术人员可想到的，操作可以是任何有用的算术或逻辑操作，例如求和、乘积、逻辑与、逻辑或等等。

当诊断运行期间检测到缺陷时，由于在具体测试单元的范围内，对测试单元执行上行链路和下行链路测试具有立即定位硬件故障的好处。已知硬件故障在具体测试单元中是并行计算中的极大的好处，所述并行计算中具体计算机可包含数以千计计算节点和数以千计数据通信链路。对非重叠测试层次集合执行上行链路和下行链路测试提供了好处：如果一个测试层次中的链路是有缺陷的，则有缺陷链路不能妨碍其它测试层次中的测试操作。

因为下行链路测试是对并行计算机中的计算节点的一个非重叠测试层次集合中的测试单元执行的，所以对一个非重叠测试层次集合中的所有测试单元可同时执行下行链路测试。对一个非重叠测试层次集合中的所有测试单元同时执行下行链路测试提供了好处：每次测试需要恒定的时间量。

主要在用于定位并行计算机中的硬件故障的全功能计算机系统的情况中描述了本发明的示范实施例。然而，本领域技术人员将认识到，本发明也可被实现在用于任何适当数据处理系统的信号承载介质上所布置的计算机程序产品中。此类信号承载介质可以是传输介质或机器可读信息的可记录介质，包括磁介质、光学介质或其它适当介质。可记录介质的例子包括硬盘驱动器中的磁盘或软盘、光学驱动器的光盘、磁带以及本领域的技术人员将想到的其它可记录介质。传输介质的例子包括用于音频通信的电话网络和数字数据通信网络，例如Ethernets^TM，以及利用网际协议和World Wide Web通信的网络。所属技术领域的专业人员会立即认识到，具有适合程序的任何计算机系统意指如程序产品中所实现的，将能够执行本发明的方法的步骤。所属技术领域的专业人员将立即认识到，尽管该说明书中所描述的一些示范实施例是以在计算机硬件上安装并执行的软件为目标的，然而作为固件或如硬件实现的可选实施例在本发明的范畴内也可行。

从上述描述中将理解，在不偏离其真正宗旨的情况下，在本发明的各种实施例中可作出修改和改变。该说明书中的描述仅为了说明的目的，而不被视为限制的意义。本发明的范围仅受限于以下权利要求书的语言。