一种大规模并行计算系统互连网络构造方法

摘要

本发明公开了一种大规模并行计算系统互连网络构造方法，OCT互连网络由8×2k×2m个节点组成，首先将每8个节点连接成一个Octagon互连网络，共得到2k×2m个Octagon互连网络，每个Octagon互连网络中节点用4位约翰逊码进行编码；再将每个Octagon互连网络中节点编码相同的2k×2m个节点连接成每行2m个节点和每列2k个节点的Torus互连网络，共得到8个Torus互连网络，每个Torus互连网络中节点用k+m位约翰逊码进行编码，即该OCT互连网络可记为OCT(k，m)互连网络，其中k，m为自然数是互连网络节点数量的参数。本发明在保持节点度不变进行互连网络的扩展；OCT(k，m)互连网络是对称正规互连网络，节点编码采用约翰逊编码方法，任意相邻节点的编码有且仅有一位不同，使得路由算法简单高效。

说明书

技术领域

本发明属于并行计算技术领域，尤其涉及一种大规模并行计算系统互连网 络构造方法。

背景技术

随着硬件技术的不断发展，特别是超大规模集成电路工艺的发展，使得包 含成千上万处理器的大规模多处理器系统成为可能。例如天河-1A有7168计算 节点、富士通的超级计算系统超过80，000计算节点。在未来的几年，新的应 用与算法促使单芯片处理器核的数量将达到20世纪80年代建立的大规模超级 计算系统节点数量。我们正在走向E级计算(Exascale Computing)时代，预计 2018年，超级计算系统将达到1exaFLOPS(1018FLOPS)，进入E级计算 (Exascale Computing)时代。

进入E级计算时代，多处理器系统规模将达到几百万到上千万个处理器核， 互连网络对如此大规模的多处理器系统的性能具有重要的影响，将决定未来大 规模并行应用的计算和存储性能。为了提高并行计算的通信效率，人们一直在 研究结构简单、节点度小、网络直径小、路由策略简单以及良好可扩展的互连 网络。

Torus互连网络的拓扑结构具有正规性、对称性、容错性、短直径、可嵌 入性等特殊性质，因此深受研究者和实践者们的欢迎，是一种最为重要和最具 吸引力的并行计算机互连网络拓扑结构。然而，在几百万到上千万个处理器核 的互连网络中，传统Torus互连网络的直径变得非常大，不适合用于未来并行 系统的互连，同时，由于许多并行程序要在一组节点内进行频繁的通信(即局 部通信)，因此，提出了多种基于Torus的分层互连网络(HINs，Hierarchical  Interconnection Networks)。在这些分层互连网络中，由计算节点组成较低层 互连网络进行局部通信，由簇组成的较高层互连网络用于远程通信。这些分层 互连网络的直径都是由每层网络直径之积，相对直径仍然较大。Octagon互连 网络被F.Karim等人用于片上互连网络，该互连网络的拓扑结构具有正规性、 对称性、短直径等性质。

2k×2m的2维Torus互连网络(简称为T(k，m))是具有下述性质的一种互 连网络：1)由2k×2m个节点和8k×m条直接链路组成；2)用m位的2m个约翰 逊编码标识节点的横坐标，用k位的2k个约翰逊编码标识节点的纵坐标，把节 点的纵坐标作为高位横坐标作为低位组合成一个节点编码，这样，任意一个节 点可以用k+m位的二进制编码标识；3)节点编码的规则为：当且仅当T(k，m) 中两个节点的编码有且仅有一位不同时，两个节点是相邻的，即这两个节点之 间有一直接链路。

图1给出了T(k，m)互连网络的拓扑结构及节点编码(k＝2，m＝3)。T(k，m) 互连网络具有以下的良好性质：①每行每列的节点编码都是二进制单位距离循 环码；②任意一个节点有且仅有四个相邻节点(当节点编码位数大于或等于5 时，2维格雷编码不满足此特性)，自然形成了Torus结构；③若k或m增加 一位，则相应的节点个数只增加4m个或者4k个(2维格雷编码形成的节点数 为2k×2m，若k或m增加一位，则相应的节点个数增加为原来节点数目的2倍)； ④将任意两个节点编码异或所得“1”的个数即为两个节点间的最小距离；⑤具有 Hypercube结构简单的路由机制。

Octagon互连网络是具有下述性质的一种互连网络：1)由8个节点和12 条直接链路组成；2)用4位的约翰逊编码标识节点的坐标；3)当互连网络中 两个节点编码有且仅有一位不同或者两个节点编码异或结果的每一位为“1” 时，两个节点是相邻的，即这两个节点之间有一直接链路。

图2是Octagon互连网络的拓扑结构及节点编码。由图2可知，Octagon 互连网络具有以下良好的性质：1)网络中任意节点的连接度均为3，整个网络 的直径为2，网络具有正规性、对称性、短直径、低连接度等优良特性；2)网 络中任意两个节点之间有3条无交的链路，若两个节点直接相连，则这3条链 路的长度分别为1，4，4，否则为2，3，3，因此，具有良好的容错性与并行性；3) 任意两个节点编码异或结果为1个“1”或者4个“1”时，两个节点相邻，任意两 个节点编码异或结果为2个“1”或者3个“1”时，两个节点的距离为2。其缺点是 网络不具备可扩展性。

发明内容

本发明提出了一种大规模并行计算系统互连网络构造方法，构造的互连网 络结合Torus互连网络和Octagon互连网络的优点，具有短直径、正规性、对 称性和良好的扩展性。互连网络构造方法中采用约翰逊编码方法对互连网络节 点进行编码，使得路由算法设计简单，分别设计了基于混合编码的单播、广播 路由算法。

本发明实施例是这样实现的，一种大规模并行计算系统互连网络构造方法， 该方法包括：

首先，将每8个节点连接成一个Octagon互连网络，共得到2k×2m个Octagon 互连网络，每个Octagon网络称为一片；

其次，对每一片采用相同的节点编码方法，即每片中节点都用4位约翰逊码 进行编码；

再次，再将每个片中节点编码相同的2k×2m个节点连接成每行2m个节点和 每列2k个节点的Torus互连网络，可记为T(k，m)互连网络，共得到8个T(k， m)互连网络；

然后，对每个T(k，m)互连网络采用相同的节点编码方法，即每个T(k， m)互连网络中节点都用k+m位约翰逊码进行编码；

这样构造的互连网络称为OCT互连网络，可记为OCT(k，m)互连网络，其中 k，m为自然数是互连网络节点数量的参数。

进一步，OCT(k，m)互连网络采用如下节点编码方法，每个节点编码由两部 分(A_t，A_o)组成，其中A_o(4位约翰逊码)为每个Octagon网络中节点编码，A_t(k+m 位约翰逊码)为每个Octagon片的编码，也即每个T(k，m)网络内的节点编码。

进一步，构造的OCT(k，m)互连网络节点规模可以通过扩展T(k，m)互连网 络而扩展，只要将编码位数增加一位，即m或k增大1，在T(k，m)互连网络中 就增加两行或两列(相应的节点个数就增加4k或4m个)，即在OCT(k，m)网络 基础上增加8×4k或8×4m个节点，形成OCT(k，m+1)或OCT(k+1，m)互连网络； 原来OCT(k，m)网络中每个Octagon互连网络节点连接关系没有变化，节点的 连接度没有变化。在T(k，m+1)或T(k+1，m)互连网络中，除了与新增节点相连 的节点外，其它节点与连接关系没有任何变动。

本发明将Torus互连网络的可扩展性和Octagon互连网络的短直径结合构 造了一种简单的可扩展的OCT(k，m)互连网络。该互连网络是一种节点度为7 的正规对称可扩展的互连网络，可以在保持节点度不变进行网络规模的扩展， 网络节点编码采用约翰逊编码方法，使得路由算法简单高效。分析和实验结果 表明，OCT(k，m)互连网络具有良好通信性能、容错能力、可扩展性，是一种适 合大规模并行计算的互连网络。

附图说明

图1是本发明实施例提供的T(k，m)互连网络及节点编码(k＝2，m＝3)；

图2是本发明实施例提供的Octagon互连网络及节点编码；

图3是本发明实施例提供的大规模并行计算系统互连网络构造方法流程 图；

图4是本发明实施例提供的OCT(k，m)互连网络(k＝2，m＝2)。

具体实施方式

为了使本发明的目的、技术发明及优点更加清楚明白，以下结合实施例， 对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以 解释本发明，并不用于限定本发明。

图3提出了本发明实施案例提供的一种大规模并行计算机系统互连网络构 造方法，该方法包括：

在步骤S101中，首先，每8个节点按照上述Octagon互连网络描述方式连接 成一个Octagon互连网络，共得到2k×2m个Octagon互连网络，每个Octagon互连 网络称为一片；

在步骤S102中，将2k×2m个片按照如下方法连接成Torus网络：2k×2m个片 中节点用4位约翰逊码进行编码，将每个片中节点编码相同的节点按照上述T(k， m)互连网络描述的方式连接成T(k，m)互连网络；

在步骤S103中，OCT(k，m)互连网络的节点编码：OCT(k，m)采用如下编码 方法，每个节点编码由两部分(A_t，A_o)组成，其中A_o(4位约翰逊码)为每个 Octagon互连网络中的节点编码，A_t(k+m位约翰逊码)为每个Octagon片的编码， 也即每个T(k，m)网络内的节点编码；

在步骤S104中，连接成OCT(k，m)互连网络拓扑结构。

图4是本发明实施例提供的OCT(k，m)互连网络(k＝2，m＝2)，图中实线 表示Octagon互连网络链路，虚线表示T(k，m)互连网络链路，小圆圈表示网 络节点，上下左右标号相同的端点之间有直接链路连接。OCT(k，m)互连网络节 点规模的可以通过扩展T(k，m)网络而扩展，只要将编码位数增加一位，即m或 k增大1，在T(k，m)网络中就增加两行或两列(相应的节点个数就增加4k或 4m个)，即在OCT(k，m)网络基础上增加8×4k或8×4m个节点，形成OCT(k， m+1)或OCT(k+1，m)互连网络。原来OCT(k，m)网络中每个Octagon片网络连接 关系没有变化，节点的连接度没有变化。在T(k，m+1)或T(k+1，m)互连网络中， 除了与新增节点相连的节点外，其它节点与连接关系没有任何变动。

构造的OCT(k，m)互连网络的性质：

性质1.OCT(k，m)互连网络是正规互连网络，任意节点的连接度均为7。

由于每个Octagon片是正规互连网络且节点连接度均为3，根据OCT(k，m) 网络的构造过程易知，把Octagon片看作一个节点，该网络就是T(k，m)互连 网络且节点连接度为4，所以，OCT(k，m)网络是正规网络，节点连接度为3+4＝7。

性质2.OCT(k，m)互连网络中任意两个节点间的距离最大值(网络直径) 为k+m+2。

由于T(k，m)互连网络的直径为2m个节点环的直径和2k个节点环的直径 之和，即为m+k，根据OCT(k，m)网络的构造过程易知，把T(k，m)互连网络 看作一个节点，该网络就是Octagon互连网络，其直径为2。所以，OCT(k，m) 网络直径为Torus直径和Octagon直径之和，即m+k+2。

性质3.OCT(k，m)互连网络是对称网络。

根据OCT(k，m)互连网络的构造过程易知，该网络中任何节点标识为原点 都同构于本身，即从任何节点观察网络都是一样的。简化了路由算法的实现， 即路由算法与节点位置无关系。

性质4.OCT(k，m)互连网络的链路数为112×k×m。

OCT(k，m)互连网络的链路数为2k×2m个Octagon链路数12和8个2k×2m 的Torus链路数2×2k×2m之和，2k×2m×12+8×2×2k×2m＝112×k×m。

性质5.OCT(k，m)互连网络的等分宽度为24×k×m。

网络等分宽度是把网络分成两个相等网络时，必须删去的最小通信链路数。 OCT(k，m)互连网络等分是将2k×2m个Octagon互连网络等分，Octagon等分 宽度为6，所以等分宽度为6×2k×2m＝24×k×m。

为了进一步说明OCT(k，m)互连网络的优良特性，表1给出了OCT(k，m) 互连网络、(2k，2m，3)-OMMH(也称为Torus Embedded Hypercube)互连网络和 2维Torus互连网络的对比，其中N＝8×2k×2m＝4k×8m。

表1三种静态网络的性能特征

互连网络中采用约翰逊编码方法，使得OCT(k，m)互连网络具有如下的性 质：对OCT(k，m)互连网络中任意两个节点A(Am+k+3…Am+k， Am+k-1…AmAm-1…A1A0)，B(Bm+k+3…Bm+k，Bm+k-1…BmBm-1…B1B0)，Ai，Bi， Aj，Bj∈{0，1}，i∈{4，…，m+k+3}，j∈{0，1，2，3}，则任意两个节点A， B之间的距离为

由于Octagon片内每个节点编码和T(k，m)内每个节点编码都是约翰逊编 码，由OCT(k，m)互连网络构造过程可知，任意两个节点之间的距离为两个节 点在T(k，m)中的距离与两个节点在Octagon中距离之和。Octagon片内两个节 点之间的距离编码有且仅有一位不同或者两个节点编码异或结果的每一位为 “1”时是相邻节点，即任意两个节点之间的距离是两节点编码不同位的数或者 是两节点编码相同位的数加1；T(k，m)内两个节点编码有且仅有一位不同时是 相邻节点，即任意两个节点之间的距离是两节点编码不同位的数。该性质方便 了路由算法的设计。

OCT(k，m)互连网络的单播路由算法及性能分析：

1)单播路由算法

假设A(A_m+k+3...A_m+k，A_m+k-1...A_mA_m-1...A₁A₀)节点向B(B_m+k+3...B_m+k，B_m+k-1...B_mB_m-1...B₁B₀) 节点发送数据，A节点与B节点(D)的汉明距离其 中“”代表A和B进行按位异或运算，“Hamming”函数代表把A和B异或后 “1”的个数相加运算。由Octagon和T(k，m)节点的编码方法以及OCT(k，m) 互连网络的构造过程可知，OCT(k，m)的最短路径路由过程如下：路由过程如下：

①如果A和B在同一个Octagon片内，那么由2.2节可知，A节点和B节点的T(k， m)编码是相同的，即$\mathrm{Ham}\min g(A_{m+k+3}...A_m{A}_{m-1}...A_5{A}_4\oplus B_{m+k+3}...B_m{B}_{m-1}...B_5{B}_4)\equiv 0,$只 要进行A_o＝A₃...A₀，B_o＝B₃...B₀的Octagon片内路由，源节点A和目的节点B的距离 是1或者2。如果或4，那么节点4直接向节点B发送 数据；否则，计算A_o的三个相邻节点为A_o1，A_o2，A_o3与B_o的距离，将节点A_o的数据 发送到与目的节点距离为1的相邻节点，然后再从相邻节点发送到目的节点B。

②如果A和B在同一个T(k，m)中，那么由2.2节可知，A节点和B节点的 Octagon的节点编码是相同的，即只要进行A_t＝ A_m+k+3...A_mA_m-1...A₅A₄节点向B_t＝B_m+k+3...B_mB_m-1...B₅B₄的T(k，m)网络的路由。T(k，m) 网络左右相邻节点编码只有横坐标相差一位，上下相邻节点只有纵坐标相差一 位，节点A_t的左相邻节点编码为右相邻节点 编码为$A_r=A_{m+k+3}...A_1...A_{k+1}{A}_k{A}_{k-2}...A_p...A_5{A}_4\overline{A_{k-1}},$上相邻节点编码为$A_u=\overline{A_k}{S}_{m+k+3}...$$A_1...A_{k+1}{A}_{k-1}...A_p...A_4,$下相邻节点编码为$A_d=A_{m+k+2}...A_1...A_{k+1}{A}_k\overline{A_{m+k+3}}{A}_{k-2}...A_p...A_5{A}_{k-1},$那么A_t相邻节点与B_t的距离为$H_l=\mathrm{Ham}\min g(A_l\oplus B_t),H_r=\mathrm{Ham}\min g(A_r\oplus B_t),$$H_u=\mathrm{Ham}\min g(A_u\oplus B_t),H_d=\mathrm{Ham}\min g\left(A_d{\oplus B}_t\right)$。H_min＝min{H_l，H_r，H_u，H_d}，将包发 送到H_min所对应的相邻节点并且将A_t修改为该相邻节点的编码，然后计算值，如果H≡0，那么A_t标识的节点即为目标节点，否则重复 前面的过程。

③如果A和B既不在同一个Octagon网络中，也不在同一个T(k，m)网络 中，是任意的两个节点，那么首先按①的方式将数据包在同一Octagon网络中 路由到节点A’(A_m+k-1...A_mA_m-1...B₃B₂B₁B₀)，A’与B在同一个T(k，m)中，然后按 ②的方式将数据包在T(k，m)中路由到目的节点B。

2)算法性能分析

OCT(k，m)的路由算法主要优点在于T(k，m)网络采用约翰逊编码方法，使 得T(k，m)网络中任意两个节点编码异或所得“1”的个数即为两个节点间的最 小距离，并且该编码隐含了全局的路由信息和相邻节点间的关系。使得网络节 点转发数据时，只要存储当前节点和目的节点的编码就可以正确的路由数据。 Octagon网络也采用约翰逊编码方法，任意两个节点编码异或结果为1个“1” 或者4个“1”时，两个节点相邻，任意两个节点编码异或结果为2个“1”或 者3个“1”时，两个节点的距离为2，使得网络路由变得简单。

根据OCT(k，m)单播路由算法，数据在Octagon中传播最坏情况下需要2 轮通信操作，在同一个T(k，m)中传播最坏情况下需要k+m轮通信操作，因此， 最坏情况下总共需要k+m+2轮通信操作。算法能沿着越短的路径将数据从源节 点发送到目的节点，算法的通信效率就越高。以上单播路由算法的每一次转发 数据是按最短路径进行的，所以，最坏情况下，路由的路径不会超过网络的直 径k+m+2，算法的通信效率为1/(k+m+2)。

OCT(k，m)互连网络的广播路由算法及性能分析：

1)广播路由算法

假设由节点A发送数据到其它所有节点。首先，将节点A的数据在所在的 Octagon片内广播到所在片的所有节点，然后收到数据信息的节点将数据采用 递归加倍方法扩散给各自所在的T(k，m)之内的所有节点。

2)算法性能分析

以这种方式进行广播路由，节点A将数据广播给所在Octagon片内的所有节点 需要2轮通信操作，然后数据在T(k，m)之内进行广播需要m+k轮通信操作。 所以，整个广播需要k+m+2轮通信操作，算法的通信效率为1/(k+m+2)。

本发明将Octagon互连网络的短直径和Torus互连网络的可扩展性结合起 来，构造OCT(k，m)互连网络：首先，每8个节点按照定义6的方式连接成一 个Octagon网络，共得到2k×2m个Octagon网络，每个Octagon网络称为一片； 将2k×2m个片按照如下方法连接成Torus网络：2k×2m个片用4位约翰逊码 进行编码，将每个片中节点编码相同的节点按照定义5的方式连接成T(k，m) 互连网络；OCT(k，m)的编码：OCT(k，m)采用如下编码方法，每个节点编码由 两部分(A_t，A_o)组成，其中A_o(4位约翰逊码)为每个Octagon网络的节点编码， A_t(k+m位约翰逊码)为每个Octagon片的编码，也即每个T(k，m)网络内的节点 编码。又设计了基于OCT(k，m)互连网络结构的单播、广播路由算法

以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发 明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明 的保护范围之内。