环形和树形网络中的算术函数

摘要

执行算术函数的方法和系统。根据本发明的第一方面，提供了方法和装置，该方法和装置和类网络路由的软件算法和硬件实现共同工作，极大地减少了环形网络上全局算术运算所需要的时间。因此，它使得在大型并行机器上运行的应用程序更具有可量测性。在改进全局运算的效率和精确性方面，该发明包含三个步骤：1)需要时，确保所有节点以同样的次序进行全局运算，从而获得唯一的答案，不受四舍五入误差的影响。2)使用环形拓扑，以使得跳点数最小，使用网络的双向能力，以将数据传送操作中的时间步数降低到绝对最小值。3)使用类函数路由，以减少数据传送中的延迟。使用本发明的方法，每个单个单元只被注入网络一次，它将被存储并发送，而不需要加任何软件开销。根据本发明的第二方面，提供方法和系统，在支持全局混合运算的网络上有效执行全局算术运算。通过使用这些方法，极大地减少了进行这种全局运算的延迟(图4，节点1，节点2，节点3)。

说明书

对相关申请的交叉引用

本发明请求于2001年2月24日提交的题为“MASSIVELY PARALLELSUPERCOMPUTER”的共同拥有、共同未决的美国临时专利申请No.60/271,124的利益，通过引用的方式将该申请的全部内容和公开直接并入到这里，就好像是在这里完整给出的一样。本专利申请还涉及下面与之同日提交的共同拥有、共同未决的美国专利申请，通过引用的方式将这些申请的每一个的全部内容和公开直接并入到这里，就好像是在这里完整给出的一样：美国专利申请No.(Y0R920020027US1，YOR920020044US1(15270))，“Class NetworkingRouting”；美国专利申请No.(YOR920020028US1(152771)，“A GlobalTree Network for Computing Structures”；美国专利申请No.(YOR920020029US1(15272))，“Global Interrupt and BarrierNetworks”；美国专利申请No.(YOR920020030US1(15273))，“Optimized Scalable Network Switch”；美国专利申请No.(YOR920020031US1，YOR920020032US1(15258))，“ArithmeticFunctions in Torus and Tree Networks”；美国专利申请No.(YOR920020033US1，YOR920020034US1(15259))，“Data CaptureTechnique for High Speed Signaling”；美国专利申请No.(YOR920020035US1(15260))，“Managing Coherence Via Put/GetWindows”；美国专利申请No.(YOR920020036US1，YOR920020037US1(15261))，“Low LatencyMemory Access And Synchronization”；美国专利申请No.(YOR920020038US1(15276))，“Twin-Tailed Fail-Over forFileservers Maintaining Full Performance in the Presence ofFailure”；美国专利申请No.(YOR920020039US1(15277))，“FaultIsolation Through No-Overhead Link Level Checksums”；美国专利申请No.(YOR920020040US1(15278))，“Ethernet AddressingVia Physical Location for Massively Parallel Systems”；美国专利申请No.(YOR920020041US1(15274))，“Fault Toleranceina Supercomputer Through Dynamic Repartitioning”；美国专利申请No.(YOR920020042US1(15279))，“checkpointingFilesystem”；美国专利申请No.(YOR920020043US1(15262))，“Efficient Implementation of Multidimensional Fast FourierTransform on a Distributed-Memory Parallel Multi-NodeComputer”；美国专利申请No.(YOR9-20010211US2(15275))，“ANovel Massively Parallel Supercomputer”；以及美国专利申请No.(YOR920020045US1(15263))，“Smart Fan Modules and System”。

背景技术

题为“A Novel Massively Parallel Supercomputer”的临时专利申请中，描述了一种包含许多计算节点和较少量输入/输出节点的计算机。这些节点通过几个网络连接。特别地，这些节点通过环形网络和双重功能树形网络互相连接。可用多种方式使用环形网络，以提高该计算机的有效性。

详细地说，在拥有足够数量节点的机器上，并且有一个拥有M维环形连通性的网络，进行全局操作的一般方法是借助于移位和运算。例如，为了对所有节点进行全局求和，在每个计算机节点完成自身的本地求和后，第一，每个节点沿着一个方向将本地和传送到下一个节点，并将从上一节点接收到的数加到它自己的和上。第二，将从上一节点接收到的数送到下一个节点，并且再将收到的数加到它自己的和上。重复第二步骤(N-1)次(其中N是沿着这一方向节点的数目)，随后一次一个方向在所有方向上重复整个过程，在所有节点上产生期望的结果。可是，对于浮点数来说，因为每个节点上操作的浮点求和的次序是不同的，因此每个节点的结果由于四舍五入效果而略有不同。假如需要进行全局判断，而该判断又取决于全局求和数值的话，就会出现问题。在许多情况下，通过选用一个特殊节点，该节点首先从其它节点收集数据，进行整体计算并将该和向所有节点广播，从而避免了这一问题。但是，当节点数足够大时，该方法比移位和运算方法速度慢。另外，如上面指出的，在临时专利申请60/271,124中所公开的计算机中，该节点也可通过双重功能树形网络连接，该网络支持整数混合运算，如整数求和和整数求最大值(max)和最小值(min)。全局混合网络的存在引发了在该网络中有效实施全局算术运算的可能性。例如，将来自每个计算节点的浮点数加起来，并将和向所有参与节点广播。在普通并行超级计算机中，这些运算通常是在承载正常信息传送流量的网络上进行的。通常存在与该种全局运算相关的高延迟。

发明概述

本发明的一个目的是在分布式并行计算机上改进用于全局运算的全局数值的计算方法。

本发明的另一个目的是在拥有许多节点的分布式并行M-环结构上，使用移位和运算方法计算一个用于全局运算的唯一全局数值。

本发明的另一个目的是提供方法和装置，和类网络路由的软件算法和硬件实施一起作用，以显著减少环形结构上全局算法运算所需要的时间。

本发明的另一个目的是在支持全局混合运算的网络上，有效实施全局算法运算。

本发明的另一个目的是实施全局算法运算，以生成二进制复验性的结果。

本发明的另一个目的是提供一个用于处理全局求和运算的改进的方法。

本发明的另一个目的是提供一个用于处理全局整体合并运算的改进的方法。

用以下描述的方法和系统执行算术功能，可以达到这些目的和其它目的。根据该发明的第一方面，提供了一种方法和设备，和类网络路由的软件算法和硬件实施一起作用，用以显著减少环形结构上全局算术运算所需要的时间。这导致了在大型并行机器上运行的应用程序的更大的可量测性。本发明包含用于改进全局运算的效率，精确性和精确复验性性的三个步骤：

1.需要时，确保所有节点以同样的次序对数据进行全局运算，从而获得唯一的答案，而不受四舍五入误差的影响。

2.使用环形拓扑，使得跳点数最小，使用网络的双向能力，将数据传送操作中的时间步数降低到绝对最小值。

3.使用类函数路由(专利申请号-----(代理卷号15270))，以降低数据传送中的延迟。使用本发明的方法，每个单个单元只被注入网络一次，它将被存储并发送，而不需要加任何软件开销。

根据本发明的第二方面，提供了方法和系统，用以在支持全局混合运算的网络上，有效实施全局算术运算。通过使用该方法，极大地降低了进行该全局运算的延迟。特别地，使用支持整数求最大值MAX，求和SUM，和位运算AND，OR，和XOR的混合树型网络，我们可以在该网络上实现MPI(信息传送接口标准)的事实上所有的预定义全局简化运算：MPI_SUM，MPI_MAX，MPI_MIN，MPI_LAND，MPI_BAND，MPI_LOR，MPI_BOR，MPI_LXOR，MPI_BXOR，MPI_MAXLOC，AND MPI_MINLOC和MPI_ALLGATHER。这种实现简单有效，证明了混合树形网络给大规模并行超级计算机带来的巨大的灵活性和有效性。

通过考虑以下参考附图给出的详细描述，本发明的其它好处和优点将变得显而易见，该附图详细说明并示出了本发明的优选实施例。

附图简述

图1示意性地表示了连接计算机各节点的环形网络。没有示出有包装的网络连接。

图2示意性地表示了连接计算机各节点的树形网络。

图3说明了在单向环形网络中实现全局求和的方法。

图4是一个表示几个步骤的表格，该步骤可以用来提高在环形结构中全局算数运算的有效性。

图5说明了在双重功能树形网络中全局求和的运算。

图6说明了在双重功能树形网络中全局整体合并运算。

图7说明了3×4环形网络。

图8说明了用于进行最终广播操作的树形网络。

优选实施例的详细说明

本发明涉及在计算机上实现算术功能，并涉及在临时专利申请No.60/271,124中公开的一种适合的计算机。该计算机包含许多计算节点和较少量输入/输出节点；该计算机的各个节点通过图1中以10示意性表示的环形网络和图2中以20示意性表示的双重功能树形网络互相连接。

更具体地说，本发明的一个方面提供方法和设备，和类网络路由的软件算法和硬件实施一起作用，用以显著减少环形结构上全局算法运算所需要的时间。因此，这导致了在大型并行机器上运行的应用程序的更大的可量测性。如图3所说明的，本发明包含用于改进全局运算的效率和精确性的三个步骤：

1.需要时，确保所有节点以同样的次序进行全局运算，从而获得唯一的答案，不受四舍五入误差的影响。

2.使用环形拓扑结构，以使得跳点数最小，使用网络的双向能力，以将数据传送操作中的时间步数降低到绝对最小值。

3.使用类函数路由，以减少数据传送中的延迟。使用本发明的优选方法，每个单个单元只被注入网络一次，它将被存储并发送，而不需要加任何软件开销。

下面详细讨论每个步骤：

1.确保所有节点以同样的次序进行全局运算(如MPI_SUM)：

当进行本地部分求和的单向移位和加法，而不是当数字进来时将它们相加时，每个节点将保持从各个方向接收的N-1个数。在接收到数字后对这些数字进行全局运算，因此运算是以固定的次序进行的，从而导致在所有节点上唯一的结果。

例如，如图4中所说明的，假如每个节点在收到数字时就将其相加，那么在节点0计算的和为S0+S3+S2+S1，在节点1为S1+S0+S3+S2，在节点2为S2+S1+S0+S3，在节点3为S3+S2+S1+S0。在这些和中会有四舍五入差。可是，如果每个节点接收到的数都保存着，然后所有的节点以相同的次序求和以获得S0+S1+S2+S3，所以不会存在四舍五入差。

在所有其它方向重复该过程。最后，所有节点将获得同样的数字，不需要最后的广播。

2.在M-环形结构中，将数据传送步骤数减到最小：

在两个相邻节点之间的网络连接是双向的任何机器中，我们可以在每个步骤中双向传送数据。这意味着每个数据单元必须在网络上传播的距离减小了1/2。这使得在环形网络中进行全局算术运算的时间也减小了差不多1/2。

3.使用类函数路由减少延迟：

通过在网络硬件中加入存储和发送类网络路由运算，可以取得额外的性能收益，从而去除多次提取和加入同样的数据单元到该网络的软件开销。当在能够进行类路由的网络上实现全局算术运算时，图4中说明的步骤1到3将简化为单个网络步骤，即每个节点只需要加入一个数字一次，每个其它节点在保存一个拷贝自己用的同时，还将自动发送该数字到需要该数字的所有其它节点。这极大地减少了全局运算的延迟。不用在环形网络的每个跳点加软件开销，而只要在该机器的每个方向加一个开销。例如，对于临时专利申请号60/271,124中公开的计算机系统，我们估计当CPU在单用户模式下运行时，至少可以有5倍的提高，而在多用户模式下有超过10倍的提高。

使用以上讨论的三个改进步骤，在分布式并行结构的全局算术运算方面，我们至少可以取得10倍的提高，并很大地提高大型并行机器上应用程序的可量测性。

另外，如上所述，在上述临时申请中公开的计算机系统中，节点也是通过树形网络连接的，该树形网络支持数据混合运算，如整数求和，整数求最大值和最小值，面向位的AND，OR和XOR。另外，该树形网络将自动向所有参与的节点广播最终混合运算结果。假如计算机网络支持全局混合运算，那么该网络可以有效支持许多全局通讯模式。到现在为止对于混合网络硬件最简单的要求是支持一定精度的无符号整数加法和无符号整数求最大值。例如，在上述临时专利申请中公开的超级计算机将支持至少32位，64位和128位无符号整数和或最大值，加上一个高达2048位数据包大小的很长精度的和或最大值。在实施高性能全局算术函数时，该网络硬件中的混合函数提供了很大的灵活性。下面描述了该实施的几个案例。

1.带符号整数求和

图5示出了全局求和运算。每个参与节点拥有一个同样大小的数组，这些数组有相同数量数组元素。全局求和运算的结果是每个节点都将拥有来自所有节点的相应数组元素的和。这涉及MPI(信息传送接口)标准中的MPI_SUM函数。

相比本地数来说，在网络中需要使用更高精度来获得最终结果的精度。用N表示参与求和的节点数，M表示用来求和的整数数字中的最大绝对值，2＾P表示一个比M大的大正整数。为了在支持无符号运算的网络中实施带符号整数求和，我们只需

(1)将所有需要相加的数加上大正整数2＾P，使得它们现在都变成非负的。

(2)在网络中进行无符号整数求和。

(3)在结果中减去(N*2＾P)。

选择P使得2＾P＞M，并且(N*2＾(P+1))不会在混合网络中溢出。

2.全局带符号整数求最大值和最小值

除了最终结果不是相应元素之和，而是最大值和最小值外，该运算和上述全局求和运算非常类似。它们涉及带有整数输入的MPI标准中的MPI_MAX和MPI_MIN函数。全局求最大值的实施和上述全局求和的实施非常类似。

(1)将所有数字都加上大正整数2＾P，使它们都变成非负的。

(2)在网络中进行无符号全局求最大值。

(3)从结果中减去2＾P。

要进行全局求最小值，只要对所有数求反，然后进行全局求最大值。

3.浮点数全局求和：

除了现在输入是浮点数外，浮点数全局求和运算和前面讨论的整数求和非常类似。为简洁起见，我们将示范对来自各节点的一个数进行求和。要对数列求和，只要重复这些步骤。

基本思想是在混合网络中进行两个来回过程。

(1)使用全局求最大值中列出的步骤，寻找所有数的指数的整数最大值Emax。

(2)每个节点将使本地数标准化，并将它转换成整数。使得节点“i”上的本地数变成X_i，其指数为E_i。使用全局求和描述中定义的符号，该转换对应计算

A_i＝2＾P+2＾[P-(Emax-E)-1]*X_i            [公式1]

其中A_i是无符号整数。然后在使用混合硬件的网络中进行全局无符号整数求和。一旦最终和A到达各个节点，通过以下计算可以获得真正的和S：

S＝(A-N*2＾P)/2＾(P-1)

再次选择P使得N*2＾(P+1)不会在混合网络中溢出。

需要指出的是上面公式1中进行的步骤获得尽可能高的精度，是通过使用微处理器的浮点单元来将负数转化成正数，并使用它的整数单元来进行适当的移位获得的。

该浮点求和运算的一个重要特征在于，因为实际求和是通过整数求和进行的，因此和求和进行的次序无关。在全局求和后，每个参与节点将得到完全相同的数。不需要另外的来自特殊节点的广播，而当经由一般消息传送网络实施浮点全局求和时，通常需要这种广播。

本领域的技术人员将认识到当整数是以2的补码表示时，即使网络硬件仅支持无符号整数求和，只要最终和中间结果不溢出，并且任何两个数之和的进位都不被硬件漏掉的话，就可以获得正确的和。对全局整数和浮点求和运算步骤进行简化，和网络硬件直接支持带符号整数求和并带有正确的溢出处理，都在本发明的范围内。

例如，当硬件仅支持无符号整数求和，并漏掉所有无符号整数溢出的携带位时，如在临时专利申请号60/271,124中公开的超级计算机上实施的，简化的带符号整数求和步骤可以是：

(1)将每个整数加符号扩展到更高的精度，以保证不会发生任何结果溢出；即给所有正整数和零的扩展高位补0，给所有负整数的扩展位补1；

(2)在网络上进行求和。最终的结果将有正确的符号。

以上步骤也可应用于浮点求和的求和步骤。

在全局整数求和描述的基础上进行类似的修改，用到全局求最大值的描述上，也可以很容易地获得浮点求最大值和最小值的方法。

这里还有一个浮点非负数求最大值的特殊例子，该运算可以在一个来回过程中完成，而不需要两个。对于使用IEEE 754标准的浮点二进制算术格式的数来说，就像在大多数现代微处理器中的，不需要额外的本地运算。通过适当的字节排序，每个节点可以只将数字放在混合网络上。对于其它浮点格式，象那些用于一些数字信号处理器的，可能需要一些本地操作。通过对它们绝对值进行全局求最大值，负数求最小值也只要单个来回过程就可获得。

4.使用整数全局求和的全局整体合并运算

图6中阐述了全局整体合并运算。每个节点贡献一个或多个数字。最终结果是这些数字都放进一个数组，在该数组中它们的位置对应于它们来自的位置。例如，来自节点1的数字在最终的数组中出现在第一个，后面紧跟着来自节点2的数字，...，等等。该运算对应于MPI标准中的MPI_ALLGATHER函数。

在支持整数求和的混合网络中，可以很容易地将该函数实现为一次完成的运算。利用零加一个数等于该数的事实，每个节点只需要产生一个数组，该数组的大小等于最终数组，然后将该节点的数放在相应的位置上并将零放在所有对应来自所有其它节点的数的其它位置上。在混合网络上对来自所有节点的数列进行整数求和后，每个节点将获得最终数列，所有的数字都存储在相应位置上。

5.使用整数全局求最大值的全局min_loc和max_loc

这些函数对应于MPI标准中的MPI_MINLOC和MPI_MAXLOC。例如，除了寻找全局最小值和最大值外，还给每个数加了一个标记，使得人们可以找到是哪个节点有全局最小值或最大值。

在支持整数全局求最大值的混合网络中，该函数是直接实施的。作为例子，我们将阐述全局max_loc。假设节点j，j＝1，...，N的数为X_j，标记为K_j。假设M为一个大整数，M＞max(K_j)，节点j只需要将两个数：

X_j

M-K_j

作为一个单元放在混合网络中进行全局整数求最大值。在该运算的最后，每个节点将收到：

X

M-K

其中X＝max(X_j)是所有X_j的最大值，K是对应最大数X的标记数。假如等于最大值X的不止一个数，那么K是最小的标记数。

在上述过程中，将X_j改为P-X_j，其中P是一个大正整数且P＞max(X_j)，就可以类似地得到全局min_loc。

在全局求最大值或最小值运算中将标记数附加到数字后的想法也可应用到浮点数上。在全局浮点数求和操作步骤的讨论中使用类似于上述的步骤。

6.其它运算：

在临时专利申请60/271,124中描述的超级计算机系统上，混合网络也支持其它全局位运算AND，OR和XOR。这使得全局简化位运算可以很容易地实施，如MPI标准中的MPI_BAND，MPI_BOR和MPI_BXOR。基本上，每个节点只需将用于全局运算的操作数放到网络上，网络就可以自动处理全局运算。

另外，只要在位运算中仅使用一位，就可以实施逻辑运算MPI_LAND，MPI_LOR和MPI_LXOR。

最后，每个全局运算也意味着全局障碍(barrier)运算。这是因为直到所有操作数都被注入网络，网络才会继续工作。因此，使用任何一个全局算术运算，如全局位运算AND，就可实施有效的MPI_BARRIER运算。

7.使用环形和树形两种网络的运算

依靠环形和树形网络的相对带宽，并且依靠在浮点和定点表示法之间进行转换所必要的开销，同时使用环形和树形网络进行全局浮点简化运算可能更有效。在这种情况下，环形网络用于进行简化运算，而树形网络用于向所有节点广播最终结果。在环形网络中进行简化运算的现有技术众所周知。可是，在现有技术中，广播阶段也是在环形网络中进行的。例如，在图7中以30表示的一个3×4环形网络(或网状网络)中，沿着行进行简化运算，然后在一行的最后一个节点转到下一行。特别地，在求和简化运算中，图7描述了节点Q20插入一个数据包，并将它传送到节点Q21。Q21处理该数据包，将它的相应元素和该引入的数据包的相应元素相加，并将包含和的数据包传送到Q22。Q22处理该数据包，将它的相应元素和该引入的数据包的相应元素相加，并将包含和的数据包传送到Q23。每一行都重复该过程。节点Q23将它的本地值和来自Q22的数据包中的相应值相加，并将作为结果的数据包传送到Q13。节点Q13将它的本地值和来自Q12和Q23的数据包的值相加，并将作为结果的和送到Q03。Q03将它的本地值和来自Q13和Q02的数据包的相应值相加。这时Q03拥有全局和。在现有技术中，该全局和是通过环形网络送到所有其它节点(而不是如图中所示在树形网络上)。扩展到更多的节点和更加高维的环形网络在本领域的技术人员能力范围内，所以也属于本发明的范围。为了对很多值进行简化运算，以流水线方式使用多个数据包。

可是，和环形网络相比，使用树形网络可以进行更加快速并且更加有效的最终广播操作。在图8中说明了这一点。在简化步骤中通过减少跳点数可以进一步优化性能。例如，数据包可以在一行的中间进行传送(和相加)，而不是在一行的末端。

在一个三维环形网络中，在上述基础上直接扩展导致了在每个z平面中单个节点沿着z方向对它们的值求和。这有个缺点，需要这些节点处理三个引入数据包。例如节点Q03z必须接收来自Q02z，Q13z和Q03(z+1)的数据包。假如该处理器不够快，这就会成为运算中的瓶颈。为优化性能，我们修改通信模式，使得没有节点需要在环形网络中处理两个以上引入数据包。这在图8中进行阐述。在图中，为了沿着z方向求和，节点Q03z将它的数据包送到节点Q00z。另外，节点Q00z不传送它的数据包到节点Q01z，而只是接收来自节点Q00(z+1)的数据包，并将它的本地值和两个引入数据包的相应值相加。最后，节点Q000通过树形网络广播最终结果。

显然，这里公开的发明是经过很好的设计，用来满足上述目的的，而本领域的技术人员还可以设计许多变体和实施例，意图是所附权利要求涵盖所有在本发明的真正精神和范围内的变体和实施例。