CN105072032B - A kind of method and system of definite network-on-chip routed path - Google Patents
A kind of method and system of definite network-on-chip routed path Download PDFInfo
- Publication number
- CN105072032B CN105072032B CN201510594792.4A CN201510594792A CN105072032B CN 105072032 B CN105072032 B CN 105072032B CN 201510594792 A CN201510594792 A CN 201510594792A CN 105072032 B CN105072032 B CN 105072032B
- Authority
- CN
- China
- Prior art keywords
- horizontal
- destination node
- nodes
- total number
- move
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 42
- 235000008694 Humulus lupulus Nutrition 0.000 claims abstract description 49
- 239000000872 buffer Substances 0.000 claims description 12
- 238000004364 calculation method Methods 0.000 claims description 10
- 238000009826 distribution Methods 0.000 abstract description 12
- 230000000694 effects Effects 0.000 abstract description 7
- 238000010586 diagram Methods 0.000 description 4
- 230000003044 adaptive effect Effects 0.000 description 3
- 230000006870 function Effects 0.000 description 3
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 238000004458 analytical method Methods 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000004519 manufacturing process Methods 0.000 description 1
- 230000008569 process Effects 0.000 description 1
- 230000000750 progressive effect Effects 0.000 description 1
- 238000003860 storage Methods 0.000 description 1
Landscapes
- Data Exchanges In Wide-Area Networks (AREA)
Abstract
本发明公开了一种确定片上网络路由路径的方法及系统，包括：从源节点所在的垂直总线上移动到目的节点所在的垂直总线上，到达目的水平层的第一位置；根据所述第一位置的水平位置值与所述目的节点的水平位置值，计算得到所述第一位置到所述目的节点的水平跳数；根据所述水平跳数与所述水平层的节点总数，按照预定水平层路由算法，得到从所述第一位置到达所述目的节点的水平路径；该方法及系统能够根据网络状态动态调整路由路径，实际效果表明该方法可以提高吞吐量和降低网路延时，平衡网络中的流量分布。
The present invention discloses a method and system for determining the routing path of an on-chip network. The horizontal position value of the position and the horizontal position value of the destination node are calculated to obtain the number of horizontal hops from the first position to the destination node; according to the number of horizontal hops and the total number of nodes in the horizontal layer, according to a predetermined level layer routing algorithm to obtain the horizontal path from the first position to the destination node; the method and system can dynamically adjust the routing path according to the network status, and the actual effect shows that the method can improve throughput and reduce network delay, balance Traffic distribution in the network.
Description
技术领域technical field
本发明涉及芯片体系结构领域，特别涉及一种确定片上网络路由路径的方法及系统。The invention relates to the field of chip architecture, in particular to a method and a system for determining an on-chip network routing path.
背景技术Background technique
三维片上网络是在三维集成电路工艺和二维片上网络的基础上发展起来的，主要用于解决高集成度芯片通信瓶颈等问题。三维片上网络(network on a chip，noc)垂直连线与水平连线上存在结构差异，水平层内部连线需要横跨资源节点与其它路由单元相连，连线长度为资源节点宽度，其典型值为数千微米，而三维集成电路工艺允许水平层直接相互叠加，使得在垂直方向上的距离仅为几十微米。V-Spidergon三维拓扑结构是一种混合型三维拓扑，该结构的垂直总线深刻影响拓扑的性能。由于三维集成电路生产工艺的限制，只能在垂直方向上连接水平子层，水平子层间的资源节点无法斜向连接。因此，如何使得片上网络路由路径最优，是本领域技术人员需要解决的技术问题。The 3D on-chip network is developed on the basis of the three-dimensional integrated circuit technology and the two-dimensional on-chip network, and is mainly used to solve problems such as communication bottlenecks of highly integrated chips. There are structural differences between the vertical connection and the horizontal connection of the three-dimensional network on a chip (noc). The internal connection of the horizontal layer needs to cross the resource node and connect to other routing units. The length of the connection is the width of the resource node, and its typical value is The three-dimensional integrated circuit process allows horizontal layers to be directly stacked on each other, so that the distance in the vertical direction is only tens of microns. The V-Spidergon three-dimensional topology is a hybrid three-dimensional topology, and the vertical bus of the structure deeply affects the performance of the topology. Due to the limitation of the production process of the three-dimensional integrated circuit, the horizontal sub-layers can only be connected in the vertical direction, and the resource nodes between the horizontal sub-layers cannot be connected obliquely. Therefore, how to optimize the routing path of the network on chip is a technical problem to be solved by those skilled in the art.
发明内容Contents of the invention
本发明的目的是提供一种确定片上网络路由路径的方法，该方法能够根据网络状态动态调整路由路径，实际效果表明该方法可以提高吞吐量和降低网路延时，平衡网络中的流量分布；此外本发明的另一目的是提供一种确定片上网络路由路径的系统。The purpose of the present invention is to provide a method for determining the routing path of the on-chip network. The method can dynamically adjust the routing path according to the network status. The actual effect shows that the method can improve throughput and reduce network delay, and balance the traffic distribution in the network; Furthermore, another object of the present invention is to provide a system for determining a network-on-chip routing path.
为解决上述技术问题，本发明提供一种确定片上网络路由路径的方法，包括：In order to solve the above-mentioned technical problems, the present invention provides a method for determining a network-on-chip routing path, including:
从源节点所在的垂直总线上移动到目的节点所在的垂直总线上，到达目的水平层的第一位置；Move from the vertical bus where the source node is located to the vertical bus where the destination node is located, and reach the first position of the destination horizontal layer;
根据所述第一位置的水平位置值与所述目的节点的水平位置值，计算得到所述第一位置到所述目的节点的水平跳数；calculating the number of horizontal hops from the first position to the destination node according to the horizontal position value of the first position and the horizontal position value of the destination node;
根据所述水平跳数与所述水平层的节点总数，按照预定水平层路由算法，得到从所述第一位置到达所述目的节点的水平路径。According to the number of horizontal hops and the total number of nodes in the horizontal layer, a horizontal path from the first position to the destination node is obtained according to a predetermined horizontal layer routing algorithm.
优选的，所述预定水平层路由算法包括：第一预定算法，其中，所述第一预定算法包括：Preferably, the predetermined horizontal layer routing algorithm includes: a first predetermined algorithm, wherein the first predetermined algorithm includes:
将所述水平跳数与所述水平层的节点总数相除；dividing the number of horizontal hops by the total number of nodes in the horizontal layer;
当相除的结果不大于四分之一所述水平层的节点总数时，按照逆时针移动到所述目的节点；When the result of the division is not greater than a quarter of the total number of nodes in the horizontal layer, move counterclockwise to the destination node;
当相除的结果不小于四分之三所述水平层的节点总数时，按照顺时针移动到所述目的节点；When the result of the division is not less than three quarters of the total number of nodes in the horizontal layer, move clockwise to the destination node;
当相除的结果大于四分之一且小于二分之一所述水平层的节点总数时，将所述第一位置移动到对面的第二位置，将所述第二位置按照顺时针移动到所述目的节点；其中，所述移动到对面中间节点具体为：计算出所述第一位置到距所述目的节点具有二分之一所述水平层的节点总数的中间节点的跳数，将所述第一位置移动到按顺时针距所述目的节点具有相同跳数的第二位置；When the result of the division is greater than 1/4 and less than 1/2 of the total number of nodes in the horizontal layer, move the first position to the opposite second position, and move the second position clockwise to The destination node; wherein, the moving to the opposite intermediate node is specifically: calculating the number of hops from the first position to the intermediate node having half the total number of nodes in the horizontal layer from the destination node, and The first location is moved to a second location with the same number of hops clockwise from the destination node;
当相除的结果小于四分之三且大于二分之一所述水平层的节点总数时，将所述第一位置移动到对面的第二位置，将所述第二位置按照逆时针移动到所述目的节点；When the result of the division is less than three-quarters and greater than one-half of the total number of nodes in the horizontal layer, move the first position to the opposite second position, and move the second position counterclockwise to said destination node;
当相除的结果等于二分之一所述水平层的节点总数时，将所述第一位置移动到所述目的节点。When the result of the division is equal to half of the total number of nodes in the horizontal layer, the first position is moved to the destination node.
优选的，所述预定水平层路由算法包括：第二预定算法，其中，所述第二预定算法包括：Preferably, the predetermined horizontal layer routing algorithm includes: a second predetermined algorithm, wherein the second predetermined algorithm includes:
将所述水平跳数与所述水平层的节点总数相除；dividing the number of horizontal hops by the total number of nodes in the horizontal layer;
当相除的结果不大于四分之一所述水平层的节点总数时，按照逆时针移动到所述目的节点；When the result of the division is not greater than a quarter of the total number of nodes in the horizontal layer, move counterclockwise to the destination node;
当相除的结果不小于四分之三所述水平层的节点总数时，按照顺时针移动到所述目的节点；When the result of the division is not less than three quarters of the total number of nodes in the horizontal layer, move clockwise to the destination node;
当相除的结果大于四分之一且小于二分之一所述水平层的节点总数时，将所述第一位置按照顺时针移动到距所述目的节点具有二分之一所述水平层的节点总数的中间节点，从所述中间节点移动到所述目的节点；When the result of the division is greater than 1/4 and less than 1/2 of the total number of nodes in the horizontal layer, move the first position clockwise to the destination node with 1/2 of the horizontal layer an intermediate node of the total number of nodes, moving from the intermediate node to the destination node;
当相除的结果小于四分之三且大于二分之一所述水平层的节点总数时，将所述第一位置按照逆时针移动到距所述目的节点具有二分之一所述水平层的节点总数的中间节点，从所述中间节点移动到所述目的节点；When the result of the division is less than three-quarters and greater than one-half of the total number of nodes in the horizontal layer, the first position is moved counterclockwise to the distance from the destination node with one-half of the horizontal layer an intermediate node of the total number of nodes, moving from the intermediate node to the destination node;
当相除的结果等于二分之一所述水平层的节点总数时，将所述第一位置移动到所述目的节点。When the result of the division is equal to half of the total number of nodes in the horizontal layer, the first position is moved to the destination node.
优选的，所述预定水平层路由算法包括第一预定算法和第二预定算法，还包括：Preferably, the predetermined horizontal layer routing algorithm includes a first predetermined algorithm and a second predetermined algorithm, and further includes:
当存在所述第一位置到所述目的节点的路径跳数相同时，比较两条路径的输出端口的缓存使用量，并使用缓存使用量小的输出端口所在路径，将所述第一位置移动到所述目的节点。When there is the same number of path hops from the first location to the destination node, compare the cache usage of the output ports of the two paths, and use the path where the output port with the smaller cache usage is used to move the first location to the destination node.
优选的，还包括：Preferably, it also includes:
在垂直方向建立两路虚通道；Establish two virtual channels in the vertical direction;
当所述源节点的垂直位置值大于所述目的节点的垂直位置值，则使用第一虚通道；When the vertical position value of the source node is greater than the vertical position value of the destination node, the first virtual channel is used;
当所述源节点的垂直位置值小于所述目的节点的垂直位置值，则使用第二虚通道；When the vertical position value of the source node is smaller than the vertical position value of the destination node, use the second virtual channel;
和/或，在水平方向建立两路虚通道；And/or, establish two virtual channels in the horizontal direction;
当所述第一位置的水平位置值大于所述目的节点的水平位置值，则使用第一虚通道；When the horizontal position value of the first position is greater than the horizontal position value of the destination node, the first virtual channel is used;
当所述第一位置的水平位置值小于所述目的节点的水平位置值，则使用第二虚通道。When the horizontal position value of the first position is smaller than the horizontal position value of the destination node, the second virtual channel is used.
优选的，还包括：Preferably, it also includes:
当垂直总线负载大于阈值时，通过水平子层确定空闲总线。When the vertical bus load is greater than a threshold, a free bus is determined by the horizontal sublayer.
本发明提供一种确定片上网络路由路径的系统，包括：The present invention provides a system for determining an on-chip network routing path, including:
垂直移动模块，用于从源节点所在的垂直总线上移动到目的节点所在的垂直总线上，到达目的水平层的第一位置；The vertical movement module is used to move from the vertical bus where the source node is located to the vertical bus where the destination node is located, to reach the first position of the destination horizontal layer;
计算模块，用于根据所述第一位置的水平位置值与所述目的节点的水平位置值，计算得到所述第一位置到所述目的节点的水平跳数；A calculation module, configured to calculate the number of horizontal hops from the first position to the destination node according to the horizontal position value of the first position and the horizontal position value of the destination node;
水平移动模块，用于根据所述水平跳数与所述水平层的节点总数，按照预定水平层路由算法，得到从所述第一位置到达所述目的节点的水平路径。A horizontal movement module, configured to obtain a horizontal path from the first location to the destination node according to the number of horizontal hops and the total number of nodes in the horizontal layer according to a predetermined horizontal layer routing algorithm.
优选的，所述水平移动模块包括：第一预定算法单元，其中，所述第一预定算法单元包括：Preferably, the horizontal movement module includes: a first predetermined algorithm unit, wherein the first predetermined algorithm unit includes:
第一计算单元，用于将所述水平跳数与所述水平层的节点总数相除；a first calculation unit, configured to divide the number of horizontal hops by the total number of nodes in the horizontal layer;
第一移动单元，用于当相除的结果不大于四分之一所述水平层的节点总数时，按照逆时针移动到所述目的节点；当相除的结果不小于四分之三所述水平层的节点总数时，按照顺时针移动到所述目的节点；当相除的结果大于四分之一且小于二分之一所述水平层的节点总数时，将所述第一位置移动到对面的第二位置，将所述第二位置按照顺时针移动到所述目的节点；其中，所述移动到对面中间节点具体为：计算出所述第一位置到距所述目的节点具有二分之一所述水平层的节点总数的中间节点的跳数，将所述第一位置移动到按顺时针距所述目的节点具有相同跳数的第二位置；当相除的结果小于四分之三且大于二分之一所述水平层的节点总数时，将所述第一位置移动到对面的第二位置，将所述第二位置按照逆时针移动到所述目的节点；当相除的结果等于二分之一所述水平层的节点总数时，将所述第一位置移动到所述目的节点。The first mobile unit is used to move to the destination node counterclockwise when the result of the division is not greater than 1/4 of the total number of nodes in the horizontal layer; when the result of the division is not less than 3/4 of the When the total number of nodes in the horizontal layer, move to the destination node clockwise; when the result of the division is greater than 1/4 and less than 1/2 of the total number of nodes in the horizontal layer, move the first position to For the second position on the opposite side, move the second position clockwise to the destination node; wherein, the moving to the opposite intermediate node is specifically: calculate the first position to be 2 points away from the destination node The number of hops of the intermediate node of the total number of nodes in one of the horizontal layers, the first position is moved to the second position with the same number of hops clockwise away from the destination node; when the result of the division is less than 1/4 When three and more than one-half of the total number of nodes in the horizontal layer, move the first position to the opposite second position, and move the second position counterclockwise to the destination node; when the divided When the result is equal to half of the total number of nodes in the horizontal layer, move the first position to the destination node.
优选的，所述水平移动模块包括：第二预定算法单元，其中，所述第一预定算法单元包括：Preferably, the horizontal movement module includes: a second predetermined algorithm unit, wherein the first predetermined algorithm unit includes:
第二计算单元，用于将所述水平跳数与所述水平层的节点总数相除；a second calculation unit, configured to divide the number of horizontal hops by the total number of nodes in the horizontal layer;
第二移动单元，用于当相除的结果不大于四分之一所述水平层的节点总数时，按照逆时针移动到所述目的节点；当相除的结果不小于四分之三所述水平层的节点总数时，按照顺时针移动到所述目的节点；当相除的结果大于四分之一且小于二分之一所述水平层的节点总数时，将所述第一位置按照顺时针移动到距所述目的节点具有二分之一所述水平层的节点总数的中间节点，从所述中间节点移动到所述目的节点；当相除的结果小于四分之三且大于二分之一所述水平层的节点总数时，将所述第一位置按照逆时针移动到距所述目的节点具有二分之一所述水平层的节点总数的中间节点，从所述中间节点移动到所述目的节点；当相除的结果等于二分之一所述水平层的节点总数时，将所述第一位置移动到所述目的节点。The second mobile unit is used to move to the destination node counterclockwise when the result of the division is not greater than 1/4 of the total number of nodes in the horizontal layer; when the result of the division is not less than 3/4 of the When the total number of nodes in the horizontal layer, move to the destination node clockwise; when the result of the division is greater than one-fourth and less than one-half of the total number of nodes in the horizontal layer, move the first position in order Hour hand moves to the intermediate node that has the node total number of 1/2 described horizontal layer apart from described purpose node, moves to described purpose node from described intermediate node; When the result of dividing is less than three-quarters and greater than half When the total number of nodes in one of the horizontal layers, move the first position counterclockwise to an intermediate node that has half the total number of nodes in the horizontal layer from the destination node, and move from the intermediate node to The destination node; when the result of the division is equal to half of the total number of nodes in the horizontal layer, moving the first position to the destination node.
优选的，同时具有所述第一预定算法单元和所述第二预定算法单元，还包括：Preferably, having both the first predetermined algorithm unit and the second predetermined algorithm unit also includes:
选择模块，用于当存在所述第一位置到所述目的节点的路径跳数相同时，比较两条路径的输出端口的缓存使用量，并使用缓存使用量小的输出端口所在路径，将所述第一位置移动到所述目的节点。A selection module, configured to compare the buffer usage of the output ports of the two paths when there are paths from the first position to the destination node with the same number of hops, and use the path where the output port with the smallest buffer usage is located to select all The first location is moved to the destination node.
本发明所提供的确定片上网络路由路径的方法及系统，包括：从源节点所在的垂直总线上移动到目的节点所在的垂直总线上，到达目的水平层的第一位置；根据所述第一位置的水平位置值与所述目的节点的水平位置值，计算得到所述第一位置到所述目的节点的水平跳数；根据所述水平跳数与所述水平层的节点总数，按照预定水平层路由算法，得到从所述第一位置到达所述目的节点的水平路径；The method and system for determining the routing path of the on-chip network provided by the present invention include: moving from the vertical bus where the source node is located to the vertical bus where the destination node is located, and reaching the first position of the target horizontal layer; according to the first position The horizontal position value of the horizontal position value and the horizontal position value of the destination node, calculate the horizontal hop number from the first position to the destination node; according to the horizontal jump number and the total number of nodes in the horizontal layer, according to the predetermined horizontal layer a routing algorithm to obtain a horizontal path from the first position to the destination node;
该方法及系统能够将数据包首先在垂直方向进行确定性路由，到达目的层之后再根据链路利用率自适应选择二维路由算法路由到目的节点，可以平衡网络中的流量分布。根据网络状态动态调整路由路径，实际效果表明该方法可以提高吞吐量和降低网路延时，平衡网络中的流量分布。The method and system can deterministically route the data packets in the vertical direction first, and then adaptively select a two-dimensional routing algorithm to route to the destination node according to the link utilization rate after reaching the destination layer, which can balance the traffic distribution in the network. The routing path is dynamically adjusted according to the network status. The actual results show that this method can improve throughput, reduce network delay, and balance traffic distribution in the network.
附图说明Description of drawings
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据提供的附图获得其他的附图。In order to more clearly illustrate the technical solutions in the embodiments of the present invention or the prior art, the following will briefly introduce the drawings that need to be used in the description of the embodiments or the prior art. Obviously, the accompanying drawings in the following description are only It is an embodiment of the present invention, and those skilled in the art can also obtain other drawings according to the provided drawings without creative work.
图1为本发明实施例所提供的确定片上网络路由路径的方法的流程图；FIG. 1 is a flow chart of a method for determining a network-on-chip routing path provided by an embodiment of the present invention;
图2为本发明实施例所提供的第一预定算法效果的示意图；Fig. 2 is a schematic diagram of the effect of the first predetermined algorithm provided by the embodiment of the present invention;
图3为本发明实施例所提供的第二预定算法效果的示意图；Fig. 3 is a schematic diagram of the effect of the second predetermined algorithm provided by the embodiment of the present invention;
图4为本发明实施例所提供的确定片上网络路由路径的系统的结构框图。Fig. 4 is a structural block diagram of a system for determining a network-on-chip routing path provided by an embodiment of the present invention.
具体实施方式Detailed ways
本发明的核心是提供一种确定片上网络路由路径的方法，该方法能够根据网络状态动态调整路由路径，实际效果表明该方法可以提高吞吐量和降低网路延时，平衡网络中的流量分布。The core of the present invention is to provide a method for determining the routing path of the on-chip network. The method can dynamically adjust the routing path according to the network state. The actual effect shows that the method can improve throughput, reduce network delay, and balance traffic distribution in the network.
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。In order to make the purpose, technical solutions and advantages of the embodiments of the present invention clearer, the technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the drawings in the embodiments of the present invention. Obviously, the described embodiments It is a part of embodiments of the present invention, but not all embodiments. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.
请参考图1，图1为本发明实施例所提供的确定片上网络路由路径的方法的流程图，该方法可以包括：Please refer to FIG. 1. FIG. 1 is a flow chart of a method for determining a network-on-chip routing path provided by an embodiment of the present invention. The method may include:
步骤s100、从源节点所在的垂直总线上移动到目的节点所在的垂直总线上，到达目的水平层的第一位置；Step s100, moving from the vertical bus where the source node is located to the vertical bus where the destination node is located, to reach the first position of the destination horizontal layer;
步骤s110、根据所述第一位置的水平位置值与所述目的节点的水平位置值，计算得到所述第一位置到所述目的节点的水平跳数；Step s110, calculating the number of horizontal hops from the first position to the destination node according to the horizontal position value of the first position and the horizontal position value of the destination node;
步骤s120、根据所述水平跳数与所述水平层的节点总数，按照预定水平层路由算法，得到从所述第一位置到达所述目的节点的水平路径。Step s120, according to the number of horizontal hops and the total number of nodes in the horizontal layer, and according to a predetermined horizontal layer routing algorithm, obtain a horizontal path from the first location to the destination node.
其中，该方法首先使得数据包在垂直层面上到达目的节点所在的数据总线上，在根据在水平层面上计算得到的从第一位置到目的节点所需要的跳数，根据该跳数与水平层面上的节点总数即最大的跳数的关系，利用预定水平层路由算法可以找到水平方向的路径；因此可以看出来，该预定水平算法决定着在水平层面上路径的实际情况，该算法的效率决定了片上网络路由路径效率。Wherein, the method first makes the data packet arrive at the data bus where the destination node is located on the vertical level, and according to the number of hops required from the first position to the destination node calculated on the horizontal level, according to the number of hops and the horizontal level The relationship between the total number of nodes on the network and the maximum number of hops, the horizontal path can be found by using the predetermined level routing algorithm; therefore, it can be seen that the predetermined level algorithm determines the actual situation of the path on the horizontal level, and the efficiency of the algorithm determines The network-on-chip routing path efficiency is improved.
通过举例对该方法进行说明：This method is illustrated by an example:
设网络中的节点位置为(i,j)，i表示节点在水平层的位置，j表示其在垂直方向的位置。节点在水平层方向的位置按顺时针方向编号。如果源节点(isrc,jsrc)与目标节点(idest,jdest)在垂直方向的距离|jdest-jsrc|不等于0，则优先在垂直方向路由使|jdest-jsrc|等于0，然后在水平层根据最短路径原则选择出口。算法按如下公式计算当前节点和目的节点在水平层上的距离：Let the node position in the network be (i, j), where i represents the position of the node in the horizontal layer, and j represents its position in the vertical direction. The position of nodes in the horizontal layer direction is numbered clockwise. If the distance between the source node (i src , j src ) and the destination node (i dest , j dest ) in the vertical direction |j dest -j src | is not equal to 0, the priority is to route in the vertical direction so that |j dest -j src | Equal to 0, then choose the exit according to the shortest path principle in the horizontal layer. The algorithm calculates the distance between the current node and the destination node on the horizontal layer according to the following formula:
Dist＝((idest-isrc)+m)mod mDist＝((i dest -i src )+m)mod m
上式中m表示在水平层上的节点数目。实际上，Dist表示当前节点和目标节点在顺时针方向的水平跳数。其中，这里是使用取模的方式进行计算，当然也可以用其他方式获取目的节点和第一位置在水平层面的跳数。In the above formula, m represents the number of nodes on the horizontal layer. In fact, Dist represents the number of horizontal hops between the current node and the target node in the clockwise direction. Wherein, here, the method of modulo is used for calculation, and of course other methods may also be used to obtain the number of hops at the horizontal level between the destination node and the first position.
优选的，所述预定水平层路由算法可以包括：第一预定算法和/或第二预定算法；其中，本发明可以只有第一预定算法，也可以只有第二预定算法，当然也可以两者都有。本发明在此只是举例。这两种算法，一种是路由单元优先使用连接到对面节点的通道，如果目的节点与源节点在环上的距离不超过环上节点总数的一半，则数据包可以根据最短路径原则选择顺时针或者逆时针方向作为通道出口。如果目的节点与源节点在环上的距离超过环上节点总数的一半，则数据包首先通过连接到对面节点的通道路由到环上的对面节点，再选择最短路径路由。第二种选择与第一种相反数据包首先被路由到与目的节点相对的节点，再通过对面通道路由到目的节点。Preferably, the predetermined horizontal layer routing algorithm may include: a first predetermined algorithm and/or a second predetermined algorithm; wherein, the present invention may only have the first predetermined algorithm, or only the second predetermined algorithm, or both Have. The invention is presented here by way of example only. These two algorithms, one is that the routing unit preferentially uses the channel connected to the opposite node, if the distance between the destination node and the source node on the ring does not exceed half of the total number of nodes on the ring, the data packet can be selected clockwise according to the shortest path principle Or counterclockwise as the channel exit. If the distance between the destination node and the source node on the ring exceeds half of the total number of nodes on the ring, the data packet is first routed to the opposite node on the ring through the channel connected to the opposite node, and then the shortest path route is selected. The second option is opposite to the first. The data packet is first routed to the node opposite to the destination node, and then routed to the destination node through the opposite channel.
请参考图2，所述第一预定算法可以包括：Please refer to FIG. 2, the first predetermined algorithm may include:
将所述水平跳数与所述水平层的节点总数相除；dividing the number of horizontal hops by the total number of nodes in the horizontal layer;
当相除的结果不大于四分之一所述水平层的节点总数时，按照逆时针移动到所述目的节点；When the result of the division is not greater than a quarter of the total number of nodes in the horizontal layer, move counterclockwise to the destination node;
例如图2中标识1至4的四个方框都是逆时针移动到目的节点0。这里的逆时针可以是列举的一种特殊情况，其可以根据实际情况进行改变，即当相除的结果不大于四分之一所述水平层的节点总数时，按照第一方向移动到所述目的节点；当相除的结果不小于四分之三所述水平层的节点总数时，按照第二方向移动到所述目的节点；后续第一预定算法中的方向都仅为列举，都可以根据用户实际使用的算法进行改变，这里不再一一列举。For example, the four boxes labeled 1 to 4 in FIG. 2 all move counterclockwise to the destination node 0 . The counterclockwise here can be a special case listed, which can be changed according to the actual situation, that is, when the result of the division is not greater than a quarter of the total number of nodes in the horizontal layer, move to the Destination node; when the result of division is not less than three-quarters of the total number of nodes in the horizontal layer, move to the destination node according to the second direction; the directions in the subsequent first predetermined algorithm are only enumerated, and can be based on Algorithms actually used by the user are changed, and will not be listed here.
当相除的结果不小于四分之三所述水平层的节点总数时，按照顺时针移动到所述目的节点；When the result of the division is not less than three quarters of the total number of nodes in the horizontal layer, move clockwise to the destination node;
例如图2中标识12至15的四个方框都是顺时针移动到目的节点0。For example, the four boxes labeled 12 to 15 in FIG. 2 all move clockwise to the destination node 0 .
当相除的结果大于四分之一且小于二分之一所述水平层的节点总数时，将所述第一位置移动到对面的第二位置，将所述第二位置按照顺时针移动到所述目的节点；其中，所述移动到对面中间节点具体为：计算出所述第一位置到距所述目的节点具有二分之一所述水平层的节点总数的中间节点的跳数，将所述第一位置移动到按顺时针距所述目的节点具有相同跳数的第二位置；When the result of the division is greater than 1/4 and less than 1/2 of the total number of nodes in the horizontal layer, move the first position to the opposite second position, and move the second position clockwise to The destination node; wherein, the moving to the opposite intermediate node is specifically: calculating the number of hops from the first position to the intermediate node having half the total number of nodes in the horizontal layer from the destination node, and The first location is moved to a second location with the same number of hops clockwise from the destination node;
例如图2中5、6、7三个位置，若5为第一位置时，将5首先移动到对面的第二位置13，在从13移动到目的节点0。For example, the three positions 5, 6, and 7 in FIG. 2, if 5 is the first position, first move 5 to the opposite second position 13, and then move from 13 to the destination node 0.
当相除的结果小于四分之三且大于二分之一所述水平层的节点总数时，将所述第一位置移动到对面的第二位置，将所述第二位置按照逆时针移动到所述目的节点；When the result of the division is less than three-quarters and greater than one-half of the total number of nodes in the horizontal layer, move the first position to the opposite second position, and move the second position counterclockwise to said destination node;
例如图2中11、10、9三个位置，若10为第一位置时，将10首先移动到对面的第二位置3，在从3移动到目的节点0。For example, the three positions 11, 10, and 9 in Fig. 2, if 10 is the first position, first move 10 to the opposite second position 3, and then move from 3 to the destination node 0.
当相除的结果等于二分之一所述水平层的节点总数时，将所述第一位置移动到所述目的节点；When the result of the division is equal to one-half of the total number of nodes in the horizontal layer, moving the first position to the destination node;
例如图2中标识8的位置移动到目的节点0。For example, the position marked 8 in FIG. 2 is moved to the destination node 0.
其中，还可以将第一预定算法中的逆时针顺序、顺时针顺序进行适应性的变换又是一个新的算法。Wherein, it is also a new algorithm to adaptively transform the counterclockwise order and the clockwise order in the first predetermined algorithm.
请参考图3，所述第二预定算法可以包括：Please refer to FIG. 3, the second predetermined algorithm may include:
将所述水平跳数与所述水平层的节点总数相除；dividing the number of horizontal hops by the total number of nodes in the horizontal layer;
当相除的结果不大于四分之一所述水平层的节点总数时，按照逆时针移动到所述目的节点；When the result of the division is not greater than a quarter of the total number of nodes in the horizontal layer, move counterclockwise to the destination node;
例如图3中标识1至4的四个方框都是逆时针移动到目的节点0。For example, the four boxes marked 1 to 4 in FIG. 3 all move counterclockwise to the destination node 0 .
当相除的结果不小于四分之三所述水平层的节点总数时，按照顺时针移动到所述目的节点；When the result of the division is not less than three quarters of the total number of nodes in the horizontal layer, move clockwise to the destination node;
例如图3中标识12至15的四个方框都是顺时针移动到目的节点0。For example, the four boxes marked 12 to 15 in FIG. 3 all move clockwise to the destination node 0 .
当相除的结果大于四分之一且小于二分之一所述水平层的节点总数时，将所述第一位置按照顺时针移动到距所述目的节点具有二分之一所述水平层的节点总数的中间节点，从所述中间节点移动到所述目的节点；When the result of the division is greater than 1/4 and less than 1/2 of the total number of nodes in the horizontal layer, move the first position clockwise to the destination node with 1/2 of the horizontal layer an intermediate node of the total number of nodes, moving from the intermediate node to the destination node;
例如图3中5、6、7三个位置，若5为第一位置时，将5首先移动到中间节点8，在从8移动到对面的目的节点0。For example, the three positions 5, 6, and 7 in Figure 3, if 5 is the first position, first move 5 to the middle node 8, and then move from 8 to the opposite destination node 0.
当相除的结果小于四分之三且大于二分之一所述水平层的节点总数时，将所述第一位置按照逆时针移动到距所述目的节点具有二分之一所述水平层的节点总数的中间节点，从所述中间节点移动到所述目的节点；When the result of the division is less than three-quarters and greater than one-half of the total number of nodes in the horizontal layer, the first position is moved counterclockwise to the distance from the destination node with one-half of the horizontal layer an intermediate node of the total number of nodes, moving from the intermediate node to the destination node;
例如图3中11、10、9三个位置，若9为第一位置时，将9首先移动到中间节点8，在从8移动到对面的目的节点0。For example, there are three positions 11, 10, and 9 in Fig. 3, if 9 is the first position, first move 9 to the middle node 8, and then move from 8 to the opposite destination node 0.
当相除的结果等于二分之一所述水平层的节点总数时，将所述第一位置移动到所述目的节点。When the result of the division is equal to half of the total number of nodes in the horizontal layer, the first position is moved to the destination node.
例如图3中标识8的位置可以直接通过移动到对面算法移动到目的节点0。For example, the position marked 8 in FIG. 3 can be directly moved to the destination node 0 through the move-to-the-opposite algorithm.
其中，还可以将第二预定算法中的逆时针顺序、顺时针顺序进行适应性的变换后也可以是一个新的算法。Wherein, the counterclockwise order and the clockwise order in the second predetermined algorithm may also be adaptively transformed into a new algorithm.
该算法中由分析可知，在Dist小于m/4和大于3m/4的情况下，分别选择顺时针和逆时针方向在路径上是最短的，而其余部分有两种等效的路由方法。算法会根据出口链路的阻塞程度选择任意一条路径作为路由路径。The analysis in this algorithm shows that when Dist is less than m/4 and greater than 3m/4, the clockwise and counterclockwise directions are the shortest on the path respectively, and there are two equivalent routing methods for the rest. The algorithm will select any path as the routing path according to the degree of congestion of the egress link.
其中所述第一预定算法和第二预定算法都具有顺时针、逆时针和对面三个方向的出口通道。Wherein, both the first predetermined algorithm and the second predetermined algorithm have exit passages in three directions: clockwise, counterclockwise and opposite.
该确定片上网络路由路径的方法是基于V-Spidergon结构除了具有顺时针、逆时针和对面三个方向的出口通道，还有垂直方向的通道。数据包首先在垂直方向进行确定性路由，到达目的层之后再根据链路利用率自适应选择水平层路由算法例如第一预订算法到达目的节点。The method for determining the routing path of the on-chip network is based on the V-Spidergon structure, in addition to the exit channels in the three directions of clockwise, counterclockwise and opposite, there are also channels in the vertical direction. The data packet is deterministically routed in the vertical direction first, and after reaching the destination layer, a horizontal layer routing algorithm such as the first reservation algorithm is adaptively selected according to the link utilization rate to reach the destination node.
基于上述技术方案，本发明实施例提供的确定片上网络路由路径的方法，该方法适用于V-Spidergon混合型三维网络结构的自适应路由算法。可以根据网络状态动态调整路由路径，实际效果表明该路由算法可以提高吞吐量和降低网路延时。该算法具有顺时针、逆时针和对面三个方向的出口通道，还有垂直方向的通道。数据包首先在垂直方向进行确定性路由，到达目的层之后再根据链路利用率自适应选择二维路由算法路由到目的节点，可以平衡网络中的流量分布。Based on the above technical solution, the embodiment of the present invention provides a method for determining the routing path of the network on chip, which is applicable to the adaptive routing algorithm of the V-Spidergon hybrid three-dimensional network structure. The routing path can be dynamically adjusted according to the network status, and the actual effect shows that the routing algorithm can improve throughput and reduce network delay. The algorithm has exit passages in three directions, clockwise, counterclockwise and opposite, as well as a passage in the vertical direction. The data packets are deterministically routed in the vertical direction first, and after reaching the destination layer, the two-dimensional routing algorithm is adaptively selected according to the link utilization rate to route to the destination node, which can balance the traffic distribution in the network.
基于上述技术方案，本发明的另一具体实施例还可以包括：Based on the above technical solution, another specific embodiment of the present invention may also include:
在垂直方向建立两路虚通道；Establish two virtual channels in the vertical direction;
当所述源节点的垂直位置值大于所述目的节点的垂直位置值，则使用第一虚通道；When the vertical position value of the source node is greater than the vertical position value of the destination node, the first virtual channel is used;
当所述源节点的垂直位置值小于所述目的节点的垂直位置值，则使用第二虚通道；When the vertical position value of the source node is smaller than the vertical position value of the destination node, use the second virtual channel;
和/或，在水平方向建立两路虚通道；And/or, establish two virtual channels in the horizontal direction;
当所述第一位置的水平位置值大于所述目的节点的水平位置值，则使用第一虚通道；When the horizontal position value of the first position is greater than the horizontal position value of the destination node, the first virtual channel is used;
当所述第一位置的水平位置值小于所述目的节点的水平位置值，则使用第二虚通道。When the horizontal position value of the first position is smaller than the horizontal position value of the destination node, the second virtual channel is used.
由于拓扑里所有的物理通道分为两个虚通道，并在算法中建立虚通道的使用顺序。在垂直方向可以首先比较垂直方向源坐标和目的节点坐标的大小。如果源坐标大于目的节点坐标，则使用第一虚通道VC1，而相反则使用第二虚通道VC2。在水平方向也使用相同的判断方法。此时在虚通道内数据只能向一个方向流动而不会产生通道闭环情况，从而保证了该方法中没有死锁。Because all physical channels in the topology are divided into two virtual channels, and the use order of the virtual channels is established in the algorithm. In the vertical direction, the size of the vertical source coordinates and the destination node coordinates can be compared first. If the source coordinates are greater than the destination node coordinates, the first virtual channel VC1 is used, and on the contrary, the second virtual channel VC2 is used. The same judgment method is also used in the horizontal direction. At this time, the data in the virtual channel can only flow in one direction without generating a channel closed-loop situation, thereby ensuring that there is no deadlock in this method.
即基于V-Spidergon拓扑结构使用虚信道来避免死锁问题，在输出队列缓冲中建立两个独立的微片缓冲区来避免路径中的环形链路依赖的出现。That is, based on the V-Spidergon topology, virtual channels are used to avoid deadlock problems, and two independent microchip buffers are established in the output queue buffer to avoid the occurrence of ring link dependencies in the path.
基于上述技术方案，本发明又一具体实施例在当所述预定水平层路由算法包括第一预定算法和第二预定算法时，还可以包括：Based on the above technical solution, another specific embodiment of the present invention may further include when the predetermined horizontal layer routing algorithm includes a first predetermined algorithm and a second predetermined algorithm:
当存在所述第一位置到所述目的节点的路径跳数相同时，比较两条路径的输出端口的缓存使用量，并使用缓存使用量小的输出端口所在路径，将所述第一位置移动到所述目的节点。When there is the same number of path hops from the first location to the destination node, compare the cache usage of the output ports of the two paths, and use the path where the output port with the smaller cache usage is used to move the first location to the destination node.
该算法自适应搜索源节点与目的地节点之间的等效最小路径，当存在两条完全等效的路径时，路由算法根据输出端口的缓冲使用情况选择负载较轻的端口作为输出端口，以平衡网络中的流量分布。The algorithm adaptively searches for the equivalent minimum path between the source node and the destination node. When there are two completely equivalent paths, the routing algorithm selects the port with the lighter load as the output port according to the buffer usage of the output port. Balance traffic distribution in the network.
其中，路由算法选择最短路径来实现数据传输，所以在节点水平距离dist小于m/4、大于3m/4和等于m/2时选择固定端口作为输出端口。而在其它情况下，拓扑存在两条完全等效的路径，数据流向如图2和图3所示，则根据输出端口的缓冲区使用情况选择负载较轻的端口作为输出端口，以平衡网络中的流量分布。Among them, the routing algorithm selects the shortest path to realize data transmission, so the fixed port is selected as the output port when the node horizontal distance dist is less than m/4, greater than 3m/4 and equal to m/2. In other cases, there are two completely equivalent paths in the topology, and the data flow direction is shown in Figure 2 and Figure 3. According to the buffer usage of the output port, the port with a lighter load is selected as the output port to balance the traffic in the network. flow distribution.
基于上述技术方案，本发明再一具体实施例在上述任意一个实施例的基础上还可以包括：Based on the above technical solution, another specific embodiment of the present invention may further include on the basis of any one of the above embodiments:
当垂直总线负载大于阈值时，通过水平子层确定空闲总线。When the vertical bus load is greater than a threshold, a free bus is determined by the horizontal sublayer.
考虑到链路拥塞状态和均衡网路流量，在总线负载较高的情况下可以先通过水平子层寻找空闲垂直总线，以减小总线负载，防止出现链路拥塞。Considering the state of link congestion and balancing network traffic, in the case of high bus load, the horizontal sublayer can be used to find an idle vertical bus first, so as to reduce the bus load and prevent link congestion.
基于上述技术方案，本发明实施例提供的确定片上网络路由路径的方法，该方法适用于V-Spidergon混合型三维网络结构的自适应路由算法。可以根据网络状态动态调整路由路径，实际效果表明该路由算法可以提高吞吐量和降低网路延时。该算法具有顺时针、逆时针和对面三个方向的出口通道，还有垂直方向的通道。数据包首先在垂直方向进行确定性路由，到达目的层之后再根据链路利用率自适应选择二维路由算法路由到目的节点，可以平衡网络中的流量分布。拓扑里所有的物理通道分为两个虚通道，并在算法中建立虚通道的使用顺序来避免死锁情况的发生；在存在两条完全等效的路径时，路由算法根据输出端口的缓冲使用情况选择负载较轻的端口作为输出端口，以平衡网络中的流量分布；在总线负载较高的情况下可以先通过水平子层寻找空闲垂直总线，以减小总线负载，防止出现链路拥塞。Based on the above technical solution, the embodiment of the present invention provides a method for determining the routing path of the network on chip, which is applicable to the adaptive routing algorithm of the V-Spidergon hybrid three-dimensional network structure. The routing path can be dynamically adjusted according to the network status, and the actual results show that the routing algorithm can improve throughput and reduce network delay. The algorithm has exit passages in three directions, clockwise, counterclockwise and opposite, as well as a passage in the vertical direction. The data packets are deterministically routed in the vertical direction first, and after reaching the destination layer, the two-dimensional routing algorithm is adaptively selected according to the link utilization rate to route to the destination node, which can balance the traffic distribution in the network. All physical channels in the topology are divided into two virtual channels, and the use order of the virtual channels is established in the algorithm to avoid deadlocks; when there are two completely equivalent paths, the routing algorithm uses them according to the buffer of the output port In some cases, ports with light loads are selected as output ports to balance the traffic distribution in the network; when the bus load is high, the horizontal sublayer can be used to find an idle vertical bus first, so as to reduce the bus load and prevent link congestion.
本发明实施例提供了确定片上网络路由路径的方法，可以通过上述方法能够根据网络状态动态调整路由路径。The embodiment of the present invention provides a method for determining a network-on-chip routing path, through which the routing path can be dynamically adjusted according to the network status.
下面对本发明实施例提供的确定片上网络路由路径的系统进行介绍，下文描述的确定片上网络路由路径的系统与上文描述的确定片上网络路由路径的方法可相互对应参照。The following is an introduction to the system for determining the routing path of the network on chip provided by the embodiment of the present invention. The system for determining the routing path of the network on chip described below and the method for determining the routing path of the network on chip described above can be referred to for each other.
请参考图4，图4为本发明实施例所提供的确定片上网络路由路径的系统的结构框图；该系统可以包括：Please refer to FIG. 4. FIG. 4 is a structural block diagram of a system for determining a network-on-chip routing path provided by an embodiment of the present invention; the system may include:
垂直移动模块100，用于从源节点所在的垂直总线上移动到目的节点所在的垂直总线上，到达目的水平层的第一位置；The vertical movement module 100 is used to move from the vertical bus where the source node is located to the vertical bus where the destination node is located, to reach the first position of the destination horizontal layer;
计算模块200，用于根据所述第一位置的水平位置值与所述目的节点的水平位置值，计算得到所述第一位置到所述目的节点的水平跳数；A calculation module 200, configured to calculate the number of horizontal hops from the first position to the destination node according to the horizontal position value of the first position and the horizontal position value of the destination node;
水平移动模块300，用于根据所述水平跳数与所述水平层的节点总数，按照预定水平层路由算法，得到从所述第一位置到达所述目的节点的水平路径。The horizontal movement module 300 is configured to obtain a horizontal path from the first location to the destination node according to the number of horizontal hops and the total number of nodes in the horizontal layer according to a predetermined horizontal layer routing algorithm.
优选的，所述水平移动模块300包括：第一预定算法单元和/或第二预定算法单元；其中，Preferably, the horizontal movement module 300 includes: a first predetermined algorithm unit and/or a second predetermined algorithm unit; wherein,
所述第一预定算法单元包括：The first predetermined algorithm unit includes:
第一计算单元，用于将所述水平跳数与所述水平层的节点总数相除；a first calculation unit, configured to divide the number of horizontal hops by the total number of nodes in the horizontal layer;
第一移动单元，用于当相除的结果不大于四分之一所述水平层的节点总数时，按照顺时针移动到所述目的节点；当相除的结果不小于四分之三所述水平层的节点总数时，按照顺时针移动到所述目的节点；当相除的结果大于四分之一且小于二分之一所述水平层的节点总数时，将所述第一位置移动到对面的第二位置，将所述第二位置按照顺时针移动到所述目的节点；其中，所述移动到对面中间节点具体为：计算出所述第一位置到距所述目的节点具有二分之一所述水平层的节点总数的中间节点的跳数，将所述第一位置移动到按顺时针距所述目的节点具有相同跳数的第二位置；当相除的结果小于四分之三且大于二分之一所述水平层的节点总数时，将所述第一位置移动到对面的第二位置，将所述第二位置按照顺时针移动到所述目的节点；当相除的结果等于二分之一所述水平层的节点总数时，将所述第一位置移动到所述目的节点；The first moving unit is used to move clockwise to the destination node when the result of the division is not greater than 1/4 of the total number of nodes in the horizontal layer; when the result of the division is not less than 3/4 of the When the total number of nodes in the horizontal layer, move to the destination node clockwise; when the result of the division is greater than 1/4 and less than 1/2 of the total number of nodes in the horizontal layer, move the first position to For the second position on the opposite side, move the second position clockwise to the destination node; wherein, the moving to the opposite intermediate node is specifically: calculate the first position to be 2 points away from the destination node The number of hops of the intermediate node of the total number of nodes in one of the horizontal layers, the first position is moved to the second position with the same number of hops clockwise away from the destination node; when the result of the division is less than 1/4 When three and more than one-half of the total number of nodes in the horizontal layer, move the first position to the opposite second position, and move the second position clockwise to the destination node; when dividing When the result is equal to one-half of the total number of nodes in the horizontal layer, moving the first position to the destination node;
所述第二预定算法单元包括：The second predetermined algorithm unit includes:
第二计算单元，用于将所述水平跳数与所述水平层的节点总数相除；a second calculation unit, configured to divide the number of horizontal hops by the total number of nodes in the horizontal layer;
第二移动单元，用于当相除的结果不大于四分之一所述水平层的节点总数时，按照顺时针移动到所述目的节点；当相除的结果不小于四分之三所述水平层的节点总数时，按照顺时针移动到所述目的节点；当相除的结果大于四分之一且小于二分之一所述水平层的节点总数时，将所述第一位置按照顺时针移动到距所述目的节点具有二分之一所述水平层的节点总数的中间节点，从所述中间节点移动到所述目的节点；当相除的结果小于四分之三且大于二分之一所述水平层的节点总数时，将所述第一位置按照顺时针移动到距所述目的节点具有二分之一所述水平层的节点总数的中间节点，从所述中间节点移动到所述目的节点；当相除的结果等于二分之一所述水平层的节点总数时，将所述第一位置移动到所述目的节点。The second moving unit is used to move clockwise to the destination node when the result of the division is not greater than 1/4 of the total number of nodes in the horizontal layer; when the result of the division is not less than 3/4 of the When the total number of nodes in the horizontal layer, move to the destination node clockwise; when the result of the division is greater than one-fourth and less than one-half of the total number of nodes in the horizontal layer, move the first position in order Hour hand moves to the intermediate node that has the node total number of 1/2 described horizontal layer apart from described purpose node, moves to described purpose node from described intermediate node; When the result of dividing is less than three-quarters and greater than half When the total number of nodes in one of the horizontal layers, move the first position clockwise to an intermediate node that has half the total number of nodes in the horizontal layer from the destination node, and move from the intermediate node to The destination node; when the result of the division is equal to half of the total number of nodes in the horizontal layer, moving the first position to the destination node.
优选的，同时具有所述第一预定算法单元和所述第二预定算法单元，该系统还可以包括：Preferably, having both the first predetermined algorithm unit and the second predetermined algorithm unit, the system may also include:
选择模块，用于当存在所述第一位置到所述目的节点的路径跳数相同时，比较两条路径的输出端口的缓存使用量，并使用缓存使用量小的输出端口所在路径，将所述第一位置移动到所述目的节点。A selection module, configured to compare the buffer usage of the output ports of the two paths when there are paths from the first position to the destination node with the same number of hops, and use the path where the output port with the smallest buffer usage is located to select all The first location is moved to the destination node.
优选的，基于上述系统，该系统还可以包括：Preferably, based on the above system, the system may also include:
垂直通道模块，用于在垂直方向建立两路虚通道；当所述源节点的垂直位置值大于所述目的节点的垂直位置值，则使用第一虚通道；当所述源节点的垂直位置值小于所述目的节点的垂直位置值，则使用第二虚通道；和/或，The vertical channel module is used to establish two virtual channels in the vertical direction; when the vertical position value of the source node is greater than the vertical position value of the destination node, the first virtual channel is used; when the vertical position value of the source node is less than the vertical position value of the destination node, then use the second virtual channel; and/or,
水平通道模块，用于在水平方向建立两路虚通道；当所述第一位置的水平位置值大于所述目的节点的水平位置值，则使用第一虚通道；当所述第一位置的水平位置值小于所述目的节点的水平位置值，则使用第二虚通道。The horizontal channel module is used to establish two virtual channels in the horizontal direction; when the horizontal position value of the first position is greater than the horizontal position value of the destination node, the first virtual channel is used; when the horizontal position value of the first position If the position value is smaller than the horizontal position value of the destination node, the second virtual channel is used.
基于上述任意系统，该系统还可以包括：Based on any of the above systems, the system may also include:
判定模块，用于当垂直总线负载大于阈值时，通过水平子层确定空闲总线。A judging module, configured to determine an idle bus through the horizontal sublayer when the vertical bus load is greater than a threshold.
基于上述技术方案，本发明实施例提供的确定片上网络路由路径的系统，该系统适用于V-Spidergon混合型三维网络结构的自适应路由算法。可以根据网络状态动态调整路由路径，实际效果表明该路由算法可以提高吞吐量和降低网路延时。该算法具有顺时针、逆时针和对面三个方向的出口通道，还有垂直方向的通道。数据包首先在垂直方向进行确定性路由，到达目的层之后再根据链路利用率自适应选择二维路由算法路由到目的节点，可以平衡网络中的流量分布。拓扑里所有的物理通道分为两个虚通道，并在算法中建立虚通道的使用顺序来避免死锁情况的发生；在存在两条完全等效的路径时，路由算法根据输出端口的缓冲使用情况选择负载较轻的端口作为输出端口，以平衡网络中的流量分布；在总线负载较高的情况下可以先通过水平子层寻找空闲垂直总线，以减小总线负载，防止出现链路拥塞。Based on the above technical solution, the embodiment of the present invention provides a system for determining a network-on-chip routing path, which is applicable to an adaptive routing algorithm of a V-Spidergon hybrid three-dimensional network structure. The routing path can be dynamically adjusted according to the network status, and the actual effect shows that the routing algorithm can improve throughput and reduce network delay. The algorithm has exit passages in three directions, clockwise, counterclockwise and opposite, as well as a passage in the vertical direction. The data packets are deterministically routed in the vertical direction first, and after reaching the destination layer, the two-dimensional routing algorithm is adaptively selected according to the link utilization rate to route to the destination node, which can balance the traffic distribution in the network. All physical channels in the topology are divided into two virtual channels, and the use order of the virtual channels is established in the algorithm to avoid deadlocks; when there are two completely equivalent paths, the routing algorithm uses them according to the buffer of the output port In some cases, ports with light loads are selected as output ports to balance the traffic distribution in the network; when the bus load is high, the horizontal sublayer can be used to find an idle vertical bus first, so as to reduce the bus load and prevent link congestion.
说明书中各个实施例采用递进的方式描述，每个实施例重点说明的都是与其他实施例的不同之处，各个实施例之间相同相似部分互相参见即可。对于实施例公开的装置而言，由于其与实施例公开的方法相对应，所以描述的比较简单，相关之处参见方法部分说明即可。Each embodiment in the description is described in a progressive manner, each embodiment focuses on the difference from other embodiments, and the same and similar parts of each embodiment can be referred to each other. As for the device disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and for the related information, please refer to the description of the method part.
专业人员还可以进一步意识到，结合本文中所公开的实施例描述的各示例的单元及算法步骤，能够以电子硬件、计算机软件或者二者的结合来实现，为了清楚地说明硬件和软件的可互换性，在上述说明中已经按照功能一般性地描述了各示例的组成及步骤。这些功能究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。Professionals can further realize that the units and algorithm steps of the examples described in conjunction with the embodiments disclosed herein can be implemented by electronic hardware, computer software or a combination of the two. In order to clearly illustrate the possible For interchangeability, in the above description, the composition and steps of each example have been generally described according to their functions. Whether these functions are executed by hardware or software depends on the specific application and design constraints of the technical solution. Those skilled in the art may use different methods to implement the described functions for each specific application, but such implementation should not be regarded as exceeding the scope of the present invention.
结合本文中所公开的实施例描述的方法或算法的步骤可以直接用硬件、处理器执行的软件模块，或者二者的结合来实施。软件模块可以置于随机存储器(RAM)、内存、只读存储器(ROM)、电可编程ROM、电可擦除可编程ROM、寄存器、硬盘、可移动磁盘、CD-ROM、或技术领域内所公知的任意其它形式的存储介质中。The steps of the methods or algorithms described in connection with the embodiments disclosed herein may be directly implemented by hardware, software modules executed by a processor, or a combination of both. Software modules can be placed in random access memory (RAM), internal memory, read-only memory (ROM), electrically programmable ROM, electrically erasable programmable ROM, registers, hard disk, removable disk, CD-ROM, or any other Any other known storage medium.
以上对本发明所提供的确定片上网络路由路径的方法及系统进行了详细介绍。本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。The method and system for determining the routing path of the network-on-chip provided by the present invention have been introduced in detail above. In this paper, specific examples are used to illustrate the principle and implementation of the present invention, and the descriptions of the above embodiments are only used to help understand the method and core idea of the present invention. It should be pointed out that for those skilled in the art, without departing from the principle of the present invention, some improvements and modifications can be made to the present invention, and these improvements and modifications also fall within the protection scope of the claims of the present invention.
Claims (6)
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510594792.4A CN105072032B (en) | 2015-09-17 | 2015-09-17 | A kind of method and system of definite network-on-chip routed path |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201510594792.4A CN105072032B (en) | 2015-09-17 | 2015-09-17 | A kind of method and system of definite network-on-chip routed path |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN105072032A CN105072032A (en) | 2015-11-18 |
| CN105072032B true CN105072032B (en) | 2018-05-18 |
Family
ID=54501318
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201510594792.4A Active CN105072032B (en) | 2015-09-17 | 2015-09-17 | A kind of method and system of definite network-on-chip routed path |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN105072032B (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN105577539B (en) * | 2016-01-27 | 2018-08-10 | 中国科学院计算技术研究所 | A kind of method for routing and system towards irregular three dimensional integrated circuits network-on-chip |
| US10454830B2 (en) * | 2016-05-05 | 2019-10-22 | City University Of Hong Kong | System and method for load balancing in a data network |
| CN110958177B (en) * | 2019-11-07 | 2022-02-18 | 浪潮电子信息产业股份有限公司 | Network-on-chip route optimization method, device, equipment and readable storage medium |
| CN111966595B (en) * | 2020-08-13 | 2024-04-05 | 安徽芯纪元科技有限公司 | A chip positioning method and debugging message transmission method in a software debugging system |
| CN113709040B (en) * | 2021-08-31 | 2023-04-07 | 中国电子科技集团公司第五十八研究所 | Package-level network routing algorithm based on extensible interconnected die |
| CN115955429B (en) * | 2023-02-15 | 2023-07-21 | 北京象帝先计算技术有限公司 | Routing method, device, system and electronic equipment of network on chip |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101388834A (en) * | 2008-10-20 | 2009-03-18 | 电子科技大学 | 3D Network-on-Chip Architecture Approach |
| CN102333038A (en) * | 2011-10-21 | 2012-01-25 | 上海交通大学 | A Deadlock-Free Routing Method Based on Network-on-Chip |
| CN104079480A (en) * | 2014-05-30 | 2014-10-01 | 中国科学院计算技术研究所 | Routing method and system of network on three-dimensional integrated circuit chip |
| CN104092617A (en) * | 2014-05-30 | 2014-10-08 | 中国科学院计算技术研究所 | A three-dimensional integrated circuit on-chip network routing method and system thereof |
-
2015
- 2015-09-17 CN CN201510594792.4A patent/CN105072032B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101388834A (en) * | 2008-10-20 | 2009-03-18 | 电子科技大学 | 3D Network-on-Chip Architecture Approach |
| CN102333038A (en) * | 2011-10-21 | 2012-01-25 | 上海交通大学 | A Deadlock-Free Routing Method Based on Network-on-Chip |
| CN104079480A (en) * | 2014-05-30 | 2014-10-01 | 中国科学院计算技术研究所 | Routing method and system of network on three-dimensional integrated circuit chip |
| CN104092617A (en) * | 2014-05-30 | 2014-10-08 | 中国科学院计算技术研究所 | A three-dimensional integrated circuit on-chip network routing method and system thereof |
Also Published As
| Publication number | Publication date |
|---|---|
| CN105072032A (en) | 2015-11-18 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN105072032B (en) | A kind of method and system of definite network-on-chip routed path | |
| US8819616B2 (en) | Asymmetric mesh NoC topologies | |
| JP6093867B2 (en) | Non-uniform channel capacity in the interconnect | |
| US9130856B2 (en) | Creating multiple NoC layers for isolation or avoiding NoC traffic congestion | |
| KR102374572B1 (en) | Transactional traffic specification for network-on-chip design | |
| CN106165356B (en) | Method for routing packets in a distributed direct interconnect network | |
| Ebrahimi et al. | DyXYZ: Fully adaptive routing algorithm for 3D NoCs | |
| US20150178435A1 (en) | Automatic pipelining of noc channels to meet timing and/or performance | |
| CN103763205B (en) | The global network on three-dimensional chip Delay Bound optimization method in a balanced way of silicon hole load | |
| US20140301241A1 (en) | Multiple heterogeneous noc layers | |
| US10050843B2 (en) | Generation of network-on-chip layout based on user specified topological constraints | |
| CN104022950B (en) | It is a kind of to share the router topology cached with self-configuring | |
| CN101335704A (en) | Adaptive routing method without dead lock in three-dimensional torus network | |
| CN101123576A (en) | A Path Selection Method for Mobile Ad Hoc Networks Based on Bandwidth Constraint and Minimum Load | |
| US10374943B2 (en) | Routing packets in dimensional order in multidimensional networks | |
| CN102693213A (en) | System-level transmission delay model building method applied to network on chip | |
| CN106105282B (en) | Systems and methods for traffic engineering using link buffer state | |
| US9762474B2 (en) | Systems and methods for selecting a router to connect a bridge in the network on chip (NoC) | |
| US10084725B2 (en) | Extracting features from a NoC for machine learning construction | |
| Nosrati et al. | Regional selection mechanism for traffic-balanced adaptive routing algorithms in mesh-based NoC architectures | |
| Cai et al. | Deadlock-free adaptive routing based on the repetitive turn model for 3D network-on-chip | |
| Azampanah et al. | LATEX: New selection policy for adaptive routing in application-specific NoC | |
| Satish et al. | Comparative performance analysis of routing topology for noc architecture | |
| Foroutan et al. | Cost-efficient buffer sizing in shared-memory 3D-MPSoCs using wide I/O interfaces | |
| Azampanah et al. | Traffic-aware selection strategy for application-specific 3D NoC |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |