二维片上网络拓扑结构的自适应路由方法
二维片上网络拓扑结构的自适应路由方法
【技术领域】
[0001]本发明属于电子物理技术领域，更进一步涉及微电子集成电路技术领域中的一种基于二维片上网络拓扑结构的拥塞控制路由方法技术。本发明自适应路由方法中包括本地注入方向选择、路由节点路由计算以及流量控制器输出端口选择三个部分，本发明的自适应路由方法可以很好地避开拥塞节点，提高网络通吐率以及降低网络延迟。
【背景技术】
[0002]片上网络NoC(Network-on-Chip)借鉴了计算机网络通信的思想，由路由和包交换技术替代了传统的总线通讯方式，实现了处理单元(IP核)与通信结构(网络)的分离，解决了传统SOC(System-On-Chip)的总线结构所固有的三大问题:(I)由于地址空间有限而引起的可扩展性问题；(2)由于分时通讯而引起的通讯效率问题；(3)由于全局同步而引起的功耗和面积问题。在NoC中，每个节点与一个路由器相连接。路由器通过局部互连线与其他临近的路由器相连接，节点之间的通讯需要经过多个跳步。微处理器的设计也将从以计算为中心逐渐过渡到以通讯为中心。
[0003]现有的片上网络结构主要分为2D和3D两大类，其中2D中主要包括二维网状片上网络(2D mesh)、树形(Tree)和蝶形(Butterfly)等拓扑结构，其中传统的二维网状片上网络结构(2D Mesh)的规则性和易扩展性，有利于布局布线，因此有关片上网络很多的路由算法、容错、服务质量、功耗等问题的研宄都是基于Mesh结构及变型结构，本发明就是基于一种Mesh的变形结构。基于二维网状片上网络的路由方法可以分为确定性的维序路由方法和自适应性的路由方法，其中确定性的维序路由方法路由路径是确定的，无法避免拥塞节点，在网络负载重时则导致网络性能低；自适应性的路由方法主要有DyAD路由方法以及DyXY路由方法等，这些自适应的路由方法均衡网络负载效率低以及拥塞控制能力弱，并且不加虚通道输入缓冲时会存在死锁问题，为解决死锁问题加上虚通道输入缓冲时，使得硬件开销大。
[0004]浙江大学拥有的专利技术“具备自适应路由能力的片上网络路由器及其实现方法”(申请号CN 200910095348.2，授权公告号CN 101488922，公开日为2009.07.22)，公开了一种具备自适应路由能力的片上网络路由器及其实现方法，该片上网络路由器，包括依次连接的输入流控制器、输入缓存器、路由仲裁器、输出控制器和输出流控制器。其通过采用改进的XY路由器，使得路由过程具备一定的自适应性，可以根据数据端口拥塞度，动态选择合适的数据端口，减少数据包的阻塞，提高网络的传输速度和吞吐量。该专利技术存在的不足是，路由方法是基于传统的二维片上网络结构，导致网络性能差，同时该专利技术在动态选择数据端口时忽视了网络负载的均匀性，又在一定程度上降低了网络性能。
[0005]上海交通大学拥有的专利技术“一种基于片上网络的无死锁路由方法”(申请号CN 201110321481.2，授权公告号CN 102333038 A，公开日为 2012.01.25)，公开了一种基于片上网络的无死锁路由方法，该路由方法主要包括的步骤为:在源节点将数据包复制η份，其中，η彡3 ;在片上网络中设定η条自源节点至目的节点的不交叉的通道，η份数据包分别在η条通道上传输；η份数据包到达目的节点后再通过表决器得到正确结果，实现了空间上的冗余。该专利技术存在的不足是，路由方法并不能避开拥塞节点，并且通过将数据包复制η份的方法导致网络资源浪费严重，从而影响网络性能。
[0006]长春理工大学拥有的专利技术“基于动态路由表的片上网络拥塞控制方法”(申请号 CN 201410384166.8，授权公告号 CN 104202253 Α，公开日为 2014.12.10)公开了一种基于动态路由表的片上网络拥塞控制方法包括定义动态路由表的自更新规则、片上网络的启动和初始化、求解和自身动态路由表、确定非故障邻近节点并交付数据等步骤。该方法中采用动态路由表可根据其他节点的当前状况动态更新和决策自身当前的最佳传送路径，其每一个动态路由表内总是保存有去其他任意目的节点的全局拥塞度最小的最佳路径，减少各路由节点之间频繁的读写操作，削减数据计算量并节约运算占用的时间，缓解和限制了网络拥塞的产生，提高了整个片上网络的数据处理能力和吞吐量。该专利存在的不足是:每个路由节点均含有一个动态路由表且该动态路由表随着网络规模的增大而迅速增大，使其面积和功耗开销随着网络规模的增大而增大，同时该动态路由表工作步骤冗长，影响网络性會K。
【发明内容】
[0007]本发明的目的就是克服上述现有技术的不足，解决传统二维片上网络路由方法无法有效避免拥塞节点或者避免拥塞节点时硬件开销大效率低导致网络性能低下的问题，该自适应路由算法具有拥塞性能控制能力强、硬件开销小、网络延迟低、吞吐率高的特点。
[0008]为实现上述目的，本发明采取的技术方案为:
[0009]一种基于二维片上网络拓扑结构的自适应路由方法，其特征在于包括如下步骤:
[0010](I)源节点本地端口接收数据分组；
[0011](2)源节点根据本地注入方向选择方法所得到的注入方向的结果，将数据分组从本地端口注入到该输出端口方向；
[0012](3)与路由节点输出方向相连的流量控制器端口接收数据分组；
[0013](4)为数据分组分配流量控制器的输出端口，根据流量控制器的输出端口分配方法所得到的分配结果将数据分组传输到该输出端口 ；
[0014](5)与流量控制器输出端口相连的路由节点的路由端口接收数据分组；
[0015](6)判断路由节点是否为目的节点:
[0016](6a)若该节点的坐标与目的节点的坐标相同，则执行步骤⑶；
[0017](6b)若该节点的坐标与目的节点的坐标不相同，则执行步骤(7);
[0018](7)路由节点计算输出端口方向，然后返回执行步骤(3);
[0019](8)路由节点将数据分组传输到本地输出端口，路由结束。
[0020]上述基于二维片上网络拓扑结构的自适应路由方法，步骤(2)中所述的本地注入方向选择方法是指:源节点的本地端口接收到数据分组后根据数据分组目的节点的坐标信息和本地拥塞信息选择要注入的端口方向，其具体步骤为:
[0021](2a)路由节点计算数据分组的输出端口集合:
[0022](2a-l)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有东方向，执行步骤(2d)；
[0023](2a-2)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有西方向，执行步骤(2d);
[0024](2a-3)若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合只有南方向，执行步骤(2d)；
[0025](2a-4)若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合只有北方向，执行步骤(2d);
[0026](2a-5)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有东方向和南方向，执行步骤(2b)；
[0027](2a-6)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有东方向和北方向，执行步骤(2b)；
[0028](2a-7)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有西方向和南方向，执行步骤(2b)；
[0029](2a-8)若目的节点的横坐标小 于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有西方向和北方向，执行步骤(2b)；
[0030](2b)计算四个路由输出端口方向的拥塞信息:
[0031]将本地端口最后一次注入到东方向、西方向、南方向和北方向的数据分组所等待的时钟周期数作为当前注入选择的拥塞信息，分别存储在四个方向的排队等待时间寄存器里；
[0032](2c)根据步骤(2a)中路由节点计算产生的输出端口集合以及步骤(2b)中得到的拥塞信息，选择输出端口集合里具有较小时钟周期等待数的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出端口方向，注入结束；
[0033](2d)将输出端口集合里的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出端口方向，注入结束。
[0034]上述基于二维片上网络拓扑结构的自适应路由方法，步骤(4)中所述的流量控制器的输出端口分配方法是指:流量控制器接收到路由节点的数据分组后根据计算出来的本地拥塞信息、区域拥塞信息以及高优先级拥塞信息三部分进行流量控制器的输出端口选择，具体步骤为:
[0035](4a)计算该输入端口数据分组的优先级:
[0036](4a-l)若该数据分组的目的节点和该流量控制器相连，则该数据分组具有高优先级，执行步骤(4b);
[0037](4a-2)若该数据分组的目的节点和该流量控制器没有相连，则该数据分组具有低优先级，执行步骤(4c)；
[0038](4b)将与目的节点相连的流量控制器输出端口分配给数据分组，将数据分组传输到该输出端口，同时把该输出端口分配信息作为高优先级拥塞信息发给拥塞信息收集器；
[0039](4c)计算该流量控制器其余所有输入端口所接收到的数据分组的优先级，把所有高优先级数据分组的输出端口请求信号作为高优先级拥塞信息发给拥塞信息收集器；
[0040](4d)计算当前流量控制器被使用的输出端口作为本地拥塞信息发给拥塞信息收集器;
[0041](4e)计算该数据分组下一个流量控制器的输入链路状态，如果空闲则为不拥塞，反之为拥塞，将其作为局部拥塞信息发给拥塞信息收集器；
[0042](4f)拥塞信息收集器根据收集到的拥塞信息以及数据分组的优先级别，为数据分组计算可分配的剩余还没有高优先级请求并且没有拥塞的输出端口；
[0043](4g)输出端口分配器为数据分组分配输出端口:
[0044](4g-l)若没有可分配的输出端口，数据分组被阻塞，等待可分配的输出端口可用；
[0045](4g-2)若有I个可分配的输出端口，输出端口分配器为数据分组分配该端口，将数据分组传输到该输出端口；
[0046](4g-3)若有超过I个可分配的输出端口，则可分配的输出端口按照轮询方法为数据分组分配，将数据分组传输到该输出端口。
[0047]本发明与现有技术相比，具有以下优点:
[0048]第一，本发明由于在数据分组注入网络时，采用了注入方向选择与路由计算相结合的方法，使得数据分组从本地端口注入到路由网络时，可以根据源节点和目的节点的坐标以及当前路由节点的拥塞情况，选择拥塞较小的路由端口将数据分组注入，可以很好地减少网络拥塞、提升网络性能，同时在计算路由节点每个输出端口的拥塞情况时采用等待时钟周期数的多少，只需要计数器和比较器就可以实现，从而在减小网络拥塞的同时使得硬件开销小。
[0049]第二，本发明由于在流量控制器中采用了高优先级拥塞信息，使得具有高优先级的数据分组直接到达目的节点，而不用考虑计算其它拥塞信息，从而使得网络吞吐率提高、延迟减少。
[0050]第三，本发明由于在流量控制器中采用了高优先级拥塞信息、本地拥塞信息以及区域拥塞信息相结合的方法，不仅能保证当前流量控制器的输出端口可用，还可以保证下一个流量控制器有可用的数据输入端口，从而使得数据传输在两个路由节点之间形成没有阻塞的通路，有效地避免了网络拥塞节点、提升了网络性能。
【附图说明】
[0051]图1为本发明所基于的二维片上网络4X4拓扑结构示意图；
[0052]图2为本发明流程图；
[0053]图3为本发明中数据分组注入方向选择方法流程图；
[0054]图4为本发明中流量控制器输出端口分配方法流程图。
【具体实施方式】
:
[0055]下面结合附图对本发明作进一步的描述。
[0056]参照附图1对本发明的自适应路由方法所基于的二维片上网络拓扑结构作进一步的描述。
[0057]本二维片上网络拓扑结构，包括路由节点和流量控制器。在mXn网络中，m彡2，η彡2，包含mXn个路由节点和m+n_2个流量控制器JZI^mXn个路由节点排列成mXn的矩形网络；在111\11网络中每每相邻的两行路由节点之间放置一个流量控制器；在!11\11网络中每每相邻的两列路由节点之间放置一个流量控制器；所述路由节点通过数据总线与相邻的流量控制器相连；其中:
[0058]所述的路由节点，用于接收数据分组并对数据分组进行分配，将来自本地端口的数据分组根据数据包注入原则注入相邻的流量控制器，将来自路由端口的数据分组分类转发至本地端口或目的地址对应的路由节点端口 ；
[0059]所述的流量控制器，用于接收来自路由节点的数据分组，按照相应的路由方法将数据分组传输至下一个路由节点。
[0060]为说明方便，图1中取m = 4，η = 4，即构成一个4X4的拓扑结构。每个路由节点设有四个路由端口和一个本地端口，四个路由端口分别用于连接东、西、南、北四个方向上相邻的流量控制器，本地端口通过NI模块与本地IP连接，用于将数据分组注入mXn矩形片上网络和接收mXn矩形片上网络排出的数据分组。
[0061]在m X η矩形片上网络中设定右起第一个节点为片上网络的坐标原点，将坐标原点水平向右的方向作为横坐标的正方向，将坐标原点垂直向下的方向作为纵坐标的正方向，组成一个二维坐标系 O 图1 中(0，O)，(O, I)，(O, 2)，(O, 3)，(I, O)，(I, I)，(I, 2)，(I, 3)，(2，O)，(2，I)，(2，2)，(2，3)，(3，O)，(3，I)，(3，2)，(3，3)标识，表示路由器节点所对应的坐标值。图1中ΤΜ_Η0、ΤΜ_Η1、ΤΜ_Η2的标识，表示水平流量控制器，图1中TM_V0、TM_V1、TM_V2的标识，表示垂直流量控制器。
[0062]流量控制器分为两类:水平流量控制器和垂直流量控制器。水平流量控制器用于连接两个相邻的列路由节点组，只负责东和西方向的数据传输；垂直流量控制器用于连接两个相邻的行路由节点组，只负责南和北方向的数据传输。在4X4网络拓扑结构中，包含16个路由节点和8个流量控制器，其中水平流量控制器共有3个，每个水平流量控制器有8个端口，其中左端有4个端口，标号为0，1，2，3，右端有4个端口标号为4，5，6，7，垂直流量控制器共有3个，每个垂直流量控制器有8个端口，其中上端有4个端口，标号为0，I，2，3，下端有4个端口，标号为0，I，2，3。流量控制器只能将数据分组从一端传输到另外一端而不能将数据分组在同一端传输，即对于水平流量控制器，如果左端的某一个端口接收到数据分组则只能将其传输到右端的某一个端口，如果右端的某一个端口接收到数据分组则只能将其传输到左端的某一个端口，对于垂直流量控制器，如果上端的某一个端口接收到数据分组则只能将其传输到下端的某一个端口，如果下端的某一个端口接收到数据分组则只能将其传输到上端的某一个端口。流量控制器的输入端口指的的是数据分组的接收一端的端口，流量控制的输出端口指的是非数据分组接收的一端，例如对于水平流量控制器，如果左端的某一个 端口接收到数据分组，则流量控制器的左端为输入端口右端为输出端口，如果右端的某一个端口接收到数据分组，则流量控制器的右端为输入端口左端为输出端口。
[0063]参照附图2对本发明自适应路由方法作进一步的描述。具体步骤为:
[0064]步骤1.源节点本地端口接收数据分组。
[0065]源节点的本地端口接收来自本地IP发送的数据分组。
[0066]步骤2.本地端口注入数据分组到相应方向。
[0067]源节点的根据注入方向选择的结果将本地端口的数据分组发送到相应的路由节点输出端口。
[0068]步骤3.流量控制器接收数据分组。
[0069]与路由节点输出端口方向相连的流量控制器端口接收数据分组。
[0070]步骤4.为数据分组分配流量控制器的输出端口。
[0071]流量控制器为数据分组分配流量控制器的输出端口，将数据分组传输到该输出端
□ O
[0072]步骤5.路由节点接收数据分组。
[0073]与流量控制器输出端口相连的路由节点的相应路由端口方向接收数据分组。
[0074]步骤6.判断路由节点是否为目的节点。
[0075]若当前路由节点是目的节点，则执行步骤8，否则执行步骤7。
[0076]步骤7.路由节点计算输出端口方向。
[0077]若数据分组在本路由节点的输入方向为东方向，则输出端口为西端口，将数据分组传输到该输出端口方向，执行步骤3;若数据分组在本路由节点的输入方向为西方向，则输出端口为东端口，将数据分组传输到该输出端口方向，执行步骤3 ;若数据分组在本路由节点的输入方向为南方向，则输出端口为北端口，将数据分组传输到该输出端口方向，执行步骤3;若数据分组在本路由节点的输入方向为北方向，则输出端口为南端口，将数据分组传输到该输出端口方向，执行步骤3 ；
[0078]该步骤中，数据分组在路由节点内的传输方向不允许拐弯，即数据分组输入端口方向为西方向则输出端口方向为东输出端口，数据分组输入端口方向为东方向则输出端口方向为西输出端口，数据分组输入端口方向为南方向则输出端口方向为北输出端口，数据分组输入端口方向为北方向则输出端口方向为南输出端口。这样避免了死锁的产生，并且路由计算简单所需要的硬件开销小。
[0079]步骤8.将数据分组传输到本地输出端口，路由结束。
[0080]参照附图3对本路由方法中的本地注入方向选择方法作进一步的描述，具体步骤为:
[0081]步骤2a.计算数据分组的输出端口集合。
[0082]路由节点计算数据分组的输出端口集合:
[0083]若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有东方向，执行步骤2d ；
[0084]若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有西方向，执行步骤2d ；
[0085]若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合只有南方向，执行步骤2d ；
[0086]若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合只有北方向，执行步骤2d;
[0087]若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有东方向和南方向，执行步骤2b ；
[0088]若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有东方向和北方向，执行步骤2b ；
[0089]若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有西方向和南方向，执行步骤2b ；
[0090]若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有西方向和北方向，执行步骤2b ；
[0091]步骤2b.计算四个输出方向的拥塞信息。
[0092]本地端口最后一次注入到东方向、西方向、南方向和北方向的数据分组所等待的时钟周期数作为当前注入选择的拥塞信息，分别存储在四个方向的排队等待时间寄存器里。
[0093]该步骤中，采用本地端接口最后一次到四个输出端口方向的等待时间作为每个输出端口方向的注入拥塞选择信息，这样只需要计数器就可以实现而不需要其它额外的硬件开销，使得硬件开销小。
[0094]步骤2c.选择输出端口集合里拥塞较小的作为注入方向。
[0095]根据步骤2a中路由节点计算产生的输出端口集合以及步骤2b中计算产生的拥塞信息，选择输出端口集合里具有较小时钟周期等待数的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出端口方向，注入结束。
[0096]步骤2d.将数据分组注入到该方向。
[0097]将输出端口集合里的方向作为数据分组的注入方向，将数据分组注入到该路由输出端口方向，注入结束。
[0098]参照附图4对本发明自适应路由方法中流量控制器输出端口分配方法作进一步的描述，具体步骤为:
[0099]步骤4a.判断数据分组的优先级:
[0100]若该数据分组的目的节点和该流量控制器相连，则该数据分组具有高优先级，执行步骤4b ；
[0101]若该数据分组的目的节点和该流量控制器没有相连，则该数据分组具有低优先级，执行步骤4c。
[0102]该步骤中所述的目的节点是否与该流量控制器相连，是指目的节点与流量控制器的非接收数据分组端相连，例如若路由节点将本地端口的数据分组传输给与路由节点的南端口相连的垂直流量控制器，即垂直流量控制器的上端为数据分组接收端，非数据分组接收端则为垂直流量控制器的下端，若路由节点将本地端口的数据分组传输给与路由节点的北端口相连的垂直流量控制器，即垂直流量控制器的下端为数据分组接收端，非数据分组接收端则为垂直流量控制器的上端，水平流量控制器类似。
[0103]步骤4b.直接分配输出端口并发分配信息给拥塞信息收集器，分配结束。
[0104]流量控制器将与目的节点相连的流量控制器输出端口分配给数据分组，同时把该输出端口分配信息作为高优先级拥塞信息发给拥塞信息收集器，流量控制器输出端口分配结束。
[0105]步骤4c.计算其余输入端口高优先级拥塞信息并发给拥塞信息收集器。
[0106]流量控制器计算其余所有输入端口数据分组的优先级，把所有高优先级数据分组的输出端口请求信号作为高优先级拥塞信息发给拥塞信息收集器。
[0107]步骤4d.计算本地拥塞信息并发给拥塞信息收集器。
[0108]流量控制器计算当前流量控制器被使用的输出端口作为本地拥塞信息发给拥塞信息收集器。
[0109]该步骤中当前流量控制器被使用的输出端口，表示的是输出端口中有数据分组传输，即该输出端口不能分配给当前数据分组。
[0110]步骤4e.计算区域拥塞信息并发给拥塞信息收集器。
[0111]计算该数据分组下一个流量控制器的输入链路状态，如果可用则为不拥塞，反之为拥塞，将其作为局部拥塞信息发给拥塞信息收集器。
[0112]该步骤中数据分组下一个流量控制器是指，数据分组没有到达目的节点需要通过路由节点和流量控制器继续传输，下一个传输数据分组的流量控制器为所述的下一个流量控制器。该自适应路由方法中，数据分组只能在一种流量控制器中传输，即数据分组在到达目的节点之前要么一直在水平流量控制器中传输，要么一直在垂直流量控制器中传输，而不能在传输过程中通过两种流量控制器传输。
[0113]步骤4f.拥塞信息收集器计算可分配输 出端口。
[0114]拥塞信息收集器根据收集到的拥塞信息以及数据分组的优先级别，为数据分组计算可分配的剩余还没有高优先级请求并且没有拥塞的输出端口。
[0115]该步骤中，首先排除掉输入端口中所有高优先级数据分组所请求的流量控制器输出端口(即为高优先级拥塞信息)，然后排除掉被使用的流量控制器输出端口(即为本地拥塞信息)，最后排除掉下一个流量控制器被使用的输入端口与路由节点相连的当前流量控制器的输出端口(即为区域拥塞信息)，剩下的即为空闲的可以分配的流量控制器输出端口。采用这种方法，使得低优先级数据分组可以从路由节点连续传输两个流量控制器到达第二个流量控制器的输入端口，传输过程中没有拥塞；使得高优先级数据分组直接通过流量控制器到达目的节点，传输过程中没有拥塞。这种拥塞方法很好的控制了数据分组在传输过程中的拥塞，从而提高了网络吞吐率，降低了网络延迟，提高了网络性能。
[0116]步骤4g.流量控制器分配输出端口。
[0117]流量控制器为数据分组分配步骤4f中计算得到的可以分配的空闲输出端口:
[0118]若没有可分配的输出端口，数据分组被阻塞，等待可分配的输出端口可用；
[0119]若有I个可分配的输出端口，流量控制器为数据分组分配该端口，分配结束；
[0120]若有超过I个可分配的输出端口，则可分配的输出端口按照轮询方法为数据分组分配，即假设有1、2、3三个可分配的输出端口，该输入端口不同的数据分组(可分配输出端口均为1、2、3端口)按照顺序依次分配1、2、3端口并进行循环，分配结束。
【主权项】
1.一种基于二维片上网络拓扑结构的自适应路由方法，其特征在于包括如下步骤: (1)源节点本地端口接收数据分组； (2)源节点根据本地注入方向选择方法所得到的注入方向的结果，将数据分组从本地端口注入到该输出端口方向； (3)与路由节点输出方向相连的流量控制器端口接收数据分组； (4)为数据分组分配流量控制器的输出端口，根据流量控制器的输出端口分配方法所得到的分配结果将数据分组传输到该输出端口； (5)与流量控制器输出端口相连的路由节点的路由端口接收数据分组； (6)判断路由节点是否为目的节点: (6a)若该节点的坐标与目的节点的坐标相同，则执行步骤(8); (6b)若该节点的坐标与目的节点的坐标不相同，则执行步骤(7); (7)路由节点计算输出端口方向，然后返回执行步骤(3); (8)路由节点将数据分组传输到本地输出端口，路由结束。2.根据权利要求1所述的基于二维片上网络拓扑结构的自适应路由方法，其特征在于，步骤(2)中所述的本地注入方向选择方法是指:源节点的本地端口接收到数据分组后根据数据分组目的节点的坐标信息和本地拥塞信息选择要注入的端口方向，其具体步骤为: (2a)路由节点计算数据分组的输出端口集合: (2a_l)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有东方向，执行步骤(2d)； (2a_2)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有西方向，执行步骤(2d); (2a_3)若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合只有南方向，执行步骤(2d)； (2a-4)若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合只有北方向，执行步骤(2d); (2a-5)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有东方向和南方向，执行步骤(2b)； (2a-6)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有东方向和北方向，执行步骤(2b)； (2a-7)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有西方向和南方向，执行步骤(2b)； (2a-8)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有西方向和北方向，执行步骤(2b)； (2b)计算四个路由输出端口方向的拥塞信息:将本地端口最后一次注入到东方向、西方向、南方向和北方向的数据分组所等待的时钟周期数作为当前注入选择的拥塞信息，分别存储在四个方向的排队等待时间寄存器里；(2c)根据步骤(2a)中路由节点计算产生的输出端口集合以及步骤(2b)中得到的拥塞信息，选择输出端口集合里具有较小时钟周期等待数的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出端口方向，注入结束； (2d)将输出端口集合里的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出〗而口方向，注入结束。3.根据权利要求1所述的基于二维片上网络拓扑结构的自适应路由方法，其特征在于，步骤(4)中所述的流量控制器的输出端口分配方法是指:流量控制器接收到路由节点的数据分组后根据计算出来的本地拥塞信息、区域拥塞信息以及高优先级拥塞信息三部分进行流量控制器的输出端口选择，具体步骤为: (4a)判断输入端口数据分组的优先级: (4a-l)若该数据分组的目的节点和该流量控制器相连，则该数据分组具有高优先级，执行步骤(4b)； (4a-2)若该数据分组的目的节点和该流量控制器没有相连，则该数据分组具有低优先级，执行步骤(4c)； (4b)将与目的节点相连的流量控制器输出端口分配给数据分组，将数据分组传输到该输出端口，同时把该输出端口分配信息作为高优先级拥塞信息发给拥塞信息收集器； (4c)计算该流量控制器其余所有输入端口所接收到的数据分组的优先级，把所有高优先级数据分组的输出端口请求信号作为高优先级拥塞信息发给拥塞信息收集器； (4d)计算当前流量控制器被使用的输出端口作为本地拥塞信息发给拥塞信息收集器; (4e)计算该数据分组下一个流量控制器的输入链路状态，如果空闲则为不拥塞，反之为拥塞，将其作为局部拥塞信息发给拥塞信息收集器； (4f)拥塞信息收集器根据收集到的拥塞信息以及数据分组的优先级别，为数据分组计算可分配的剩余还没有高优先级请求并且没有拥塞的输出端口； (4g)输出端口分配器为数据分组分配输出端口: (4g-l)若没有可分配的输出端口，数据分组被阻塞，等待可分配的输出端口可用；(4g-2)若有I个可分配的输出端口，输出端口分配器为数据分组分配该端口，将数据分组传输到该输出端口； (4g-3)若有超过I个可分配的输出端口，则可分配的输出端口按照轮询方法为数据分组分配，将数据分组传输到该输出端口。
【专利摘要】本发明公开了一种基于二维片上网络拓扑结构的自适应路由方法，用于解决传统二维片上网络路由方法无法有效避免拥塞节点或者避免拥塞节点时硬件开销大效率低导致网络性能低下的问题。本发明的自适应路由方法采用了注入方向选择和流量控制器输出端口分配相结合的方法。本发明的自适应路由方法具体步骤为：1.源节点本地端口接收数据分组；2.数据分组的注入；3.流量控制器接收数据分组；4.流量控制器输出端口分配；5.路由节点接收数据分组；6.判断路由节点是否为目的节点；7.路由节点计算输出端口方向；8.数据分组传输到目的节点本地输出端口。该路由方法是一种具有良好拥塞控制能力且无死锁、硬件开销小的自适应路由方法。
【IPC分类】H04L12/833, G06F15/78, H04L12/801
【公开号】CN104901899
【申请号】CN201510342328
【发明人】史江义, 舒浩, 李钊, 马佩军, 王禛, 吴冰冰, 余文哲, 张春焱
【申请人】西安电子科技大学
【公开日】2015年9月9日
【申请日】2015年6月18日
【技术领域】
[0001]本发明属于电子物理技术领域，更进一步涉及微电子集成电路技术领域中的一种基于二维片上网络拓扑结构的拥塞控制路由方法技术。本发明自适应路由方法中包括本地注入方向选择、路由节点路由计算以及流量控制器输出端口选择三个部分，本发明的自适应路由方法可以很好地避开拥塞节点，提高网络通吐率以及降低网络延迟。
【背景技术】
[0002]片上网络NoC(Network-on-Chip)借鉴了计算机网络通信的思想，由路由和包交换技术替代了传统的总线通讯方式，实现了处理单元(IP核)与通信结构(网络)的分离，解决了传统SOC(System-On-Chip)的总线结构所固有的三大问题:(I)由于地址空间有限而引起的可扩展性问题；(2)由于分时通讯而引起的通讯效率问题；(3)由于全局同步而引起的功耗和面积问题。在NoC中，每个节点与一个路由器相连接。路由器通过局部互连线与其他临近的路由器相连接，节点之间的通讯需要经过多个跳步。微处理器的设计也将从以计算为中心逐渐过渡到以通讯为中心。
[0003]现有的片上网络结构主要分为2D和3D两大类，其中2D中主要包括二维网状片上网络(2D mesh)、树形(Tree)和蝶形(Butterfly)等拓扑结构，其中传统的二维网状片上网络结构(2D Mesh)的规则性和易扩展性，有利于布局布线，因此有关片上网络很多的路由算法、容错、服务质量、功耗等问题的研宄都是基于Mesh结构及变型结构，本发明就是基于一种Mesh的变形结构。基于二维网状片上网络的路由方法可以分为确定性的维序路由方法和自适应性的路由方法，其中确定性的维序路由方法路由路径是确定的，无法避免拥塞节点，在网络负载重时则导致网络性能低；自适应性的路由方法主要有DyAD路由方法以及DyXY路由方法等，这些自适应的路由方法均衡网络负载效率低以及拥塞控制能力弱，并且不加虚通道输入缓冲时会存在死锁问题，为解决死锁问题加上虚通道输入缓冲时，使得硬件开销大。
[0004]浙江大学拥有的专利技术“具备自适应路由能力的片上网络路由器及其实现方法”(申请号CN 200910095348.2，授权公告号CN 101488922，公开日为2009.07.22)，公开了一种具备自适应路由能力的片上网络路由器及其实现方法，该片上网络路由器，包括依次连接的输入流控制器、输入缓存器、路由仲裁器、输出控制器和输出流控制器。其通过采用改进的XY路由器，使得路由过程具备一定的自适应性，可以根据数据端口拥塞度，动态选择合适的数据端口，减少数据包的阻塞，提高网络的传输速度和吞吐量。该专利技术存在的不足是，路由方法是基于传统的二维片上网络结构，导致网络性能差，同时该专利技术在动态选择数据端口时忽视了网络负载的均匀性，又在一定程度上降低了网络性能。
[0005]上海交通大学拥有的专利技术“一种基于片上网络的无死锁路由方法”(申请号CN 201110321481.2，授权公告号CN 102333038 A，公开日为 2012.01.25)，公开了一种基于片上网络的无死锁路由方法，该路由方法主要包括的步骤为:在源节点将数据包复制η份，其中，η彡3 ;在片上网络中设定η条自源节点至目的节点的不交叉的通道，η份数据包分别在η条通道上传输；η份数据包到达目的节点后再通过表决器得到正确结果，实现了空间上的冗余。该专利技术存在的不足是，路由方法并不能避开拥塞节点，并且通过将数据包复制η份的方法导致网络资源浪费严重，从而影响网络性能。
[0006]长春理工大学拥有的专利技术“基于动态路由表的片上网络拥塞控制方法”(申请号 CN 201410384166.8，授权公告号 CN 104202253 Α，公开日为 2014.12.10)公开了一种基于动态路由表的片上网络拥塞控制方法包括定义动态路由表的自更新规则、片上网络的启动和初始化、求解和自身动态路由表、确定非故障邻近节点并交付数据等步骤。该方法中采用动态路由表可根据其他节点的当前状况动态更新和决策自身当前的最佳传送路径，其每一个动态路由表内总是保存有去其他任意目的节点的全局拥塞度最小的最佳路径，减少各路由节点之间频繁的读写操作，削减数据计算量并节约运算占用的时间，缓解和限制了网络拥塞的产生，提高了整个片上网络的数据处理能力和吞吐量。该专利存在的不足是:每个路由节点均含有一个动态路由表且该动态路由表随着网络规模的增大而迅速增大，使其面积和功耗开销随着网络规模的增大而增大，同时该动态路由表工作步骤冗长，影响网络性會K。
【发明内容】
[0007]本发明的目的就是克服上述现有技术的不足，解决传统二维片上网络路由方法无法有效避免拥塞节点或者避免拥塞节点时硬件开销大效率低导致网络性能低下的问题，该自适应路由算法具有拥塞性能控制能力强、硬件开销小、网络延迟低、吞吐率高的特点。
[0008]为实现上述目的，本发明采取的技术方案为:
[0009]一种基于二维片上网络拓扑结构的自适应路由方法，其特征在于包括如下步骤:
[0010](I)源节点本地端口接收数据分组；
[0011](2)源节点根据本地注入方向选择方法所得到的注入方向的结果，将数据分组从本地端口注入到该输出端口方向；
[0012](3)与路由节点输出方向相连的流量控制器端口接收数据分组；
[0013](4)为数据分组分配流量控制器的输出端口，根据流量控制器的输出端口分配方法所得到的分配结果将数据分组传输到该输出端口 ；
[0014](5)与流量控制器输出端口相连的路由节点的路由端口接收数据分组；
[0015](6)判断路由节点是否为目的节点:
[0016](6a)若该节点的坐标与目的节点的坐标相同，则执行步骤⑶；
[0017](6b)若该节点的坐标与目的节点的坐标不相同，则执行步骤(7);
[0018](7)路由节点计算输出端口方向，然后返回执行步骤(3);
[0019](8)路由节点将数据分组传输到本地输出端口，路由结束。
[0020]上述基于二维片上网络拓扑结构的自适应路由方法，步骤(2)中所述的本地注入方向选择方法是指:源节点的本地端口接收到数据分组后根据数据分组目的节点的坐标信息和本地拥塞信息选择要注入的端口方向，其具体步骤为:
[0021](2a)路由节点计算数据分组的输出端口集合:
[0022](2a-l)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有东方向，执行步骤(2d)；
[0023](2a-2)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有西方向，执行步骤(2d);
[0024](2a-3)若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合只有南方向，执行步骤(2d)；
[0025](2a-4)若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合只有北方向，执行步骤(2d);
[0026](2a-5)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有东方向和南方向，执行步骤(2b)；
[0027](2a-6)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有东方向和北方向，执行步骤(2b)；
[0028](2a-7)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有西方向和南方向，执行步骤(2b)；
[0029](2a-8)若目的节点的横坐标小 于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有西方向和北方向，执行步骤(2b)；
[0030](2b)计算四个路由输出端口方向的拥塞信息:
[0031]将本地端口最后一次注入到东方向、西方向、南方向和北方向的数据分组所等待的时钟周期数作为当前注入选择的拥塞信息，分别存储在四个方向的排队等待时间寄存器里；
[0032](2c)根据步骤(2a)中路由节点计算产生的输出端口集合以及步骤(2b)中得到的拥塞信息，选择输出端口集合里具有较小时钟周期等待数的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出端口方向，注入结束；
[0033](2d)将输出端口集合里的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出端口方向，注入结束。
[0034]上述基于二维片上网络拓扑结构的自适应路由方法，步骤(4)中所述的流量控制器的输出端口分配方法是指:流量控制器接收到路由节点的数据分组后根据计算出来的本地拥塞信息、区域拥塞信息以及高优先级拥塞信息三部分进行流量控制器的输出端口选择，具体步骤为:
[0035](4a)计算该输入端口数据分组的优先级:
[0036](4a-l)若该数据分组的目的节点和该流量控制器相连，则该数据分组具有高优先级，执行步骤(4b);
[0037](4a-2)若该数据分组的目的节点和该流量控制器没有相连，则该数据分组具有低优先级，执行步骤(4c)；
[0038](4b)将与目的节点相连的流量控制器输出端口分配给数据分组，将数据分组传输到该输出端口，同时把该输出端口分配信息作为高优先级拥塞信息发给拥塞信息收集器；
[0039](4c)计算该流量控制器其余所有输入端口所接收到的数据分组的优先级，把所有高优先级数据分组的输出端口请求信号作为高优先级拥塞信息发给拥塞信息收集器；
[0040](4d)计算当前流量控制器被使用的输出端口作为本地拥塞信息发给拥塞信息收集器;
[0041](4e)计算该数据分组下一个流量控制器的输入链路状态，如果空闲则为不拥塞，反之为拥塞，将其作为局部拥塞信息发给拥塞信息收集器；
[0042](4f)拥塞信息收集器根据收集到的拥塞信息以及数据分组的优先级别，为数据分组计算可分配的剩余还没有高优先级请求并且没有拥塞的输出端口；
[0043](4g)输出端口分配器为数据分组分配输出端口:
[0044](4g-l)若没有可分配的输出端口，数据分组被阻塞，等待可分配的输出端口可用；
[0045](4g-2)若有I个可分配的输出端口，输出端口分配器为数据分组分配该端口，将数据分组传输到该输出端口；
[0046](4g-3)若有超过I个可分配的输出端口，则可分配的输出端口按照轮询方法为数据分组分配，将数据分组传输到该输出端口。
[0047]本发明与现有技术相比，具有以下优点:
[0048]第一，本发明由于在数据分组注入网络时，采用了注入方向选择与路由计算相结合的方法，使得数据分组从本地端口注入到路由网络时，可以根据源节点和目的节点的坐标以及当前路由节点的拥塞情况，选择拥塞较小的路由端口将数据分组注入，可以很好地减少网络拥塞、提升网络性能，同时在计算路由节点每个输出端口的拥塞情况时采用等待时钟周期数的多少，只需要计数器和比较器就可以实现，从而在减小网络拥塞的同时使得硬件开销小。
[0049]第二，本发明由于在流量控制器中采用了高优先级拥塞信息，使得具有高优先级的数据分组直接到达目的节点，而不用考虑计算其它拥塞信息，从而使得网络吞吐率提高、延迟减少。
[0050]第三，本发明由于在流量控制器中采用了高优先级拥塞信息、本地拥塞信息以及区域拥塞信息相结合的方法，不仅能保证当前流量控制器的输出端口可用，还可以保证下一个流量控制器有可用的数据输入端口，从而使得数据传输在两个路由节点之间形成没有阻塞的通路，有效地避免了网络拥塞节点、提升了网络性能。
【附图说明】
[0051]图1为本发明所基于的二维片上网络4X4拓扑结构示意图；
[0052]图2为本发明流程图；
[0053]图3为本发明中数据分组注入方向选择方法流程图；
[0054]图4为本发明中流量控制器输出端口分配方法流程图。
【具体实施方式】
:
[0055]下面结合附图对本发明作进一步的描述。
[0056]参照附图1对本发明的自适应路由方法所基于的二维片上网络拓扑结构作进一步的描述。
[0057]本二维片上网络拓扑结构，包括路由节点和流量控制器。在mXn网络中，m彡2，η彡2，包含mXn个路由节点和m+n_2个流量控制器JZI^mXn个路由节点排列成mXn的矩形网络；在111\11网络中每每相邻的两行路由节点之间放置一个流量控制器；在!11\11网络中每每相邻的两列路由节点之间放置一个流量控制器；所述路由节点通过数据总线与相邻的流量控制器相连；其中:
[0058]所述的路由节点，用于接收数据分组并对数据分组进行分配，将来自本地端口的数据分组根据数据包注入原则注入相邻的流量控制器，将来自路由端口的数据分组分类转发至本地端口或目的地址对应的路由节点端口 ；
[0059]所述的流量控制器，用于接收来自路由节点的数据分组，按照相应的路由方法将数据分组传输至下一个路由节点。
[0060]为说明方便，图1中取m = 4，η = 4，即构成一个4X4的拓扑结构。每个路由节点设有四个路由端口和一个本地端口，四个路由端口分别用于连接东、西、南、北四个方向上相邻的流量控制器，本地端口通过NI模块与本地IP连接，用于将数据分组注入mXn矩形片上网络和接收mXn矩形片上网络排出的数据分组。
[0061]在m X η矩形片上网络中设定右起第一个节点为片上网络的坐标原点，将坐标原点水平向右的方向作为横坐标的正方向，将坐标原点垂直向下的方向作为纵坐标的正方向，组成一个二维坐标系 O 图1 中(0，O)，(O, I)，(O, 2)，(O, 3)，(I, O)，(I, I)，(I, 2)，(I, 3)，(2，O)，(2，I)，(2，2)，(2，3)，(3，O)，(3，I)，(3，2)，(3，3)标识，表示路由器节点所对应的坐标值。图1中ΤΜ_Η0、ΤΜ_Η1、ΤΜ_Η2的标识，表示水平流量控制器，图1中TM_V0、TM_V1、TM_V2的标识，表示垂直流量控制器。
[0062]流量控制器分为两类:水平流量控制器和垂直流量控制器。水平流量控制器用于连接两个相邻的列路由节点组，只负责东和西方向的数据传输；垂直流量控制器用于连接两个相邻的行路由节点组，只负责南和北方向的数据传输。在4X4网络拓扑结构中，包含16个路由节点和8个流量控制器，其中水平流量控制器共有3个，每个水平流量控制器有8个端口，其中左端有4个端口，标号为0，1，2，3，右端有4个端口标号为4，5，6，7，垂直流量控制器共有3个，每个垂直流量控制器有8个端口，其中上端有4个端口，标号为0，I，2，3，下端有4个端口，标号为0，I，2，3。流量控制器只能将数据分组从一端传输到另外一端而不能将数据分组在同一端传输，即对于水平流量控制器，如果左端的某一个端口接收到数据分组则只能将其传输到右端的某一个端口，如果右端的某一个端口接收到数据分组则只能将其传输到左端的某一个端口，对于垂直流量控制器，如果上端的某一个端口接收到数据分组则只能将其传输到下端的某一个端口，如果下端的某一个端口接收到数据分组则只能将其传输到上端的某一个端口。流量控制器的输入端口指的的是数据分组的接收一端的端口，流量控制的输出端口指的是非数据分组接收的一端，例如对于水平流量控制器，如果左端的某一个 端口接收到数据分组，则流量控制器的左端为输入端口右端为输出端口，如果右端的某一个端口接收到数据分组，则流量控制器的右端为输入端口左端为输出端口。
[0063]参照附图2对本发明自适应路由方法作进一步的描述。具体步骤为:
[0064]步骤1.源节点本地端口接收数据分组。
[0065]源节点的本地端口接收来自本地IP发送的数据分组。
[0066]步骤2.本地端口注入数据分组到相应方向。
[0067]源节点的根据注入方向选择的结果将本地端口的数据分组发送到相应的路由节点输出端口。
[0068]步骤3.流量控制器接收数据分组。
[0069]与路由节点输出端口方向相连的流量控制器端口接收数据分组。
[0070]步骤4.为数据分组分配流量控制器的输出端口。
[0071]流量控制器为数据分组分配流量控制器的输出端口，将数据分组传输到该输出端
□ O
[0072]步骤5.路由节点接收数据分组。
[0073]与流量控制器输出端口相连的路由节点的相应路由端口方向接收数据分组。
[0074]步骤6.判断路由节点是否为目的节点。
[0075]若当前路由节点是目的节点，则执行步骤8，否则执行步骤7。
[0076]步骤7.路由节点计算输出端口方向。
[0077]若数据分组在本路由节点的输入方向为东方向，则输出端口为西端口，将数据分组传输到该输出端口方向，执行步骤3;若数据分组在本路由节点的输入方向为西方向，则输出端口为东端口，将数据分组传输到该输出端口方向，执行步骤3 ;若数据分组在本路由节点的输入方向为南方向，则输出端口为北端口，将数据分组传输到该输出端口方向，执行步骤3;若数据分组在本路由节点的输入方向为北方向，则输出端口为南端口，将数据分组传输到该输出端口方向，执行步骤3 ；
[0078]该步骤中，数据分组在路由节点内的传输方向不允许拐弯，即数据分组输入端口方向为西方向则输出端口方向为东输出端口，数据分组输入端口方向为东方向则输出端口方向为西输出端口，数据分组输入端口方向为南方向则输出端口方向为北输出端口，数据分组输入端口方向为北方向则输出端口方向为南输出端口。这样避免了死锁的产生，并且路由计算简单所需要的硬件开销小。
[0079]步骤8.将数据分组传输到本地输出端口，路由结束。
[0080]参照附图3对本路由方法中的本地注入方向选择方法作进一步的描述，具体步骤为:
[0081]步骤2a.计算数据分组的输出端口集合。
[0082]路由节点计算数据分组的输出端口集合:
[0083]若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有东方向，执行步骤2d ；
[0084]若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有西方向，执行步骤2d ；
[0085]若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合只有南方向，执行步骤2d ；
[0086]若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合只有北方向，执行步骤2d;
[0087]若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有东方向和南方向，执行步骤2b ；
[0088]若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有东方向和北方向，执行步骤2b ；
[0089]若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有西方向和南方向，执行步骤2b ；
[0090]若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有西方向和北方向，执行步骤2b ；
[0091]步骤2b.计算四个输出方向的拥塞信息。
[0092]本地端口最后一次注入到东方向、西方向、南方向和北方向的数据分组所等待的时钟周期数作为当前注入选择的拥塞信息，分别存储在四个方向的排队等待时间寄存器里。
[0093]该步骤中，采用本地端接口最后一次到四个输出端口方向的等待时间作为每个输出端口方向的注入拥塞选择信息，这样只需要计数器就可以实现而不需要其它额外的硬件开销，使得硬件开销小。
[0094]步骤2c.选择输出端口集合里拥塞较小的作为注入方向。
[0095]根据步骤2a中路由节点计算产生的输出端口集合以及步骤2b中计算产生的拥塞信息，选择输出端口集合里具有较小时钟周期等待数的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出端口方向，注入结束。
[0096]步骤2d.将数据分组注入到该方向。
[0097]将输出端口集合里的方向作为数据分组的注入方向，将数据分组注入到该路由输出端口方向，注入结束。
[0098]参照附图4对本发明自适应路由方法中流量控制器输出端口分配方法作进一步的描述，具体步骤为:
[0099]步骤4a.判断数据分组的优先级:
[0100]若该数据分组的目的节点和该流量控制器相连，则该数据分组具有高优先级，执行步骤4b ；
[0101]若该数据分组的目的节点和该流量控制器没有相连，则该数据分组具有低优先级，执行步骤4c。
[0102]该步骤中所述的目的节点是否与该流量控制器相连，是指目的节点与流量控制器的非接收数据分组端相连，例如若路由节点将本地端口的数据分组传输给与路由节点的南端口相连的垂直流量控制器，即垂直流量控制器的上端为数据分组接收端，非数据分组接收端则为垂直流量控制器的下端，若路由节点将本地端口的数据分组传输给与路由节点的北端口相连的垂直流量控制器，即垂直流量控制器的下端为数据分组接收端，非数据分组接收端则为垂直流量控制器的上端，水平流量控制器类似。
[0103]步骤4b.直接分配输出端口并发分配信息给拥塞信息收集器，分配结束。
[0104]流量控制器将与目的节点相连的流量控制器输出端口分配给数据分组，同时把该输出端口分配信息作为高优先级拥塞信息发给拥塞信息收集器，流量控制器输出端口分配结束。
[0105]步骤4c.计算其余输入端口高优先级拥塞信息并发给拥塞信息收集器。
[0106]流量控制器计算其余所有输入端口数据分组的优先级，把所有高优先级数据分组的输出端口请求信号作为高优先级拥塞信息发给拥塞信息收集器。
[0107]步骤4d.计算本地拥塞信息并发给拥塞信息收集器。
[0108]流量控制器计算当前流量控制器被使用的输出端口作为本地拥塞信息发给拥塞信息收集器。
[0109]该步骤中当前流量控制器被使用的输出端口，表示的是输出端口中有数据分组传输，即该输出端口不能分配给当前数据分组。
[0110]步骤4e.计算区域拥塞信息并发给拥塞信息收集器。
[0111]计算该数据分组下一个流量控制器的输入链路状态，如果可用则为不拥塞，反之为拥塞，将其作为局部拥塞信息发给拥塞信息收集器。
[0112]该步骤中数据分组下一个流量控制器是指，数据分组没有到达目的节点需要通过路由节点和流量控制器继续传输，下一个传输数据分组的流量控制器为所述的下一个流量控制器。该自适应路由方法中，数据分组只能在一种流量控制器中传输，即数据分组在到达目的节点之前要么一直在水平流量控制器中传输，要么一直在垂直流量控制器中传输，而不能在传输过程中通过两种流量控制器传输。
[0113]步骤4f.拥塞信息收集器计算可分配输 出端口。
[0114]拥塞信息收集器根据收集到的拥塞信息以及数据分组的优先级别，为数据分组计算可分配的剩余还没有高优先级请求并且没有拥塞的输出端口。
[0115]该步骤中，首先排除掉输入端口中所有高优先级数据分组所请求的流量控制器输出端口(即为高优先级拥塞信息)，然后排除掉被使用的流量控制器输出端口(即为本地拥塞信息)，最后排除掉下一个流量控制器被使用的输入端口与路由节点相连的当前流量控制器的输出端口(即为区域拥塞信息)，剩下的即为空闲的可以分配的流量控制器输出端口。采用这种方法，使得低优先级数据分组可以从路由节点连续传输两个流量控制器到达第二个流量控制器的输入端口，传输过程中没有拥塞；使得高优先级数据分组直接通过流量控制器到达目的节点，传输过程中没有拥塞。这种拥塞方法很好的控制了数据分组在传输过程中的拥塞，从而提高了网络吞吐率，降低了网络延迟，提高了网络性能。
[0116]步骤4g.流量控制器分配输出端口。
[0117]流量控制器为数据分组分配步骤4f中计算得到的可以分配的空闲输出端口:
[0118]若没有可分配的输出端口，数据分组被阻塞，等待可分配的输出端口可用；
[0119]若有I个可分配的输出端口，流量控制器为数据分组分配该端口，分配结束；
[0120]若有超过I个可分配的输出端口，则可分配的输出端口按照轮询方法为数据分组分配，即假设有1、2、3三个可分配的输出端口，该输入端口不同的数据分组(可分配输出端口均为1、2、3端口)按照顺序依次分配1、2、3端口并进行循环，分配结束。
【主权项】
1.一种基于二维片上网络拓扑结构的自适应路由方法，其特征在于包括如下步骤: (1)源节点本地端口接收数据分组； (2)源节点根据本地注入方向选择方法所得到的注入方向的结果，将数据分组从本地端口注入到该输出端口方向； (3)与路由节点输出方向相连的流量控制器端口接收数据分组； (4)为数据分组分配流量控制器的输出端口，根据流量控制器的输出端口分配方法所得到的分配结果将数据分组传输到该输出端口； (5)与流量控制器输出端口相连的路由节点的路由端口接收数据分组； (6)判断路由节点是否为目的节点: (6a)若该节点的坐标与目的节点的坐标相同，则执行步骤(8); (6b)若该节点的坐标与目的节点的坐标不相同，则执行步骤(7); (7)路由节点计算输出端口方向，然后返回执行步骤(3); (8)路由节点将数据分组传输到本地输出端口，路由结束。2.根据权利要求1所述的基于二维片上网络拓扑结构的自适应路由方法，其特征在于，步骤(2)中所述的本地注入方向选择方法是指:源节点的本地端口接收到数据分组后根据数据分组目的节点的坐标信息和本地拥塞信息选择要注入的端口方向，其具体步骤为: (2a)路由节点计算数据分组的输出端口集合: (2a_l)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有东方向，执行步骤(2d)； (2a_2)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标等于源节点的纵坐标，则输出端口集合只有西方向，执行步骤(2d); (2a_3)若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合只有南方向，执行步骤(2d)； (2a-4)若目的节点的横坐标等于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合只有北方向，执行步骤(2d); (2a-5)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有东方向和南方向，执行步骤(2b)； (2a-6)若目的节点的横坐标大于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有东方向和北方向，执行步骤(2b)； (2a-7)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标大于源节点的纵坐标，则输出端口集合有西方向和南方向，执行步骤(2b)； (2a-8)若目的节点的横坐标小于源节点的横坐标并且目的节点的纵坐标小于源节点的纵坐标，则输出端口集合有西方向和北方向，执行步骤(2b)； (2b)计算四个路由输出端口方向的拥塞信息:将本地端口最后一次注入到东方向、西方向、南方向和北方向的数据分组所等待的时钟周期数作为当前注入选择的拥塞信息，分别存储在四个方向的排队等待时间寄存器里；(2c)根据步骤(2a)中路由节点计算产生的输出端口集合以及步骤(2b)中得到的拥塞信息，选择输出端口集合里具有较小时钟周期等待数的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出端口方向，注入结束； (2d)将输出端口集合里的方向作为数据分组的注入方向，将数据分组从本地端口注入到该输出〗而口方向，注入结束。3.根据权利要求1所述的基于二维片上网络拓扑结构的自适应路由方法，其特征在于，步骤(4)中所述的流量控制器的输出端口分配方法是指:流量控制器接收到路由节点的数据分组后根据计算出来的本地拥塞信息、区域拥塞信息以及高优先级拥塞信息三部分进行流量控制器的输出端口选择，具体步骤为: (4a)判断输入端口数据分组的优先级: (4a-l)若该数据分组的目的节点和该流量控制器相连，则该数据分组具有高优先级，执行步骤(4b)； (4a-2)若该数据分组的目的节点和该流量控制器没有相连，则该数据分组具有低优先级，执行步骤(4c)； (4b)将与目的节点相连的流量控制器输出端口分配给数据分组，将数据分组传输到该输出端口，同时把该输出端口分配信息作为高优先级拥塞信息发给拥塞信息收集器； (4c)计算该流量控制器其余所有输入端口所接收到的数据分组的优先级，把所有高优先级数据分组的输出端口请求信号作为高优先级拥塞信息发给拥塞信息收集器； (4d)计算当前流量控制器被使用的输出端口作为本地拥塞信息发给拥塞信息收集器; (4e)计算该数据分组下一个流量控制器的输入链路状态，如果空闲则为不拥塞，反之为拥塞，将其作为局部拥塞信息发给拥塞信息收集器； (4f)拥塞信息收集器根据收集到的拥塞信息以及数据分组的优先级别，为数据分组计算可分配的剩余还没有高优先级请求并且没有拥塞的输出端口； (4g)输出端口分配器为数据分组分配输出端口: (4g-l)若没有可分配的输出端口，数据分组被阻塞，等待可分配的输出端口可用；(4g-2)若有I个可分配的输出端口，输出端口分配器为数据分组分配该端口，将数据分组传输到该输出端口； (4g-3)若有超过I个可分配的输出端口，则可分配的输出端口按照轮询方法为数据分组分配，将数据分组传输到该输出端口。
【专利摘要】本发明公开了一种基于二维片上网络拓扑结构的自适应路由方法，用于解决传统二维片上网络路由方法无法有效避免拥塞节点或者避免拥塞节点时硬件开销大效率低导致网络性能低下的问题。本发明的自适应路由方法采用了注入方向选择和流量控制器输出端口分配相结合的方法。本发明的自适应路由方法具体步骤为：1.源节点本地端口接收数据分组；2.数据分组的注入；3.流量控制器接收数据分组；4.流量控制器输出端口分配；5.路由节点接收数据分组；6.判断路由节点是否为目的节点；7.路由节点计算输出端口方向；8.数据分组传输到目的节点本地输出端口。该路由方法是一种具有良好拥塞控制能力且无死锁、硬件开销小的自适应路由方法。
【IPC分类】H04L12/833, G06F15/78, H04L12/801
【公开号】CN104901899
【申请号】CN201510342328
【发明人】史江义, 舒浩, 李钊, 马佩军, 王禛, 吴冰冰, 余文哲, 张春焱
【申请人】西安电子科技大学
【公开日】2015年9月9日
【申请日】2015年6月18日
最新回复(0)