法律状态公告日
法律状态信息
法律状态
2016-09-14
授权
授权
2014-05-14
实质审查的生效 IPC(主分类):G06F15/173 申请日:20131223
实质审查的生效
2014-04-16
公开
公开
技术领域
本发明属于计算机体系结构领域,具体涉及一种基于mesh-of-tree(MoT)结构的低功耗 NoC路由方法。
背景技术
随着半导体技术的发展,越来越多的部件被集成到单一芯片上来,因此片上网络的通信 质量很大程度地影响整体的性能。片上网络NoC(Network-on-chip)作为一种可扩展的片上 结构,已经成为解决片上系统核间通信的有效方案。而NoC的拓扑结构和相应路由方法的选 择对系统的延迟、功耗等性能有至关重要的影响。
MoT结构拥有较小的直径和较低的节点度,是一种较为理想的拓扑结构。K.Manna等基 于MoT结构提出了确定性路由策略,其原理是消息在源节点路由到目的节点的过程中,根据 目的节点地址确定出一条最短路径,并按照此路径将消息传递到目的节点。此方法虽然能够 确保核间通信的最短路径,但却极易造成网络拥塞现象,增加通信延迟,从而影响系统的性 能。
发明内容
本发明提出了一种基于MoT结构的低功耗NoC路由方法,这种算法在每个flit(网络中 数据传输的基本单元)进行路径选择时,通过计算每个临近路由器的拥塞系数,选择位于最 短路径上系数较低的路由器进行转发,既能保证核间通信时的最短路径,又会减少网络中非 自适应算法产生的拥塞现象。并采用一种简化的地址模式以减小路由器的缓存中flit的大小。 从而在运行同一个应用时,使用较小的缓存存储flit,在满足性能的基础上达到降低功耗的目 的。
为达到上述目的,本发明采用以下技术方案。
本发明所述的部分适应路由方法采用的是MoT拓扑结构。在MoT中,将NoC网络中的 路由器分为三种类型:叶子层路由器(Leaf_Router),树干层路由器(Row_Router&&Col_Router) 和根路由器(Root_Router)。每个Leaf_Router连接两个IP核,并且向上连接一个Row_Router 和一个Col_Router,树干层路由器向上连接一个Root_Router。图1是一个32核的MoT拓扑 结构。
本发明采用一种简化的地址模式,例如在32核的MoT中,数据包的地址位数为5位: Core_id(IP核的ID号)1位,Col_ADDR(IP核的列地址)2位,Row_ADDR(IP核的行 地址)2位。
一种基于MoT结构的低功耗NoC路由方法,其特征在于包含以下步骤:
针对叶子层路由器的自适应路由方法如下:
步骤1,路由器接收flit,将该flit存储在相应输入端口的buffer中。
步骤2,计算最优的输出端口。
步骤2.1,计算数据包从当前节点到达目的节点所经过的Row_Router个数Δx和所经过 的Col_Router个数Δy。
步骤2.2,若Δx≠0,且Δy≠0,即源节点与目的节点位于不同的行和列上,选择某一邻居 路由器作为flit的下一跳,方法如下:
(1)计算数据包从源节点到达目的节点的最短路径的数目Palgorithm。在MoT结构中, Palgorithm=2。
(2)计算在每个叶子节点L,一个flit转发到每一个邻居路由器Row_Router或Col_Router 的概率P1和P2,公式如下:
(3)计算除flit转发来的路由器外的每一个邻居路由器的拥塞系数,公式如下:
式中,Coni为第i个叶子节点邻居路由器的拥塞系数,Pi为第i个叶子节点邻居路由器一 个flit转发到Row_Router或Col_Router的概率,i=1,2;Buf_SIZEout1和Buf_SIZEout2分别为 行或列方向输出端口和下一个可能输出端口的可用buffer数。
(4)选择拥塞系数Coni最低的邻居路由器作为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从选择的输出端口转发给相应的路由器。
针对第l层(N为一个MoT结构中的列数)树干路由器的路由方法如下:
步骤1,路由器接收flit,将该flit存储在相应输入端口的buffer中。
步骤2,选择输出端口阶段:
步骤2.1,计算目的地址Des_ADDR的l层组地址Gro_ADDR,公式如下:
步骤2.2,判断路由器的地址Cur_ADDR与Gro_ADDR是否相同,如果相同,转下一步; 否则,转步骤2.5。
步骤2.3,计算目的地址Des_ADDR的l-1层组地址Up_ADDR,公式如下:
Up_ADDR=return_groupaddr(Des_ADDR,l-1) (5)
步骤2.4,若Up_ADDR=0,发送flit至L_Router;若Up_ADDR=1,发送flit至R_Router。
步骤2.5,将l+1层路由器作为flit的下一跳,确定相应的输出端口。
步骤3,转发flit:将flit从选择的输出端口转发到相应的路由器。
与现有技术相比,本发明具有以下优点:
在源节点路由到目的节点的过程中,在可选的最短路径的范围内,比较和衡量每个临近 路由器的可用buffer数及下一个可能输入出口的可用buffer数,选择位于最短路径上较不易 产生拥塞的路由器进行转发,既能保证核间通信时的最短路径,又会减少网络中非自适应算 法产生的拥塞现象。并采用一种简化的地址模式表示网络中节点的地址,从而减小路由器的 缓存中flit的大小,在满足性能的基础上达到降低功耗的目的。
附图说明
图1为一个32核的MoT拓扑结构示意图;
图2为本发明所涉及的叶子层路由器路由方法流程图;
图3为本发明所涉及的树干层路由器路由方法流程图。
具体实施方式:
下面结合附图和实施例对本发明做进一步说明。
一个32核的MoT结构如图1所示,假设某个数据包的源地址是10000,其目的地址为 10111。本发明的方法流程图如图2和图3所示,具体步骤如下:
步骤1,Leaf_Router接收flit:core1首先将数据包转发到0000(Leaf_Router),0000 (Leaf_Router)将该flit存储在相应输入端口的buffer中。
步骤2,计算最优的输出端口。
步骤2.1,计算Δx和Δy得:Δx=1,Δy=2。
步骤2.2,Δx≠0,且Δy≠0,即源节点与目的节点位于不同的行和列上,选择某一邻居路 由器作为flit的下一跳,方法如下:
(1)计算数据包从源节点到达目的节点的最短路径的数目Palgorithm=2。
(2)根据公式(1)和(2)分别计算flit转发到每一个邻居路由器即Row_Router或
Col_Router的概率为P1和P2。计算得
(3)根据公式(3)计算Row_Router或Col_Router的拥塞系数Coni。假设Row_Router 的Buf_SIZEout1=4,Buf_SIZEout2=6,Col_Router的Buf_SIZEout1=3,Buf_SIZEout2=3, 可求得:
(4)根据Con1>Con2,选择列路由器作为flit的下一跳,确定相应的输出端口。
步骤3,转发flit:将flit从选择的输出端口转发到列路由器。
步骤4,Col_Router接收flit:将接收到的flit存储在相应输入端口的buffer中。
步骤5,选择输出端口:
步骤5.1,根据公式(4)计算目的地址Des_ADDR的组地址Gro_ADDR,这里, Gro_ADDR=1。
步骤5.2,该路由器的地址是0≠1,转下一步。
步骤5.3,将R_Router作为flit的下一跳,确定相应的输出端口。
步骤6,转发flit:将flit从选择的输出端口转发到Root_Router,Root_Router直接将flit 转发到连接在该路由器上的另一个Col_Router。
步骤7,Col_Router:接收flit:将接收到的flit存储在相应输入端口的buffer中。
步骤8,选择输出端口阶段:
步骤8.1,根据公式(4)计算目的地址Des_ADDR的组地址Gro_ADDR,这里, Gro_ADDR=1。
步骤8.2,该路由器的地址是1=1,转下一步。
步骤8.3,根据公式(5)计算目的地址Des_ADDR的l-1层即叶子层组地址Up_ADDR, 这里,Up_ADDR=1。
步骤8.4,将R_Router即0011(Leaf_Router)作为flit的下一跳,确定相应的输出端口。
步骤9,转发flit:将flit从选择的输出端口转发到0011(Leaf_Router)。
步骤10,0011(Leaf_Router)接收flit:0011(Leaf_Router)将该flit存储在相应输入端 口的buffer中。
步骤11,计算最优的输出端口:
步骤11.1,计算Δx和Δy的值,此时Δx=1且Δy=0,说明源节点与目的节点在同一行上, 转下一步。
步骤11.2,选择Row_Router作为flit的下一跳,确定相应的输出端口。
步骤12,Row_Router接收flit:将接收到的flit存储在相应输入端口的buffer中。
步骤13,选择输出端口阶段:
步骤13.1,根据公式(4)计算目的地址Des_ADDR的组地址Gro_ADDR,这里, Gro_ADDR=0。
步骤13.2,该路由器的地址是0=0,转下一步。
步骤13.3,根据公式(5)计算目的地址Des_ADDR的l-1层即叶子层组地址Up_ADDR, 这里,Up_ADDR=1。
步骤13.4,将R_Router即0111(Leaf_Router)作为flit的下一跳,确定相应的输出端口。
步骤14,转发flit阶段:将flit从选择的输出端口转发到0111(Leaf_Router)。
步骤15,0111(Leaf_Router)接收flit阶段:将接收到的flit存储在相应输入端口的buffer 中。
步骤16,计算最优的输出端口。
步骤16.1,计算Δx和Δy的值,此时Δx=0,Δy=0则说明源节点与目的节点连接在同一 路由器上,转下一步。
步骤16.2,判断目的地址的Core_id,此时Core_id=1,则将flit转发给R_Core。此时该 flit到达目的地10111。
机译: 一种在树结构中恢复无线网络中路由路径的方法,尤其是当节点自己构建树路由无线网络或其连接时,丢失并重新设置路由时,尤其是用于维护现有树路由路径的方法路径
机译: 基于低功耗无线网状网络配置的通道跳跃时间多路复用无线链路和方法的路由设备
机译: 基于低功耗无线网状网络配置的信道跳变时分多路无线链路的路由装置及其方法