一种用于片上网络的混合互连结构、其网络节点编码方法及其混合路由算法

摘要

本发明涉及一种用于片上网络的混合互连结构。所述混合互连结构包括全局网络和多个局部网络，所述全局网络为由多个网络节点组成的二叉树结构，所述局部网络为由多个网络节点组成的二维Mesh结构，局部网络的中心节点与所述全局网络上的网络节点相连。本发明中全局网络采用二叉树结构和局部网络采用二维Mesh结构，并设计了匹配的网络节点编码方法和混合路由算法，从而能够平衡局部和全局之间的数据流量，能够减少局部节点之间的路径平均距离，减少网络直径，从而提高网络的平均传输延迟和网络数据吞吐量，同时还有效的节省了连线资源，在相同的连线资源的基础上，能够加入的网络节点数更多。

说明书

技术领域

本发明属于片上网络互连技术领域，具体涉及用于片上网络的混合互连结 构、其网络节点编码方法及其混合路由算法。

背景技术

随着半导体工艺技术的快速发展，微电子技术从集成电路设计向系统芯片 设计飞速转变着。然而随着工艺技术的持续发展，出现了一些与 SoC(system-on-chip)自身特征相关的问题，且这类问题在SoC传统架构下难以 解决。基于此情形，片上网络NoC(networkonchip)概念在1999年左右被提 出。其核心思想是计算单元与通信架构相互分离，而其通信部分则借鉴了计算 机网络技术，并将其移植到集成电路设计中来，这样便可以从体系结构上解决 片上通信的瓶颈问题。

片上网络的拓扑结构定义了网络中各个模块在芯片上分布和连接的物理布 局。拓扑结构的选择将直接影响到网络节点度、网络直径、网络规模，从而影 响了网络时延、吞吐量、能耗、面积以及容错等，最终对网络性能参数产生重 要影响。因此，在片上网络中，对拓扑结构的设计研究是目前研究的重点之一。

NoC的研究通常涉及以下几种拓朴结构：二维网格结构(2DMesh)，蜘蛛网， 肥胖树，环，网格以及带环网格等。其中，二维网格结构是一种规则型结构， 是片上网络研究过程中最常用、最简单直观的拓扑结构，Mesh结构具有可扩展 性好、规则性、逻辑结构简单、便于实现和分析等优点，因此在片上网络中得 到广泛应用。这种结构设计的缺点是：对称性易引起中央区域拥塞和热点，造 成网络负载分布不均衡；其边缘节点相对闭塞，远端节点间长距离多跳通信易 造成延迟在网络架构方面，必须斟酌拓扑结构的路径平均距离、可扩展性、节 点数量、网络直径等。

片上网络的路由算法依赖于网络拓扑结构。在拓扑结构相同的片上网络中， 路由算法决定了数据包传输的路径，从而决定了网络链路的负载分布和拥塞程 度。不同路由算法所决定的通讯路径长短将直接影响到整个片上网络的传输延 迟、路由传输能耗和缓存排队能耗。良好的片上网络路由算法不仅能够平衡网 络负载分布，而且可以使路由路径尽可能短。这些都将对网络吞吐量、通信延 迟以及能耗起到关键性作用，也将极大影响整个网络的通信性能，是片上网络 设计过程中的重点和难点。

在实际应用中，片上网络的各个节点之间的通信频率是有差别的，往往局 部各核之间通信较为频繁，采用上述的几种单一的拓扑结构不能很好的兼顾到 这种差异性，很难满足现实的需求。

发明内容

本发明要解决的技术问题是：提供一种能够平衡全局和局部网络之间数据 流量的用于片上网络的混合互连结构。

基于混合互连结构，本发明的另一目的是提供一种与用于片上网络的混合 互连结构匹配的网络节点编码方法。

基于混合互连结构，本发明的又一目的是提供一种与用于片上网络的混合 互连结构匹配的混合路由算法。

本发明解决其技术问题所采用的技术方案是：一种用于片上网络的混合互 连结构，包括全局网络和多个局部网络，所述全局网络为由多个网络节点组成 的二叉树结构，所述局部网络为由多个网络节点组成的二维Mesh结构，局部网 络的中心节点与所述全局网络上的网络节点相连。

具体的，所述二维Mesh结构呈N×N的正方形结构，其中N为正方形边的 网络节点数，当N为偶数时，中心节点为二维Mesh结构在中心处形成的正方形 的四个端部的网络节点；当N为奇数时，中心节点为二维Mesh结构在中心处的 网络节点。

一种用于片上网络的混合互连结构的网络节点编码方法，所述网络节点的 地址编码为(L,X,Y,Q),其中L＝L1_L2…_Lk…_Ln,n为二叉树结构的层数，1＜k ≤n，X和Y为用XY坐标编码方式以局部网络的中心节点为坐标原点获得的坐标 值，Q值为用于表示所述网络节点是在二叉树结构上还是局部网络的坐标原点的 值，

当所述网络节点为二叉树结构上第1层的节点时，L1＝L2＝…＝Lk＝…＝Ln＝00， X＝Y＝0；

当所述网络节点为二叉树结构上第k层的节点时，L1＝L(k+1)＝…＝Ln＝00， X＝Y＝0，L2至Lk中的任一个记为La，La值根据第k层节点在a层的父节点的位 置确定，当在a层的父节点为a层的左节点，La＝10，当在a层的父节点为a层 的右节点，La＝11；

当所述网络节点为N×N的二维Mesh结构上的网络节点时，L值等于二叉树 结构上与该网络节点所在局部网络连接的网络节点的L值， X＝X₀_Xoffset,Y＝Y₀_Yoffset,其中，X₀和Y₀分别为表示所述网络节点相对于坐标 原点方向的值，Xoffset和Yoffset分别为所述网络节点相对坐标原点的在X方 向和在Y方向的偏移量。

优选的，当N为偶数时，选择二维Mesh结构在中心处形成的正方形的四个 端部中的一个网络节点为坐标原点，当N为奇数时，选择二维Mesh结构在中心 处的网络节点为坐标原点。

具体的，当所述网络节点在二叉树结构上时，Q＝1；当所述网络节点在二维 Mesh结构上且为坐标原点时，Q＝0；当所述网络节点在二维Mesh结构上且不是 坐标原点时，Q为无效值。

一种用于片上网络的混合互连结构的混合路由算法，当数据在片上网络的 网络节点之间进行传输通信时，数据输入的网络节点为源节点，数据输出的网 络节点为目标节点，通过二叉树算法和/或XY路由算法确定数据从源节点传输 到目标节点的传输路径，当源节点和目标节点在全局网络的二叉树结构上时， 采用二叉树算法确定数据的传输路径；当源节点和目标节点在同一局部网络的 二维Mesh结构上时，采用XY路由算法确定数据的传输路径；当源节点和目标 节点两个网络节点中的一个在全局网络的二叉树结构上，另一个在局部网络的 二维Mesh结构上时，采用二叉树算法确定在二叉树结构上的网络节点至二叉树 结构上与对应局部网络连接的网络节点的传输路径，采用XY路由算法确定在二 维Mesh结构上的网络节点到中心节点的传输路径；当源节点和目标节点在不同 局部网络的二维Mesh结构上时，采用XY路由算法确定源/目标节点到源/目标 节点所在局部网络的中心节点的传输路径，采用二叉树算法确定二叉树结构上 与源节点所在局部网络连接的网络节点到二叉树结构上与目标节点所在局部网 络连接的网络节点的传输路径。

优选的，根据上述的网络节点编码方法，确定数据从源节点传输到目标节 点的传输路径并根据传输路径进行数据的传输，具体包括如下步骤：

1)根据源节点和目标节点的地址编码中X、Y和Q的值判断源节点和目标 节点的位置，按照二叉树算法和/或XY路由算法确定传输路径，当网络节点的X 和Y的值为零且Q＝1时，所述网络节点在全局网络的二叉树结构上，当网络节 点的X和Y的值为零且Q＝0时，所述网络节点为局部网络的二维Mesh结构上的 坐标原点，当网络节点的X和Y的值不都为零，所述网络节点为在局部网络的 二维Mesh结构上的非坐标原点，

当源节点和目标节点均在全局网络的二叉树结构上，转到步骤2)，当源节 点和目标节点均在局部网络的二维Mesh结构上，转到步骤3)，当源节点在全 局网络的二叉树结构上，目标节点在局部网络的二维Mesh结构上转到步骤4)， 当源节点在局部网络的二维Mesh结构上，目标节点在全局网络的二叉树结构上 转到步骤5)；

2)采用二叉树算法确定传输路径，即将源节点与目标节点的地址编码中的 L进行对比，确定传输路径，数据沿确定的传输路径从源节点传输至目标节点， 具体为：

2.1)从L1位到Ln位寻找源节点与目标节点第一个不相等的位，记为 Li，

2.2)从Ln位到L1位寻找源节点中第一个不为00的位，记为Lj，

2.3)从源节点依次向上寻找父节点，寻找父节点的次数记为m，m通过 公式(1)获得：

m＝i-j+1(1)

2.4)从步骤2.3)中寻找到的最高级的父节点开始，根据目标节点的 Li至Ln位逐一向下选择传输路径，Li至Ln中的任一个记为Lb，当Lb为10时， 向下层的左节点传输，当Lb为11时，向下层的右节点传输，当Lb为00时， 数据传输完成；

3)当源节点和目标节点的L值相同时，源节点和目标节点在同一局部网络 的二维Mesh结构上，根据XY路由算法，确定源节点和目标节点的传输路径， 当源节点和目标节点的L值不同时，源节点和目标节点在不同局部网络的二维 Mesh结构上，根据XY路由算法，确定源/目标节点到源/目标节点所在局部网络 的中心节点的传输路径，采用步骤2)所述的二叉树算法确定二叉树结构上与源 节点所在局部网络连接的网络节点到二叉树结构上与目标节点所在局部网络连 接的网络节点的传输路径，数据沿确定的传输路径从源节点传输至目标节点；

4)采用步骤2)所述的二叉树算法确定源节点到全局网络的二叉树结构上 与目标节点所在局部网络连接的网络节点的传输路径，根据XY路由算法，确定 局部网络的中心节点到目标节点的传输路径，数据沿确定的传输路径从源节点 传输至目标节点；

5)根据XY路由算法，确定源节点到局部网络的中心节点的传输路径，采 用步骤2)所述的二叉树算法确定目标节点到全局网络的二叉树结构上与源节点 所在局部网络连接的网络节点的传输路径，数据沿确定的传输路径从源节点传 输至目标节点。

本发明的有益效果是，本发明中全局网络采用二叉树结构和局部网络采用二 维Mesh结构，并设计了匹配的网络节点编码方法和混合路由算法，从而能够平 衡局部和全局之间的数据流量，能够减少局部节点之间的路径平均距离，减少 网络直径，从而提高网络的平均传输延迟和网络数据吞吐量，同时还有效的节 省了连线资源，在相同的连线资源的基础上，能够加入的网络节点数更多。

附图说明

下面结合附图和实施例对本发明进一步说明。

图1是本发明一种用于片上网络的混合互连结构的一实施例的结构示意图。

图2是图1中相关网络节点的地址编码表。

具体实施方式

现在结合附图对本发明作进一步详细的说明。这些附图均为简化的示意图， 仅以示意方式说明本发明的基本结构，因此其仅显示与本发明有关的构成。

本发明的具体实施例如图1所示，本发明所述的一种用于片上网络的混合 互连结构，包括全局网络和多个局部网络。所述全局网络为由多个网络节点组 成的二叉树结构，所述局部网络为由多个网络节点组成的二维Mesh结构，局部 网络的中心节点与所述全局网络上的网络节点相连。所述二维Mesh结构呈N×N 的正方形结构，其中N为正方形边的网络节点数，当N为偶数时，中心节点为 二维Mesh结构在中心处形成的正方形的四个端部的网络节点；当N为奇数时， 中心节点为二维Mesh结构在中心处的网络节点。这种合互连结构可以减少在二 维网络上的平均寻址路径。

本实施例中采用四层的二叉树结构作为全局网络，另外选取全局网络上的 两个网络节点分别挂接一个局部网络构成片上网络的混合互连结构。对图1中 的部分网络节点进行编号，网络节点D为二叉树结构的第一层的网络节点，在 第四层的网络节点G上挂接一个4×4的二维Mesh结构，其中心处的正方形具 有四个中心节点，分别为右上角中心节点A、左上角中心节点H、右下角中心节 点Z和左下角中心节点Y。所述四个中心节点分别与网络节点G连接。在二叉树 结构的第三层的一网络节点N上挂接一个5×5的二维Mesh结构，其中心节点Q 与网络节点N相连。

针对上述的片上网络的混合互连结构，采用一种用于片上网络的混合互连 结构的网络节点编码方法。全局网络的网络节点是根据二叉树结构的分层层次 性，采用二级编址的方式。这种编址方式采用类赫夫曼编码的方式.对赫夫曼编 码进行了改进,,为了使结构中的任意节点都有等长的地址,分别用2位二进制 位表示路由节点的地址。局部网络的网络节点采用XY坐标编址方法。具体编 码方法如下：所述网络节点的地址编码为(L,X,Y,Q),其中L＝L1_L2…_Lk…_Ln,n 为二叉树结构的层数，1＜k≤n，X和Y为用XY坐标编码方式以局部网络的中心 节点为坐标原点获得的坐标值，Q值为用于表示所述网络节点是在二叉树结构上 还是局部网络的坐标原点的值，

当所述网络节点为二叉树结构上第1层的节点时，L1＝L2＝…＝Lk＝…＝Ln＝00， X＝Y＝0；

当所述网络节点为二叉树结构上第k层的节点时，L1＝L(k+1)＝…＝Ln＝00， X＝Y＝0，L2至Lk中的任一个记为La，La值根据第k层节点在a层的父节点的位 置确定，当在a层的父节点为a层的左节点，La＝10，当在a层的父节点为a层 的右节点，La＝11；

当所述网络节点为N×N的二维Mesh结构上的网络节点时，L值等于二叉树 结构上与该网络节点所在局部网络连接的网络节点的L值， X＝X₀_Xoffset,Y＝Y₀_Yoffset,其中，X₀和Y₀分别为表示所述网络节点相对于坐标 原点方向的值，Xoffset和Yoffset分别为所述网络节点相对坐标原点的在X方 向和在Y方向的偏移量。

当N为偶数时，选择二维Mesh结构在中心处形成的正方形的四个端部中的 一个网络节点为坐标原点，本实施例中4×4的二维Mesh结构的局部网络中选 择右上角中心节点A为坐标原点；当N为奇数时，选择二维Mesh结构在中心处 的网络节点为坐标原点，本实施例中5×5的二维Mesh结构的局部网络选择中 心节点Q为坐标原点。向右方向为X轴正向，X₀＝0，向左方向为X轴负向，X₀＝1； 向上方向为Y轴正向，Y₀＝0，向下方向为Y轴负向，Y₀＝1.

当所述网络节点在二叉树结构上时，Q＝1；当所述网络节点在二维Mesh结 构上且为坐标原点时，Q＝0；当所述网络节点在二维Mesh结构上且不是坐标原 点时，Q为无效值。

根据上述的网络节点的编码方法，对图1中的部分节点编码如图2所示， 其中Q为x表示在这种情况下此位无效。

针对上述的片上网络的混合互连结构，采用一种用于片上网络的混合互连 结构的混合路由算法，当数据在片上网络的网络节点之间进行传输通信时，数 据输入的网络节点为源节点，数据输出的网络节点为目标节点，通过二叉树算 法和/或XY路由算法确定数据从源节点传输到目标节点的传输路径，当源节点 和目标节点在全局网络的二叉树结构上时，采用二叉树算法确定数据的传输路 径；当源节点和目标节点在同一局部网络的二维Mesh结构上时，采用XY路由 算法确定数据的传输路径；当源节点和目标节点两个网络节点中的一个在全局 网络的二叉树结构上，另一个在局部网络的二维Mesh结构上时，采用二叉树算 法确定在二叉树结构上的网络节点至二叉树结构上与对应局部网络连接的网络 节点的传输路径，采用XY路由算法确定在二维Mesh结构上的网络节点到中心 节点的传输路径；当源节点和目标节点在不同局部网络的二维Mesh结构上时， 采用XY路由算法确定源/目标节点到源/目标节点所在局部网络的中心节点的传 输路径，采用二叉树算法确定二叉树结构上与源节点所在局部网络连接的网络 节点到二叉树结构上与目标节点所在局部网络连接的网络节点的传输路径。

具体的，根据上述的网络节点编码方法，确定数据从源节点传输到目标节 点的传输路径并根据传输路径进行数据的传输，具体包括如下步骤：

1)根据源节点和目标节点的地址编码中X、Y和Q的值判断源节点和目标 节点的位置，按照二叉树算法和/或XY路由算法确定传输路径，当网络节点的X 和Y的值为零且Q＝1时，所述网络节点在全局网络的二叉树结构上，如图1中 的D、E、M、F、N、G，当网络节点的X和Y的值为零且Q＝0时，所述网络节点 为局部网络的二维Mesh结构上的坐标原点，如图1中的A和Q,当网络节点的X 和Y的值不都为零，所述网络节点为在局部网络的二维Mesh结构上的非坐标原 点，如图1中的B、C、H、Y、Z、J。

当源节点和目标节点均在全局网络的二叉树结构上，转到步骤2)，当源节 点和目标节点均在局部网络的二维Mesh结构上，转到步骤3)，当源节点在全 局网络的二叉树结构上，目标节点在局部网络的二维Mesh结构上转到步骤4)， 当源节点在局部网络的二维Mesh结构上，目标节点在全局网络的二叉树结构上 转到步骤5)；

2)采用二叉树算法确定传输路径，即将源节点与目标节点的地址编码中的 L进行对比，确定传输路径，数据沿确定的传输路径从源节点传输至目标节点， 具体为：

2.1)从L1位到Ln位寻找源节点与目标节点第一个不相等的位，记为 Li，

2.2)从Ln位到L1位寻找源节点中第一个不为00的位，记为Lj，

2.3)从源节点依次向上寻找父节点，寻找父节点的次数记为m，m通过 公式(1)获得：

m＝i-j+1(1)

2.4)从步骤2.3)中寻找到的最高级的父节点开始，根据目标节点的 Li至Ln位逐一向下选择传输路径，Li至Ln中的任一个记为Lb，当Lb为10时， 向下层的左节点传输，当Lb为11时，向下层的右节点传输，当Lb为00时， 数据传输完成。

3)当源节点和目标节点的L值相同时，源节点和目标节点在同一局部网络 的二维Mesh结构上，根据XY路由算法，确定源节点和目标节点的传输路径。

当源节点和目标节点的L值不同时，源节点和目标节点在不同局部网络的 二维Mesh结构上。根据XY路由算法，确定源/目标节点到源/目标节点所在局 部网络的中心节点的传输路径。具体的，当源/目标节点为二维Mesh结构上的 坐标原点，直接通过源/目标节点与相连的二叉树结构上的网络节点传输数据即 可。当源/目标节点不是二维Mesh结构上的坐标原点，N为奇数时，通过XY路 由算法确定源/目标节点至中心节点的传输路径，N为偶数时，通过XY路由算法 确定源/目标节点至最接近的中心节点的传输路径。具体的，若源/目标节点位 于网络坐标零点的东北，正北，正东方向，则执行源节点到最中间正方形右上 角节点如图1中的A的XY路由算法，若源/目标节点位于网络坐标零点的西北， 正西方向，则执行源节点到最中间正方形左上角节点如图1中的H的XY路由 算法，若源/目标节点位于网络坐标零点的西南方向，则执行源节点到最中间正 方形左下角节点如图1中的Y的XY路由算法，若源/目标节点位于网络坐标零 点的正南，东南方向，则执行源节点到最中间正方形右下角节点如图1中的Z 的XY路由算法。然后采用步骤2)所述的二叉树算法确定二叉树结构上与源节 点所在局部网络连接的网络节点到二叉树结构上与目标节点所在局部网络连接 的网络节点的传输路径，数据沿确定的传输路径从源节点传输至目标节点。

4)采用步骤2)所述的二叉树算法确定源节点到全局网络的二叉树结构上 与目标节点所在局部网络连接的网络节点的传输路径，根据XY路由算法，确定 局部网络的中心节点到目标节点的传输路径，数据沿确定的传输路径从源节点 传输至目标节点。

5)根据XY路由算法，确定源节点到局部网络的中心节点的传输路径，采 用步骤2)所述的二叉树算法确定目标节点到全局网络的二叉树结构上与源节点 所在局部网络连接的网络节点的传输路径，数据沿确定的传输路径从源节点传 输至目标节点。

上述的在二维Mesh结构上进行传输路径的选择时，采用的XY路由算法具 体的如下所述：二维Mesh结构上网络节点的坐标X＝X₀_Xoffset,Y＝Y₀_Yoffset。 其中，Xoffset和Yoffset的值用二位二进制的方式表示，源节点与目标节点之 间相对于X轴的偏移量的计算方法如下:：

1.当两个网络节点的X₀相同时，两个网络节点相对于X轴的偏移量的值为目标节 点的Xoffset减去源节点的Xoffset，符号与目标节点的X₀一致。

2.当两个网络节点的X₀不同时，两个网络节点相对于X轴的偏移量的值为目标节 点的Xoffset加上源节点的Xoffset，符号与目标节点的X₀一致。

源节点与目标节点之间相对于X轴的偏移量的计算方法与上述类似，此处 不再赘述。

根据图1和图2所示，下面将具体描述几个具体的网络节点的数据传输路径的 确定。

实施例一：

当网络节点B与网络节点C通信，网络节点B为源节点，网络节点C为目标 节点，判断网络节点B，网络节点C都为二维mesh结构上的网络节点，且为同 一二维mesh网络上的网络节点，则执行XY路由算法，网络节点B的XY坐标 为(110，101)，网络节点C点的XY坐标为(001，110)，根据偏移量的计 算方法，可得Xoffset＝011，Yoffset＝101，换算为十进制Xoffset为+3，Yoffset 为-1。所以沿X轴正向走三步，再沿Y轴负向走一步，即从网络节点B到达网 络节点C。

实施例二：

网络节点G与网络节点N通信，网络节点G为源节点，网络节点N为目标 节点，判断网络节点G，网络节点N都为全局网络的二叉树结构上的节点，则 直接执行二叉树路由算法，过程如下，网络节点G点二叉树编码为00_10_10_11, 网络节点N点二叉树编码为00_11_10_00,发现从左向右第一次不相等的位段为 L2，然后找到源节点G从右向左第一次不为00的位段为L，，计算 m＝i-j+1＝4-2+1＝3,即要进行3次向上寻找父节点，到达第一个分叉的节点D。 然后以网络节点D为起点，从目标节点N的L2位开始依次向右根据图2进行 判断，目标节点N的L2位为11，路由到网络节点D的右子节点M，然后判断 目标节点N的L3位为10，路由到M的左子节点N，然后判断目标节点N的 L4位为00，停止路由，网络节点N就是我们的目标节点。此方法也适用于图1 中网络节点A、G与网络节点N、Q之间的路由，只要增加网络节点A与网络 节点G，网络节点N与网络节点Q之间的连接即可。

实施例三：

网络节点B与网络节点J通信，网络节点B为源节点，网络节点J为目标节 点，根据节点位置判断方法可知网络节点B与网络节点J位于不同的二维mesh 网络上，则先执行网络节点B到二叉树结构上的网络节点G的路由算法，网络 节点B先路由到网络节点Y，参照实施例一可知，沿X正向走一次即可到达网 络节点Y。然后网络节点Y直接路由到网络节点G，然后进行网络节点G到网 络节点N点的路由，参照实施例二。从网络节点G路由到网络节点N后，再进 行网络节点N到对应网络节点Q的直接路由，然后执行网络节点Q点到网络节 点J的路由，参照实施例一，可知先沿X正向走两次，再沿Y负向走一次，即 可到达网络节点J，至此，路由完成。

本发明所述的一种用于片上网络的混合互连结构能够平衡局部和全局之间 的数据流量，能够减少局部节点之间的路径平均距离，减少网络直径，从而提 高网络的平均传输延迟和网络数据吞吐量，同时还有效的节省了连线资源，在 相同的连线资源的基础上，能够加入的网络节点数更多。

以上述依据本发明的理想实施例为启示，通过上述的说明内容，相关工作 人员完全可以在不偏离本项发明技术思想的范围内，进行多样的变更以及修改。 本项发明的技术性范围并不局限于说明书上的内容，必须要根据权利要求范围 来确定其技术性范围。