自洽多阶张量扩展方法及多MPU并行计算系统

摘要

本发明涉及一种自洽多阶张量扩展方法及多MPU并行计算系统，将多个基于MPU架构、集成有外联扩展网络接口的超节点互连成为一部整合的、更大规模的并行计算系统。外联扩展网络接口可以通过打开MPU超节点原有的内联网络的环绕连接来实现，也可以另外增设Axon节点，Axon节点与内联网络中的节点子集进行互连。多阶张量超高扩展方法包括零阶张量扩展、一阶张量扩展和高阶张量扩展。本发明可用于诸如全局求和与全局取大值等全局操作，远端通信，以提高长程通信效率，有效地减少网络半径。同时能够更有效地在扩充系统时，减缓网络半径的增加，降低长程通信的延迟，从而保证了更大规模系统的更高扩展性与可用性。

说明书

技术领域

本发明涉及多处理器系统互连网络及其扩展领域，具体地说，涉及基于MPU系统作为超节点的并行计算系统自洽多阶张量超高扩展方法及采用该方法扩展而成的多MPU超级并行计算系统。

背景技术

本发明与专利申请“内外连网络拓扑架构及自洽扩展该架构的并行计算系统”(中国专利申请号200610029753.0)属于同一个系列。

所述MPU架构为一种K维互连网络系统，其中的每个节点，均位于2^K个相邻节点所组成的K维立方体的体心，并同时可与上述2^K个相邻节点互连，在所述网络系统边界处的节点，位于2^K个相邻的节点和拓扑循环映射节点所组成的一个虚拟K维立方体的体心，并同时与上述2^K个节点互连。

一个MPU系统本身即是一部小型完整的高性能并行计算系统，具有高扩展性、高带宽低延迟等特征。如果能将每个MPU系统视为一个高性能可高耦合的超节点，借助外联扩展网络系统，按照一定的扩展方式，灵活地整合成为一部更大规模的、具有更高计算性能的多MPU超级并行计算系统，则是本发明要解决的技术问题。

发明内容

本发明的目的在于提供一种自洽多阶张量超高扩展方法及采用该方法扩展而成的多MPU超级并行计算系统，能够更有效地在扩充系统时，减缓网络半径的增加，降低长程通信的延迟。

为了实现上述发明目的，本发明的技术方案如下：

一种自洽多阶张量超高扩展方法，将多个基于MPU架构、集成有外联扩展网络接口的超节点互连成为一部整合的、更大规模的并行计算系统；该方法包括：

1-1)零阶张量扩展：

每个MPU超节点打开原有的内联网络的环绕连接，形成外联扩展网络接口；

按照MPU拓扑架构的连接法则，将多个超节点利用外联扩展网络接口互连起来，从而使得所有打开的环绕连接重新在超节点间得到闭合；

1-2)一阶张量扩展：

在每个MPU超节点，增加若干Axon节点；

上述的Axon节点，一方面，与内联网络中的一个含多个节点的子集进行互连，另一方面，提供Axon节点间互连的网络接口；

按照一定的Axon节点间的互连方式，所有Axon节点互连成为一个一阶外联扩展网络系统；

1-3)高阶张量扩展：

以由比它低一阶张量扩展方式生成的MPU系统为超节点；

在上述的超节点中，增加若干高阶Axon节点，作为辅助的通信节点；

上述的高阶Axon节点，一方面，与内联网络中的一个低一阶Axon节点子集进行互连，另一方面，提供高阶外联扩展网络的接口；

按照一定的Axon节点间的互连方式，所有Axon节点互连成为一个高阶外联扩展网络系统。

对应地，采用自洽多阶张量方式扩展而成的多MPU超级并行计算系统包括：

多个基于MPU架构、集成有外联扩展网络接口的超节点；

一种或多种混和的自洽多阶张量扩展方式，此方式用于互连各个超节点的外联扩展网络接口，形成外联扩展网络系统，从而将各个超节点互连成为一部整合的、更大规模的并行计算系统。

本发明可用于诸如全局求和与全局取大值等全局操作，远端通信，以提高长程通信效率，有效地减少网络半径。同时，本发明提出的互连网络拓扑方式，还可应用于任意类型节点间的扩展互连网络的搭建，比较通常所采用的简易外联网络拓扑，如树型拓扑、星型拓扑，能够更有效地在扩充系统时，减缓网络半径的增加，降低长程通信的延迟，从而保证了更大规模系统的更高扩展性与可用性。

附图说明

为了更透彻、更直观地理解本发明的设计方案和特点，下面参考相关的附图进行详细描述和说明，其中：

图1是一个已知的2维MPU(4×4)系统的实施例图；每个节点代表完整的MPU(4×4)系统内联网络中的一个节点，其中，虚线代表了环绕连接，实线代表了内部连接。

图2是一个基于MPU(4×4)系统、用于零阶张量扩展的超节点实施例图；其中，虚线标示了外联网络接口。

图3是一个零阶张量扩展方式的实施例图。

图4至图7是基于MPU(4×4)系统、用于一阶张量扩展的单Axon超节点实施例图；Axon节点分别与MPU(4×4)系统中的1个、4个、16个和32个节点相连。

图8、图9是基于MPU(4×4)系统、用于一阶张量扩展的多Axon超节点

实施例图。

图10是单Axon超节点互连方式的实施例图。

图11是多Axon超节点互连方式的实施例图。

具体实施方式

在本发明中，每个MPU系统被视为一个高性能、具有MPU内外连网络系统架构的超节点，通过多阶张量扩展方式，互连成为多MPU超级并行计算系统。所述的多阶张量扩展方式包括零阶、一阶和高阶张量扩展方式。

零阶张量扩展方式，或称为自然扩展方式，是一种最直接的、甚为简单直观的扩展方式。该扩展方式是展开MPU系统内联网络的环绕连接，将各个不同的超节点互连起来的。首先，对于一个完整的MPU系统，我们将所有或部分闭合的环绕连接打开，形成用于外联网络连接的接口。这里的环绕连接是指一个MPU拓扑结构的边界节点与拓扑循环映射节点间的连接，如图1所示。然后，通过对应边界点上的外联网络接口的互连，所有的超节点可整合成一个更大规模的MPU系统。就本质而言，通过这种方式扩展生成的MPU并行计算系统，在全局上，其互连网络是和完整的MPU拓扑架构完全同构的，可以被视为是一个更大规模的MPU系统。

零阶张量扩展方式的优势在于它简捷而易于实现。同时，不用增加新的通信节点，每个节点的节点度保持不变，超节点间的外联网络通信仅与内联网络的边界节点发生关系，全局拓扑架构一致。只是系统的网络直径随系统规模的增大，也相应地在每一维空间方向线性增加。零阶张量扩展方式的系统定义如下：

定义1  设超节点A和B的内联网络系统分别为K维MPU(N_A1×N_A2×L×N_AK)系统和K维MPU(N_B1×N_B2×L×N_BK)系统，且满足：至少存在K-1个维度上，系统A和B的节点数目是相等的(零阶张量扩展的必要条件)。不妨设N_Aj＝N_Bj≡N_j j∈[1，K-1]，N_AK＝N_A，N_BK＝N_B。则在这K-1维超平面上，系统A和B打开所有边界节点处的环绕连接，形成外联扩展网络接口，然后在超节点间的对应边界处互连，形成外联扩展网络。根据拓扑循环性质，所有打开的环绕连接都将被两相连的系统A与B闭合。这一扩展方式，称为零阶张量扩展方式。其数学表达式记为

MPU(N₁×N₂×L×N_K-1×(N_A+N_B))≡

            {MPU(N₁×N₂×L×N_K-1×N_A)}{MPU(N₁×N₂×L×N_K-1×N_B)}

则由以上方式扩展生成的多MPU超级并行计算系统，总共集成了个节点。以此类推，对于任意M个满足零阶张量扩展条件的超节点，其零阶张量扩展所生成的新的MPU系统记为

$$ >>MPU>=>>(>>N>1>>\times >>N>2>>\times >L>\times >>N>K>>)>>\equiv >>\Sigma >>j>=>1>>M>>\oplus >\{>MPU>>(>>N>>l>>j>1>>>>\times >>N>>l>>j>2>>>>\times >L>\times >>N>>l>jK>>>)>>\}>>$$

图3中给出了一个2□2的零阶张量扩展方式的实施例，按照零阶张量扩展方式，利用外联扩展网络接口，将4个图2所示的超节点进行互连。即

$$ >>MPU>>(>8>\times >8>)>>\equiv >>\Sigma >>i>=>1>>2>>\oplus >\{>\{>MPU>>(>4>\times >4>)>>\}>\oplus >\{>MPU>>(>4>\times >4>)>>\}>\}>=>>\Sigma >>i>=>1>>2>>>\Sigma >>j>=>1>>2>>\oplus >\{>MPU>>(>4>\times >4>)>>\}>.>>$$

一阶张量扩展方式，是借助于MPU拓扑架构的思想，不仅要在每个超节点的外联网络中实现完整的MPU拓扑架构，而且要在互连超节点的内联扩展网络中也实现完整的MPU拓扑架构。这样，内联网络系统和外联网络系统就可同时具备MPU拓扑架构的优点，以保证由此方法而扩展生成的多MPU超级并行计算系统具有高耦合性、高带宽低延迟、高可扩展等特征。特别地，在一阶张量扩展方式中，所述的超节点可以是由零阶张量扩展方式生成的一个大规模的超节点，其中的内外连网络一起被视为其内联网络。在一阶张量扩展方式中，我们保持每个超节点的内联网络MPU拓扑架构的完整性，同时，增加一些辅助通信和协助外连的节点，即一阶Axon节点，来提供外联扩展网络的接口。根据超节点具有Axon节点数目的不同，Axon节点互连方式，又进一步划分为单Axon超节点互连方式和多Axon超节点互连方式。

单Axon超节点互连方式是，每个超节点仅具有一个Axon节点，用于外联扩展网络的连接与其他功能。这个Axon节点，按照一定规律，与MPU系统内联网络中的一个一定数目的节点子集互连。在互连Axon节点构建外联扩展网络的时候，每个Axon节点又被视为一个虚拟的内联网络中的节点，按照原有的MPU拓扑架构，互连成为一个外联扩展网络。

定义2  设超节点为K维MPU(N₁×N₂×L×N_K)系统，则其内联网络节点数为$$ >>M>=>2>>\Pi >>j>=>1>>K>>>N>j>>,>>$$所有这些节点组成的集合为$$ >>MPU>=sup>>>\{>>P>j>>\}>>>j>=>0>>>M>->1>sup>>,>>$$P_j表示第j个内联网络节点，j∈[0，M-1]。每个超节点具有一个Axon节点与一个内部节点子集互连，设该子集为Axon＝{P_j|0≤j≤M-1}。所有的Axon节点，按照L维MPU(M₁×M₂×L×M_L)拓扑结构进行互连，即每个Axon节点视为该虚拟的内联网络中的一个节点，从而形成一套外联扩展网络。这一扩展方式，称为单Axon超节点互连方式，定义为

        MPU((N₁×L×N_K)×(M₁×L×M_L))≡

                   MPU(N₁×N₂×L×N_K)MPU(M₁×M₂×L×M_L)

则由以上方式扩展生成的多MPU超级并行计算系统，总共集成了个节点，以及个Axon节点。

多Axon超节点互连方式是，每个超节点具有多个Axon节点，来提供外联扩展网络接口。每个Axon节点，按照一定规律，与MPU系统内联网络中的一个一定数量的节点子集互连。所有Axon节点组成的集合，又可分成若干子集合。每个子集中的Axon节点，按照一定的MPU拓扑方式，互连成为一个独立的外联扩展网络。所有这样的外联扩展网络，构成一个整合的外联扩展网络系统。实质上，这样的多Axon的MPU系统可由零阶张量扩展而成。以下，我们首先定义一些集合。

定义3  在多Axon超节点互连方式中，我们使用如下的集合符号进行表述。

设每个超节点A具有R个Axon节点，记为：A₀，...，A_R-1，其中，A_j表示超节点A的第j个Axon节点，j∈[0，R-1]。设多MPU超级并行计算系统一共集成有P个这样的超节点。Axon_k表示由所有超节点的第k个Axon节点组成的集合，即：Axon_k＝{所有超节点的A_k}，k∈[0，R-1]。设∑表示所有Axon节点的集合，则有：$$ >>S>=>>>>\cup >>>k>=>0>>>R>->1>>>Axo>>n>k>>.>>$$我们把集合∑的元素个数(MPU系统中节点个数)记作card(∑)，则card(∑)＝P×R，card(Axon_k)＝P。又设集合∑划分为N个独立的子集合：S₀，S₁，...，S_N-1，且$$ >>Sj>=>>>>\cup >>>k>=>0>>>N>->1>>>>S>k>>.>>$$

如果集合S中的所有Axon节点组成一个统一的外联扩展网络，那么，我们就称其为I型多Axon超节点互连方式。如果每个子集合S_k中的所有Axon节点组成一个独立的外联扩展网络，N个这样独立的外联扩展网络组成一个整合的外联扩展网络系统，那么，我们就称其为II型多Axon超节点互连方式。I型多Axon超节点互连方式，可视为II型多Axon超节点互连方式的一个特例，即N＝1时的情况。

定义4  设超节点为K维MPU(N₁×N₂×L×N_K)系统，具有R个Axon节点。设共有P个这样的超节点。所有的Axon节点，按照L维MPU(M₁×M₂×L×M_L)拓扑结构，互连成为一个外联扩展网络。其它集合符号如前定义3所述。则I型多Axon超节点互连方式的定义为

        (MPU(N₁×L×N_K)MPU(M₁×L×M_L))_S

则由以上方式扩展生成的多MPU超级并行计算系统，总共集成了$$ >>2>P>>(>>\Pi >>j>=>1>>K>>>N>j>>)>>=>>4>R>>>(>>\Pi >>j>=>1>>K>>>N>j>>)>>>(>>\Pi >>i>=>1>>L>>>M>i>>)>>>$$个节点，及$$ >>R>\times >P>=>2>>(>>\Pi >>i>=>1>>L>>>M>i>>)>>>$$个Axon节点。

定义5  设超节点为K维MPU(N₁×N₂×L×N_K)系统，具有R个Axon节点。设共有P个这样的超节点。所有的Axon节点分成N个独立的子集合，S₀，S₁，...，S_N-1。每个子集合S_j中的所有Axon节点，按照MPU(M₁^j×M₂^j×L×M_Lj^j)拓扑结构，互连成为一个独立的外联扩展网络。N个这样独立的外联扩展网络，组成了一套完整的外联扩展网络系统。其它集合符号如前定义3所述。则II型多Axon超节点互连方式的定义为

$$ >>>\Sigma >>j>=>1>>>N>->1>>>>>(>MPU>>(>>N>1>>\times >L>\times >>N>K>>)>>\otimes >MPU>>(sup>>M>1>jsup>>\times >L>\times sup>>M>>L>jj>>jsup>>)>>)>>>S>j>>>>$$

则由以上方式扩展生成的多MPU超级并行计算系统，总共集成了个节点，及R×P个Axon节点。

高阶张量扩展方式，是指二阶及二阶以上的张量扩展方式。二阶张量扩展方式是将一个由一阶张量扩展方式生成的MPU系统视为一个规模更大的超节点，其内外连网络系统均被视为其内联网络。其中，所有的用于提供一阶张量扩展网络接口的Axon节点，即一阶Axon节点，被视为该超节点内联网络中的节点。类似于一阶张量扩展方式，在二阶张量扩展方式中，保持上述每个超节点内联网络的完整性，同时，增加一些辅助通信和协助外连的节点，即二阶Axon节点，来提供二阶张量扩展网络的接口。一方面，每个二阶Axon节点，按照一定规律，与超节点的一个一定数目的一阶Axon节点子集互连；另一方面，所有的二阶Axon节点，仍然按照前述的单Axon超节点互连方式或多Axon超节点互连方式，互连成为一个完整的外联扩展网络系统，即二阶张量外联扩展网络系统，从而完成二阶张量扩展。

同理，对于任意更高的K阶张量扩展方式，是将K-1阶张量扩展方式生成的MPU系统视为新的超节点，其内外连网络视为新的内联网络，其K-1阶Axon节点视为这一超节点内联网络中的节点。同时，增加一些新的K阶Axon节点，作为辅助通信和协助外连的节点，来提供K阶张量扩展网络的接口。一方面，每个K阶Axon节点，按照一定规律，与超节点内的一个一定数目的K-1阶Axon节点子集互连；另一方面，所有的K阶Axon节点，按照单Axon超节点互连方式或多Axon超节点互连方式，互连成为一个完整的外联扩展网络系统，即K阶张量外联扩展网络系统，从而完成K阶张量扩展。

实施例1  零阶张量扩展(MPU(4×4)MPU(4×4))(MPU(4×4)MPU(4×4))

每个超节点如图2所示，具有基于MPU(4×4)拓扑结构的内联网络系统，及虚线所示的外联网络接口。按照零阶张量扩展方式，如图3所示，将外联扩展网络接口对应相连，4个超节点组成了一个完整的MPU(8×8)系统。

实施例2  单Axon超节点一阶张量扩展方式MPU(4×4)MPU(4×4)

每个超节点可以是图4至图7所示有的一种，具有完整的MPU(4×4)内联网络系统，同时仅具有一个Axon节点。根据单Axon超节点互连扩展方式，如图10所示，每个单Axon超节点可视为一个MPU系统中的虚拟节点，按照MPU(4×4)拓扑连接方式，将所有的Axon节点互连起来，形成一套外联扩展网络。将32个Axon节点，按照MPU(4×4)拓扑架构模式，互连成一套外联扩展网络，组成了一个完整的MPU(4×4)MPU(4×4)系统。该系统具有1024个内联网络的节点，和32个Axon节点，以及由一套外联网络组成的外联扩展网络系统。如果每个单Axon超节点采用如图4至图7中的一种模型，那么该扩展方式则记为MPU(4×4)MPU(4×4)，总共可集成1024个节点，以及32个Axon节点。

在图4至图7中，用单个Axon节点为一个如图1所示的完整MPU(4×4)系统提供外联扩展网络接口。从图4到图7，Axon节点分别与MPU(4×4)系统中的1个、4个、16个和32个节点相连，从而使得内联网络中的节点到Axon节点的平均距离依次减少。

  单Axon超节点模型  图4  图5  图6  图7  内部节点到Axon节点的平均距离(hop)  3.6  2.3  1.5  1.0  内部节点到Axon节点的连接数  1  4  16  32

实施例3  I型多Axon超节点一阶张量扩展方式(MPU(4×4)MPU(4×4))S

每个超节点如图8所示，具有完整的MPU(4×4)内联网络系统，同时具有4个Axon节点。一共有8个这样的超节点。根据I型多Axon超节点互连方式，如图11所示，将所有的32个Axon节点，按照MPU(4×4)拓扑架构模式，互连成一套外联扩展网络。由此扩展生成的(MPU(4×4)MPU(4×4))S并行计算系统，具有256个内联网络的节点，和32个Axon节点，以及由一套外联网络组成的外联扩展网络系统。我们采用带有4个Axon节点的MPU系统作为一个超节点，Axon节点标号从#0到#3。一共有8个这样的超节点，标号从0到7。我们将这32个Axon节点，互连成一个统一的外联扩展网络，其连接拓扑架构与MPU(4×4)系统是同构的，具体细节如图所示。如果每个多Axon超节点采用如图9所示的模型，那么该扩展方式则记为(MPU(4×4)MPU(4×4))_S，其中，$$ >>Sj>=>>>>\cup >>>k>=>0>>3>>>A>k>>,>>$$总共可集成256个节点，及32个Axon节点。

实施例4  II型多Axon超节点一阶张量扩展$$ >>>\Sigma >>j>=>0>>3>>>>(>MPU>>(>4>\times >4>)>>\otimes >MPU>>(>4>\times >4>)>>)>>>A>j>>>>$$

每个超节点如图9所示，具有完整的MPU(4×4)内联网络系统，同时具有4个Axon节点，记为Axon#0，Axon#1，Axon#2和Axon#3。一共有32个这样的超节点。根据II型多Axon超节点互连方式，将每个子集合A_k中的32个Axon节点(k□[0，3])，按照MPU(4×4)拓扑架构模式(如图10所示)，互连成一套外联扩展网络。一共4套这样的外联扩展网络，组成了一个完整的外联扩展网络系统。由此扩展生成的$$ >>>\Sigma >>j>=>0>>3>>>>(>MPU>>(>4>\times >4>)>>\otimes >MPU>>(>4>\times >4>)>>)>>>A>j>>>>$$并行计算系统，具有1024个内联网络的节点，和128个Axon节点，以及由4套独立的外联扩展网络组成的外联扩展网络系统。

综上所述的零阶、一阶和高阶张量扩展方式，共同组成了本专利提出的并行计算系统自洽多阶张量超高扩展方法，针对专利“内外连网络拓扑架构及自洽扩展该架构的并行计算系统”中提出的MPU系统，提供了一套完整的超高扩展方式。另外，我们也可同时混合使用多种扩展方式，来提高整个并行计算系统的长程通信效率，以增加大规模并行计算系统的扩展性。同时，本发明不仅能够应用于MPU系统的自洽多阶超高扩展方式的设计，而且可以应用于其它类型的节点间的扩展互连网络的搭建，例如：每个节点可以是多路的SMP节点等，以及任何有关于交换网络结构的扩展设计之中。任意类型节点，可以是向量并行机、共享存储的对称多处理系统，也可以是一个小的集群系统，等等。高阶Axon节点间的互连方式，既可采用单Axon超节点互连扩展方式，也可采用多Axon超节点互连扩展方式。既可单独采用所述扩展方式中的一种，来扩展成为多MPU超级并行计算系统。同时，也可同时采用其中的多种混合扩展方式，这样既可在全局上，保持与MPU拓扑架构的同构性，又可借助辅助多阶外联扩展网络系统，来有效地减少长程通讯延迟。应当指出，所有这些修改或者变换都不可能脱离本发明的保护范围。