一种基于MoT结构的低功耗NoC路由方法

摘要

本发明涉及一种基于MoT（mesh-of-tree，网状树）结构的低功耗NoC（Network-on-chip，片上网络）路由方法，包括针对叶子层路由器的自适应路由方法和针对树干路由器的路由方法。本发明所述的路由方法在每个flit进行路径选择时，通过计算每个临近路由器的拥塞系数，选择位于最短路径上拥塞系数较低的路由器进行转发，既能保证核间通信时的最短路径，又会减少网络中非自适应算法产生的拥塞现象。本发明同时采用了一种简化的地址模式以减小路由器的缓存中flit的大小。从而在运行同一个应用时，使用较小的缓存存储flit，在满足性能的基础上达到降低功耗的目的。

主权项

1.一种基于MoT结构的低功耗NoC路由方法，其特征在于，在每个flit进行路径选择时，通过计算每个临近路由器的拥塞系数，选择位于最短路径上拥塞系数较低的路由器进行转发，以保证核间通信时的最短路径，减少网络中非自适应算法产生的拥塞现象；所述方法包括针对叶子层路由器的自适应路由方法和针对树干路由器的路由方法；其中，针对叶子层路由器的自适应路由方法包括以下步骤；步骤1，路由器接收flit，将该flit存储在相应输入端口的buffer中；步骤2，计算最优的输出端口；步骤2.1，计算数据包从当前节点到达目的节点所经过的Row_Router个数Δx和所经过的Col_Router个数Δy；步骤2.2，若Δx≠0，且Δy≠0，即源节点与目的节点位于不同的行和列上，选择某一邻居路由器作为flit的下一跳，方法如下：（1）计算数据包从源节点到达目的节点的最短路径的数目P_algorithm；在MoT结构中，P_algorithm=2；（2）计算在每个叶子节点L，一个flit转发到每一个邻居路由器Row_Router或Col_Router的概率P₁和P₂，公式如下：$P_2=\frac{\mathrm{\Delta y}+P_{\mathrm{algorithm}}}{\mathrm{\Delta x}+\mathrm{\Delta y}+{2P}_{\mathrm{algorithm}}}$（3）计算除flit转发来的路由器外的每一个邻居路由器的拥塞系数，公式如下：${\mathrm{Con}}_i=P_i\times \frac{\mathrm{Buf}\_{\mathrm{SIZE}}_{\mathrm{out}1}+\mathrm{Buf}\_{\mathrm{SIZE}}_{\mathrm{out}2}}{2}$式中，Con_i为第i个叶子节点邻居路由器的拥塞系数，P_i为第i个叶子节点邻居路由器一个flit转发到Row_Router或Col_Router的概率，i=1,2；Buf_SIZE_out1和Buf_SIZE_out2分别为行或列方向输出端口和下一个可能输出端口的可用buffer数；（4）选择拥塞系数Con_i最低的邻居路由器作为flit的下一跳，确定相应的输出端口；步骤2.3，若Δx=0，且Δy≠0，即源节点与目的节点在同一行上，选择Row_Router作为flit的下一跳，确定相应的输出端口；步骤2.4，若Δx≠0，且Δy=0，即源节点与目的节点在同一列上，选择Col_Router作为flit的下一跳，确定相应的输出端口；步骤2.5，若Δx=0，且Δy=0，即源节点与目的节点连接在同一路由器上，当Core_id=0时，发送flit至L_Core；当Core_id=1时，发送flit至R_Core；步骤2.6，如果两个或者更多的flit想要经过同一个输出端口转发出去，则优先权高的即跳数更多的flit优先转发出去；步骤3，将flit从选择的输出端口转发给相应的路由器；针对树干路由器的路由方法包括以下步骤：步骤1，路由器接收flit，将该flit存储在相应输入端口的buffer中；步骤2，选择输出端口；步骤2.1，计算目的地址Des_ADDR的l层组地址Gro_ADDR，N为一个MoT结构中的列数，公式如下：$\mathrm{Gro}\_\mathrm{ADDR}=\left\{\begin{array}{c}\mathrm{return}\_\mathrm{rowaddr}(\mathrm{Des}\_\mathrm{ADDR}),\mathrm{if\; flit\; is\; in\; a\; Row}\_\mathrm{Router}\\ \mathrm{return}\_\mathrm{coladdr}(\mathrm{Des}\_\mathrm{ADDR}),\mathrm{if\; flit\; is\; in\; a\; Col}\_\mathrm{Router}\end{array}\right.$步骤2.2，判断路由器的地址Cur_ADDR与Gro_ADDR是否相同，如果相同，转下一步；否则，转步骤2.5；步骤2.3，计算目的地址Des_ADDR的l-1层组地址Up_ADDR，公式如下：Up_ADDR＝return_groupaddr(Des_ADDR,l-1)步骤2.4，若Up_ADDR=0，发送flit至L_Router；若Up_ADDR=1，发送flit至R_Router；步骤2.5，将l+1层路由器作为flit的下一跳，确定相应的输出端口；步骤3，转发flit：将flit从选择的输出端口转发到相应的路由器。