一种用于片上网络的混合互连Mesh拓扑结构及其路由算法

摘要

本发明一种用于片上网络的混合互连Mesh拓扑结构及其路由算法，对数据包预设路径条件；当前路由节点先根据预设的路径，判断下一级路由节点的输入端口缓冲区中的数据是否超过预设比例值，若不超过，则仍然沿着预先选定的路径传输；若超过且满足最小路径要求的两个相邻的路由节点对应输入端口中缓冲区数据存储量都不满，则选择对应输入端口的缓冲区数据包较少的路由节点作为下一级路由节点；若对应输入端口中缓冲区均满，则选择通过共享总线进行传输。由于本发明HPA路由算法在网络拥塞时可以通过总线进行传输，不会发生死锁现象；由于路由算法属于最小路径算法，因此不存在活锁现象；且所有节点的数据包在传输过程中都是等地位的，不会产生饿死现象。

说明书

技术领域

本发明涉及一种用于片上网络的混合互连Mesh拓扑结构及其路 由算法。

背景技术

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

片上网络设计中常用的几种规则型拓扑结构如下所示：

1、二维网格结构(2D Mesh)

二维网格结构是一种规则型结构，是片上网络研究过程中最常 用、最简单直观的拓扑结构，如图1所示。在一个N×N的2DMesh结 构中，每个IP核通过网络接口与路由节点相连，每个路由节点(边 界节点除外)与其上、下、左、右方向的四个路由节点相连，节点的 度为4，网络直径为2×(N-1)。

Mesh结构具有可扩展性好、规则性、逻辑结构简单、便于实现 和分析等优点，因此在片上网络中得到广泛应用。这种结构设计的缺 点是：对称性易引起中央区域拥塞和热点，造成网络负载分布不均衡； 其边缘节点相对闭塞，远端节点间长距离多跳通信易造成延迟过大； 带宽、延迟等方面的性能不是最优；对于实时性数据传输要求较高的 网络，在这样情况下将无法保证服务质量(Quality of Service，QoS)。

2、二维环绕网格结构(2D Torus)

如图2所示，二维Torus结构将每行每列中处于边缘的路由节点 对应连接起来，使整个网络中的路由节点形成一个环路。通过增加通 信链路来降低网络阻塞的概率，从而克服了上述2D Mesh结构的设计 缺陷。该结构的所有节点度均为4，直径为(取整)。

与2D Mesh结构相比，虽然直径有所减小，但却增加了环路，这 种过长的环形信道可能会产生额外的延迟。因此，研究人员设计出了 Folded Torus结构，如图3所示,通过链路改进使0与3之间的长链 路被短链路取代，如图4所示，使整个网络成球状分布。但是，这两 种拓扑结构的路由节点都会形成环路，增加了路由死锁发生的可能 性，而且环路之间存在交叉，增加了硬件实现的资源损耗。

传统Mesh拓扑结构虽然具有良好的可扩展性、规则性、结构简 单且便于实现等优点，但是，由于结构的对称性以及边缘节点相对闭 塞，传统Mesh结构容易引起负载分布不均衡和中央区域热点的形成， 从而导致网络拥塞和通信性能下降。

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

确定性路由又称为静态路由，是片上网络中一种常见的路由算 法。在确定性路由算法中，传输路径是由源节点和目的节点共同决定， 与网络当前的状态无关，即每对通信节点只有唯一一条通信路径。常 用的确定性路由主要有维序XY路由(Dimensional Ordered Routing， DOR)和O1TURN(Only one Turn)等。如图5所示，源节点为A，目 的节点为B，在XY路由算法中，数据包先沿着X轴到达C(往目的节 点的方向)，然后转向Y轴路由，最后到达B。在O1TURN路由算法中， 数据包有50％概率选择XY路由(A→C→B)，也有50％的概率选择YX路 由(A→D→B)传输。确定性路由的主要优点是：算法简单、易于实现， 在网络拥塞相对低时延迟较小。目前，工业界的很多产品路由设计都 采用确定性路由，然而，由于确定性路由算法路径只与源节点和目的 节点有关，路径单一，不能根据网络中的流量分布来合理利用网络资 源。容易造成网络负载分布不均衡，且易引起热点和网络拥塞，若网 络处于非均匀的数据流量分布时，采用该算法的系统性能将急速下 降。

自适应路由算法能根据网络中流量的分布动态改变路由路径传 输。数据包从源节点到目的节点的路径有多种选择，路径不仅与源节 点和目的节点地址有关，而且与整个网络的实时通信状态有关。当网 络中存在故障或拥塞节点时，数据包能自动绕开该节点，沿其它路径 传输到目的节点。而且，该算法能自动避开网络热点，使负载在网络 中均匀分布，能实现充分利用网络资源来提高系统的整体性能。常见 的有奇偶转向路由(Odd-Even)和自适应维序路由(DyXY)等。在奇 偶转向路由中，经过奇数列节点的数据包均不能由北向西转向，数据 包经过偶数列节点时均不能由东向北转向，属于部分自适应路由。在 DyXY路由中，当数据包与目的节点在相同X维(或Y维)时，则沿 另一维传输至目的节点；否则，数据包将选择往目的节点方向量化负 载最小的路径传输，属于完全自适应路由。虽然自适应性路由算法能 较好地缓解网络拥塞状况，达到均衡网络中各节点的负载和提高网络 整体性能的目的。但是，由于自适应性路由算法在实现过程中需要实 时监控、计算、反馈、决策，因此实现复杂度较高。此外，由于路由 路径是不确定，自适应路由算法可能存在死锁问题。

确定性与自适应性相结合的路由算法，将确定性路由算法和自适 应路由算法相结合，因此，既具备确定性路由的结构实现简单且不会 产生死锁的优点，也具备了适应性路由的根据网络的实时流量分布情 况选择路径传输的优点。目前，常见的确定性与适应性相结合的路由 算法主要有伪自适应奇偶转向路由(DyAd)和伪自适应XY路由等。 DyAd路由算法是在低负载时选用XY路由，在网络拥塞较为严重时选 用奇偶转向的路由算法。伪自适应XY路由算法是在网络无拥塞或拥 塞较低时，采用确定性路由，而在网络拥塞时采用适应性路由，动态 选择量化负载最低的相邻节点作为下一级路由节点。

片上网络主要部件包括网络接口单元和路由节点。其中网络接口 单元主要包括打包控制器、打包器、解包控制器、解包器、链路控制 器和缓冲区六个模块，如图6所示，其主要功能是实现IP核与路由 节点之间的数据格式的转换。具体来说，网络接口单元将IP核发送 过来的数据进行打包，然后通过缓冲区缓冲后在路由节点准备好时发 送给路由节点。此外，网络接口单元接收来自路由节点的数据包，对 数据包进行解包后将有效数据发送给IP核。其中路由节点主要由输 入和输出端口模块、交换开关、开关分配器以及路由单元等模块构成， 如图7所示。路由节点主要实现数据包的存储转发、路由计算、路径 判断选择等功能。为了使网络资源得到合理分配，路由缓存采用了先 进先出缓冲区(First In First Out，FIFO)。路由节点的端口数由 拓扑结构确定，比如，在传统的2D Mesh结构中，路由节点一般包含 东、南、西、北以及本地5个输入输出端口，每个端口对应一个缓存 队列。该输入端口模块用来处理来自上一级路由节点的数据包传输申 请，并为数据包分配缓存资源、解析数据包和申请路由的计算。该输 出端口模块是用来接收本级路由节点中数据包的发送请求，并向下一 级路由节点传输数据。端口通道中包含了路由节点的缓冲区，用于存 储数据分组。该交换开关(Switch)主要负责的是将路由中输入通道 连接到目标输出通道。该开关分配器(Switch Allocator)作为仲裁 逻辑，负责将输出通道分配给对应的输入通道。在本发明中，开关分 配器的资源分配策略采用的是轮询算法。该路由单元(Routing Unit) 主要是实现路由算法，为输入的数据选择输出通道。在多个数据包选 择同一个输出端口情况下，可通过仲裁模块来决定哪个数据包优先传 输。如果请求的通道正忙，则将输入数据暂时保存在输入缓存，当通 道处理完，且输入数据通过仲裁成功，则可以通过该通道进行传输。

发明内容

针对传统Mesh拓扑结构设计缺陷，本发明提出了一种用于片上 网络的混合互连Mesh拓扑结构，能减少网络中因负载分布不均衡引 起的网络热点和拥塞。

基于混合互连Mesh拓扑结构，本发明的另一目的在于提出了一 种混合伪自适应性(Hybrid Pseudo Adaptive，HPA)路由算法，可 以避免死锁、活锁现象，也不会产生饿死现象。

本发明一种用于片上网络的混合互连Mesh拓扑结构，在传统 Mesh拓扑结构基础上添加了一条缓解网络拥塞和热点形成的共享总 线，当Mesh网络不拥塞时，数据包是通过Mesh拓扑结构进行传输； 当Mesh网络较为拥塞时，则通过共享总线传输，每个路由节点对应 增加一对输入输出端口和总线接口，路由节点通过总线接口与共享总 线相连，在上级路由节点输出端口和下级路由节点输入端口之间增加 两比特信号线，用于标识下级路由节点输入端口缓冲区的状态。

一种用于片上网络的混合互连Mesh拓扑结构的混合伪自适应路 由算法，当数据包注入网络时，对数据包预设分别采用XY路由算法 或YX路由算法的路径条件；当数据包到达路由节点时，当前路由节 点先根据预设的路径，判断下一级路由节点的输入端口缓冲区中的数 据是否超过其容量的预设比例值，若不超过，则仍然沿着预先选定的 路径传输；若超过且满足最小路径要求的两个相邻的路由节点对应输 入端口中缓冲区数据存储量都不满，则需要在满足最小路径要求的两 个相邻路由节点中选择对应输入端口的缓冲区数据包较少的路由节 点作为下一级路由节点；若满足最小路径要求的两个相邻的路由节点 对应输入端口中缓冲区均满，则选择通过共享总线进行传输。

具体包括如下步骤：

步骤1、当数据包注入网络时，对数据包预设分别采用XY路由 算法或YX路由算法的路径条件；

步骤2、当数据包到达路由节点时，解析当前路由节点缓存中第 一个数据包的目的地址(dest_x，dest_y)和预设路径标识XY_router， 并判断当前节点地址(co_x，co_y)是否为目的节点，如果是，转到 步骤7；否则转到下一步；

步骤3、根据预设路径标识XY_router，求出预设路由路径的下 一级路由节点“A”的地址(next_x_1，next_y_1)，具体为：

(1)当路径标识XY_router表示数据包选择XY路由路径，则下 一级路由节点地址(next_x_1，next_y_1)可以通过公式(3.1)和 (3.2)计算得到：

next_x_1＝co_x+[u(k)-u(-k)]    (0.1)

next_y_1＝co_y+[u(t)-u(-t)]×|[u(k)-u(-k)]-1|   (0.2)

其中，k＝dest_x-co_x，t＝dext_y-co_y，是一 个单位阶跃函数；

(2)当路径标识XY_router表示数据包选择YX路由路径，则下 一级路由节点地址(next_x_1，next_y_1)可以通过公式(3.3)和 (3.4)计算得到：

next_x_1＝co_x+[u(k)-u(-k)]×|[u(t)-u(-t)]-1|  (0.3)

next_y_1＝co_y+[u(t)-u(-t)]    (0.4)

判断预设路由路径的下一级路由节点“A”相应输入端口缓冲区 的数据是否超过其容量的预置比例值，若不超过，则仍然沿着预先选 定的路径传输，将数据包发送至节点“A”，并转到步骤2；否则转到 下一步；

步骤4：计算满足最小路径传输要求的另一条路由路径的下一级 路由节点“B”的地址(next_x_2，next_y_2)，可以通过公式(3.5)、 (3.6)计算得到：

next_x_2＝co_x+[u(k)-u(-k)]×|next_y_1-co_y|   (0.5)

next_y_2＝co_y+[u(t)-u(-t)]×|next_x_1-co_x|    (0.6)

判断节点“A”和节点“B”的相应输入端口缓冲区是否均为满， 如果是，则转到步骤6，否则转到下一步；

步骤5：判断节点“A”相应输入端口缓冲区的数据存储量是否 大于节点“B”相应输入端口缓冲区的数据存储量，如果是，则将数 据包传给节点“B”，否则传给节点“A”，转到步骤2；

步骤6：当前路由节点将数据包通过共享总线传输至目的节点；

步骤7：目的节点接收数据包后本地缓存，并转到步骤8；

步骤8：返回步骤1，当前路由节点处理下一个数据包，直至当 前路由节点缓存中的所有数据包发送完毕。

本发明在传统Mesh结构基础上添加了一条缓解网络拥塞和热点 形成的互连总线，当Mesh网络不拥塞时，数据包是通过Mesh拓扑结 构进行传输；当Mesh网络较为拥塞时，则通过互连总线传输，能减 少网络中因负载分布不均衡引起的网络热点和拥塞；由于本发明HPA 路由算法在网络拥塞时可以通过总线进行传输，不会出现死锁环，因 此，不会发生死锁现象；由于HPA路由算法本质上属于最小路径算法， 因此不存在活锁现象；由于在HPA路由算法中，所有节点的数据包在 传输过程中都是等地位的，因此不会产生饿死现象。

附图说明

图1是传统的二维4*4网格拓扑结构示意图；

图2是传统的二维环绕网格拓扑结构示意图；

图3是Folded Torus拓扑结构示意图；

图4是对2D-Torus链路的改进图；

图5是传统的XY和O1TURN路由算法示意图；

图6为网络接口单元的工作原理示意图；

图7为路由节点结构示意图；

图8为本发明混合互连Mesh拓扑结构示意图；

图9为本发明中路由节点与共享总线互连结构示意图；

图10为本发明中路由节点数据包传输的整个工作流程示意图。

以下结合附图和具体实施例对本发明作进一步详述。

具体实施方式

如图8所示，本发明一种用于片上网络的混合互连Mesh拓扑结 构，在传统Mesh拓扑结构基础上添加了一条缓解网络拥塞和热点形 成的共享总线，当Mesh网络不拥塞时，数据包是通过Mesh拓扑结构 进行传输；当Mesh网络较为拥塞时，则通过共享总线传输，每个路 由节点对应增加一对输入输出端口(B_i和B_o)和总线接口，路由 节点通过总线接口与共享总线相连，如图9所示，在上级路由节点输 出端口和下级路由节点输入端口之间增加两比特信号线，用于标识下 级路由节点输入端口缓冲区的状态。

该共享总线只有在网络拥塞时才使用，也就是说，只有一部分通 信业务通过共享总线进行传输。因此，本发明的混合互连Mesh拓扑 结构对总线的带宽要求不高，使得共享总线可以工作在较低的频率， 大大的降低了总线的实现难度。

基于混合互连Mesh拓扑结构，本发明提出了一种混合伪自适应 路由算法，该算法属于伪自适应路由，将确定性路由和适应性路由相 结合，基本工作过程如下：当数据包注入网络时，对数据包预设分别 采用XY路由算法或YX路由算法的路径条件；当数据包到达路由节点 时，当前路由节点先根据预设的路径，判断下一级路由节点的输入端 口缓冲区中的数据是否超过其容量的预设比例值，若不超过，则仍然 沿着预先选定的路径传输；若超过且满足最小路径要求的两个相邻的 路由节点对应输入端口中缓冲区数据存储量都不满，则需要在满足最 小路径要求的两个相邻路由节点中选择对应输入端口的缓冲区数据 包较少的路由节点作为下一级路由节点；若满足最小路径要求的两个 相邻的路由节点对应输入端口中缓冲区均满，则选择通过共享总线进 行传输。

本发明采用二维坐标形式表示每个路由节点的地址，当前节点地 址用(co_x，co_y)表示，源节点地址用(sor_x，sor_y)表示，目 的节点地址用(dest_x，dest_y)表示，预设路由路径的下一级路由 节点为节点A，地址为(next_x_1，next_y_1)；满足最小路径要求 的另一条路由路径的下一级路由节点为节点B，地址为(next_x_2， next_y_2)。

如图10所示，本发明一种用于片上网络的混合互连Mesh拓扑结 构的混合伪自适应路由算法，具体包括如下步骤：

步骤1、当数据包注入网络时，对数据包预设分别采用XY路由 算法或YX路由算法的路径条件；

步骤2、当数据包到达路由节点时，解析当前路由节点缓存中第 一个数据包的目的地址(dest_x，dest_y)和预设路径标识XY_router， 并判断当前节点地址(co_x，co_y)是否为目的节点，如果是，转到 步骤7；否则转到下一步；

步骤3、根据预设路径标识XY_router，求出预设路由路径的下 一级路由节点“A”的地址(next_x_1，next_y_1)，具体为：

(1)当路径标识XY_router表示数据包选择XY路由路径，则下 一级路由节点地址(next_x_1，next_y_1)可以通过公式(3.1)和 (3.2)计算得到：

next_x_1＝co_x+[u(k)-u(-k)]      (0.7)

next_y_1＝co_y+[u(t)-u(-t)]×|[u(k)-u(-k)]-1|     (0.8)

其中，k＝dest_x-co_x，t＝dext_y-co_y，是一 个单位阶跃函数；

(2)当路径标识XY_router表示数据包选择YX路由路径，则下 一级路由节点地址(next_x_1，next_y_1)可以通过公式(3.3)和 (3.4)计算得到：

next_x_1＝co_x+[u(k)-u(-k)]×|[u(t)-u(-t)]-1|    (0.9)

next_y_1＝co_y+[u(t)-u(-t)]       (0.10)

判断预设路由路径的下一级路由节点“A”相应输入端口缓冲区 的数据是否超过其容量的预置比例值，若不超过，则仍然沿着预先选 定的路径传输，将数据包发送至节点“A”，并转到步骤2；否则转到 下一步；

步骤4：计算满足最小路径传输要求的另一条路由路径的下一级 路由节点“B”的地址(next_x_2，next_y_2)，可以通过公式(3.5)、 (3.6)计算得到：

next_x_2＝co_x+[u(k)-u(-k)]×|next_y_1-co_y|   (0.11)

next_y_2＝co_y+[u(t)-u(-t)]×|next_x_1-co_x|   (0.12)

判断节点“A”和节点“B”的相应输入端口缓冲区是否均为满， 如果是，则转到步骤6，否则转到下一步；

步骤5：判断节点“A”相应输入端口缓冲区的数据存储量是否 大于节点“B”相应输入端口缓冲区的数据存储量，如果是，则将数 据包传给节点“B”，否则传给节点“A”，转到步骤2；

步骤6：当前路由节点将数据包通过共享总线传输至目的节点；

步骤7：目的节点接收数据包后本地缓存，并转到步骤8；

步骤8：返回步骤1，当前路由节点处理下一个数据包，直至当 前路由节点缓存中的所有数据包发送完毕。

以上所述，仅是本发明较佳实施例而已，并非对本发明的技术范 围作任何限制，故凡是依据本发明的技术实质对以上实施例所作的任 何细微修改、等同变化与修饰，均仍属于本发明技术方案的范围内。