CN107046500A - A Two-Stage Split Router and Its Routing Algorithm for Hierarchical On-Chip Networks - Google Patents

Abstract

The invention discloses a two-stage split router and its routing algorithm applied to a hierarchical on-chip network. The calculation module includes a classification decoding unit YM, a unicast data packet routing calculation unit SR, a multicast uplink data packet routing calculation unit UR, a multicast downlink data packet routing calculation unit DR and an output port register unit. The invention can optimize and improve the hybrid multicast routing algorithm, and selectively split and transmit the data in the multicast data packet through a two-level split method, so as to reduce the delay of the multicast data packet and optimize the upper layer at the same time The congestion status of the network.

Description

A Two-Stage Split Router and Its Routing Algorithm for Hierarchical On-Chip Networks

technical field

The invention belongs to the communication technical field of integrated circuit on-chip networks, and in particular relates to a two-level split router and routing algorithm applied to hierarchical on-chip networks.

Background technique

With the continuous increase of the number of cores on the network on chip, the parallel communication between multiple cores makes the communication relationship of the network on chip quite complicated. The traditional network-on-chip design only considers the unicast communication mode from one source node to one destination node. It has become an increasingly important communication requirement to implement multicast communication from a single source node to multiple destination nodes on a network-on-chip.

Currently, there are many multicast routing algorithms, among which, the hybrid multicast routing algorithm based on hierarchical network structure adopts a two-layer network structure and divides the underlying network into different areas. Each router in the upper layer network is equivalent to a bridge router for the intermediate routers in the lower layer area. Unicast packets are only transmitted on the underlying network. The multicast data packet is first transmitted to the upper layer network, then propagates from the upper layer network to different areas where each destination node is located, and then reaches the destination node.

However, in order to avoid a deadlock situation, the algorithm stipulates that all multicast data packets in an area must enter the area from the upper router, even if a source node performs multicast transmission to other nodes or adjacent nodes in its own area. It must also enter the area through the upper layer router in the area, which will greatly increase the delay of the packet.

Contents of the invention

In order to solve the shortcomings of the above-mentioned prior art, the present invention proposes a two-level split router and its routing algorithm applied to a hierarchical network on chip, in order to directly transmit data packets to the destination node on the upward transmission path Or the destination node adjacent to the upstream transmission path can effectively improve the transmission efficiency and reduce the delay.

The technical scheme that the present invention adopts for achieving the above object is:

The present invention is a two-stage split router applied to a hierarchical network-on-chip, wherein the hierarchical network-on-chip is composed of an N×M bottom layer two-dimensional network and an L×S upper layer network; 1≤L<N, 1≤ S<M; the underlying two-dimensional network is divided into L×S areas; each area contains an intermediate router and several ordinary routers; the ordinary router includes five transmission directions; the intermediate router includes five transmission directions direction and one upward transmission direction; the upper layer network is a transmission router; the transmission router includes five transmission directions and one downward transmission direction; the intermediate router and the transmission router are connected to each other; it is characterized in that,

The decoding module in the intermediate router and several ordinary routers is set as a multicast routing calculation module; the multicast routing calculation module includes a classification decoding unit YM, a unicast packet routing calculation unit SR, a multicast uplink data The packet routing calculation unit UR, the multicast downlink data packet routing calculation unit DR and the output port register unit; the multicast uplink data packet routing calculation unit UR includes: a two-stage split unit TS and an ordinary uplink routing calculation unit RC; the output port The register unit includes: m-bit transmission direction register port_1[m-1:0] and m-bit omnidirectional register port_2[m-1:0]; m is the number of transmission directions; the transmission direction register port_1[m- 1:0] is used to store the transmission direction of the current head flits; the omnidirectional register port_2[m-1:0] is used to store the transmission directions of all the head flits;

When an intermediate router or common router in any zone is used as a current routing node and receives a data packet through its own input module, the input module of the current routing node sends the microchip in the data packet to its own multicast routing calculation module;

The classification decoding unit YM of the current routing node judges the received current flit, if the received current flit is the header flit, the classification decoding unit YM judges the header flit again;

If the header flake is the header flake of the multicast data packet; then the transmission direction of the header flake of the multicast data packet is judged, if it is the upward transmission direction, then the header of the multicast data packet is The microchip is sent to the multicast uplink data packet routing calculation unit UR for calculating the transmission direction; if it is the downward transmission direction, the header microchip of the multicast data packet is sent to the multicast downlink data packet routing calculation unit DR for calculation transmission direction;

If the header flake is the header flake of the unicast data packet; then the header flake of the unicast data packet is sent to the unicast data packet routing calculation unit SR for calculating the transmission direction;

If the received current flit is a body flit, then the output port register unit copies the transfer directions of all header flits from the omnidirectional register port_2[m-1:0] to the transfer direction register port_1[m-1 :0], the input module of the current routing node transmits the microchip to the downstream routing node according to the transmission direction of the transmission direction register port_1[m-1:0] in the output port register unit;

If the received current flit is a tail flit, the output port register unit copies the transfer directions of all head flits from the omnidirectional register port_2[m-1:0] to the transfer direction register port_1[m-1 :0], the input module of the current routing node transmits the tail chip to the downstream routing node according to the transmission direction of the transmission direction register port_1[m-1:0] in the output port register unit; then, the classification decoding of the current routing node The unit YM sends a data packet transmission end signal to the output port registration unit; the output port registration unit clears the output port registration unit of the current routing node according to the received data packet transmission end signal;

The two-level splitting unit TS of the multicast uplink data packet routing calculation unit UR compares the current routing node's own coordinates with the destination node's coordinates according to the header flake of the received multicast data packet,

If the two coordinates are the same, it means that the current routing node is the destination node, and the obtained transmission direction is the local direction and stored in the output port storage unit;

If the two coordinates are adjacent, it means that the current routing node and the destination node are adjacent nodes, and the transmission direction is obtained as an adjacent direction, and the two-stage splitting unit TS judges whether the output port of the current routing node is idle, if idle, Then store the adjacent direction in the output port register unit; if it is not idle, then do not store the adjacent direction, and transmit the header flake of the multicast data packet to the common uplink routing calculation unit RC;

If the two coordinates are neither adjacent nor the same, then directly transmit the header flake of the multicast data packet to the common uplink routing calculation unit RC; Coordinates, calculate the transmission direction downstream of the multicast packet header chip, and save it to the output port storage unit of the current routing node;

The multicast downlink data packet routing calculation unit DR uses the XY routing algorithm to calculate the downstream transmission direction of the multicast data packet header flake according to the received multicast data packet header flake, and saves it to the output of the current routing node Port register unit;

The unicast data packet routing calculation unit SR uses the XY routing algorithm to calculate the downstream transmission direction of the unicast data packet header microchip according to the received unicast data packet header microchip, and saves it to the output port storage unit of the current routing node ;

When the omnidirectional register port_2[m-1:0] receives the input direction of the current microchip, it is judged whether the transmission direction of the current microchip already exists, if it already exists, the multicast routing calculation module of the current routing node will re- The arbitration request signal is sent to its own arbitration module, which is used to open the corresponding output port of the crossbar module, otherwise, directly store the input direction of the current microchip.

The present invention is a routing algorithm for a two-level split router applied to a hierarchical network-on-chip, wherein the hierarchical network-on-chip is composed of an N×M bottom-layer two-dimensional network and an L×S upper-layer network; 1≤L<N , 1≤S<M; the underlying two-dimensional network is divided into L×S areas; each area contains an intermediate router and several ordinary routers; the ordinary router includes five transmission directions; the intermediate router includes Five transmission directions and one upward transmission direction; the upper network is a transmission router; the transmission router includes five transmission directions and one downward transmission direction; the intermediate router and the transmission router are connected to each other; its characteristics are , when using an intermediate router or common router in any zone as the current routing node and receiving data packets through its own input module, the routing algorithm is performed as follows:

Step 1, setting described intermediate router and several ordinary routers all comprise: m-bit transmission direction register port_1[m-1:0] and m-bit omnidirectional register port_2[m-1:0]; m is the transmission direction register port_2[m-1:0]; number; the transfer direction register port_1[m-1:0] is used to store the transfer direction of the current head flits; the omnidirectional register port_2[m-1:0] is used to store the transfer directions of all head flits ;

Step 2, the current routing node judges the current flit in the received data packet, if the received current flit is the header flit, then perform step 3; if the received current flit is the body flit slice, execute step 8; if the received current flit is the tail flit, execute step 9;

Step 3, the current routing node judges the header flake again; if the header flake is the header flake of a multicast data packet; then perform step 4; if the header flake is the header of a unicast packet Microchip; then directly use the XY routing algorithm to calculate the transmission direction downstream of the unicast packet header microchip and save it in the transmission direction register port_1[m-1:0] and the omnidirectional register port_2[m-1:0]; then Execute step 10;

Step 4, the current routing node judges the transmission direction of the header flake of the multicast data packet, if it is the upward transmission direction, then perform step 5; if it is the downward transmission direction, then perform step 7;

Step 5, the current routing node compares the self coordinates of the current routing node with the coordinates of the destination node according to the header chip of the received multicast data packet, if the two coordinates are the same, it means that the current routing node is The destination node obtains the transmission direction as the local direction and saves it in the transmission direction register port_1[m-1:0] and the omnidirectional register port_2[m-1:0]; then execute step 10;

If the two coordinates are adjacent, it means that the current routing node and the destination node are adjacent nodes, and the transmission direction is obtained as the adjacent direction, and judge whether the output port of the current routing node is free. If it is free, save the adjacent direction to the transmission direction In register port_1[m-1:0] and omnidirectional register port_2[m-1:0], go to step 10; otherwise go to step 6; if the two coordinates are neither adjacent nor the same, go to step 6 directly;

Step 6. The current routing node calculates the transmission direction downstream of the multicast packet header chip according to the coordinates of the intermediate router in its own area and saves it in the transmission direction register port_1[m-1:0] and the omnidirectional register port_2[m-1 :0]; then execute step 10;

Step 7. The current routing node uses the XY routing algorithm to calculate the downstream transmission direction of the multicast packet header flake according to the received multicast packet header flake and saves it in the transmission direction register port_1[m-1:0] and in the omnidirectional register port_2[m-1:0]; then perform step 10;

Step 8. The current routing node copies the transmission direction of all header flits from the omnidirectional register to the transmission direction register port_1[m-1:0], thereby according to the transmission direction in the transmission direction register port_1[m-1:0] Transmit volume microchips to downstream routing nodes; return to step 2;

Step 9. The current routing node copies the transmission direction of all header flits from the omnidirectional register port_2[m-1:0] to the transmission direction register port_1[m-1:0], thereby according to the transmission direction register port_1[m-1:0] 1:0] in the transmission direction will transmit the tail microchip to the downstream routing node; when the transmission of the tail microchip is completed, the current routing node will transmit the direction register port_1[m-1:0] and the omnidirectional register port_2[m-1 :0] to zero, and then return to step 2;

Step 10, when the omnidirectional register port_2[m-1:0] receives the input direction of the current microchip, it is judged whether the transmission direction of the current microchip already exists, if it already exists, the arbitration request of the current routing node will be re-arbitrated The signal is sent to its own arbitration module to open the corresponding output port of the crossbar switch module, otherwise, directly store the input direction of the current microchip;

Step 11, return to step 2.

Compared with the prior art, the beneficial technical effect of the present invention is reflected in:

1. The present invention divides the underlying routing network, and each area has an intermediate router connected with the transmission router of the upper layer, and connects each area through the transmission router, thereby realizing the transmission between areas; by changing the ordinary router decoding module It is a multicast routing calculation module, which divides data packet transmission into unicast data packet transmission, multicast uplink data packet transmission and multicast downlink data packet transmission according to header chip information; unicast data packet transmission, multicast downlink data packet transmission They are all directly transmitted through the XY routing algorithm, and the multicast uplink data packet transmission is classified according to whether the destination node is the current node, the adjacent node of the current node, and the nodes that do not match the two, so that the multicast uplink data packet The transmission is divided into three cases; for the case where the destination node is the current node, it is directly split, because this method will not cause deadlock problems, so even if the output channel is occupied, it can wait for the output channel to be idle for transmission, which greatly improves In order to improve the transmission efficiency, and it will not affect the transmission of data packets to other directions; when the destination node is the adjacent node of the current node, in order to avoid the deadlock problem, if the output channel is occupied, it will be directly transmitted to the intermediate route, if there is an output channel If it is idle, it can be directly transmitted to the adjacent node. Since there is no new deadlock problem, this will not increase the complexity of the algorithm hardware implementation, and will not cause congestion problems; when the destination node does not meet the above two conditions, Then the data packet is transmitted to the intermediate router, transmitted to the area where the destination node is located through the upper layer transmission router, and then transmitted to the destination node through the multicast downlink data packet transmission algorithm; thus solving the problem that the hybrid multicast routing algorithm must pass through the upper layer transmission router to transmit to the destination node. For the problem of the destination node, the data packet can be transmitted to the destination node at the position of the current node and its adjacent nodes through the two-level split routing algorithm; thereby greatly improving the transmission efficiency and reducing congestion and delay.

2. In order to be able to collect all the multicast direction information in the present invention, two kinds of registers are used to store it, and a transmission direction register is used to store the current microchip transmission direction; and in order to preserve the direction information of multiple header microchips, an omnidirectional register is used. When transmitting the body microchip and tail microchip at the same time, the direction information is transmitted to the transmission direction register; this distinguishes the current transmission direction from all multicast transmission directions; at the same time, in order to avoid multiple arbitrations in the same transmission direction, by setting re-arbitration The request signal directly turns on the crossbar switch, thereby reducing the arbitration time and complexity, and also reducing the working time of the arbitrator, reducing the delay, and reducing the power consumption of the router at the same time.

3. The present invention selectively transmits the multicast uplink data packet to the underlying network through a two-stage split routing algorithm, and checks whether the destination node of the current multicast data packet is the current node, the adjacent nodes of the current node, and both The nodes that do not match are classified, thereby increasing the process of transmitting data packets to the destination node in the underlying network, greatly reducing the process of transmitting data packets to the upper-layer transmission router, greatly reducing the congestion of the upper-layer network and reducing delay.

4. In order not to add a new deadlock problem, the present invention determines whether the data packet is split to the adjacent node according to whether the output channel is idle when the second-level splitting module judges that the destination node is in the adjacent position of the current node, and avoids the network Congestion reduces latency.

5. The present invention divides the data packet transmission into three situations by judging the position of the destination node of the data packet in the upward transmission direction, respectively being the situation that the current node is the destination node, and the situation that the adjacent node of the current node is the destination node, and other Situation; the limitation that the hybrid multicast routing algorithm based on hierarchical network structure can only be transmitted from the upper layer to the destination node has been changed, thus greatly improving the transmission efficiency and reducing the delay.

Description of drawings

Figure 1 is a hierarchical network structure diagram of the prior art with a bottom layer of 6×6 and an upper layer of 2×2 scale;

Fig. 2 is a circuit structure diagram of the multicast routing calculation module of the present invention;

Fig. 3 is two purpose nodes of the present invention on its uplink path;

Fig. 4 is the adjacent node of a destination node of the present invention on its uplink path;

Fig. 5 is the adjacent node of two destination nodes of the present invention on its uplink path;

Fig. 6 is the adjacent nodes of the uplink paths of three destination nodes in the present invention;

Fig. 7 is the adjacent nodes of four destination nodes in the present invention on its uplink path;

Fig. 8 is a delay comparison diagram of different destination node numbers on the uplink path of the present invention;

FIG. 9 is a delay comparison diagram of different numbers of detachable adjacent destination nodes according to the present invention.

detailed description

In this embodiment, the format of the data packet is as shown in Table 1. Each multicast data packet header microchip includes a virtual channel number flag, a microchip type flag, a data packet type flag, a destination node number, a source node number, a data packet current Transmission path, upper layer node number in the area where the destination node is located, upper layer network transmission direction;

Table 1 Network packet format

The hierarchical on-chip network structure adopted is a double-layer on-chip network composed of a 6×6 bottom two-dimensional network and a 2×2 upper layer network, as shown in Figure 1; the bottom two-dimensional network is divided into four areas; each The area contains an intermediate router and several ordinary routers; ordinary routers include five transmission directions; intermediate routers include five transmission directions and one upward transmission direction; upper-layer networks are all transmission routers; Downward transport direction; intermediate routers and transit routers are connected to each other.

In this embodiment, the decoding modules in the intermediate router and several common routers are set as multicast routing calculation modules; as shown in Figure 2, the multicast routing calculation module includes classification decoding unit YM, unicast packet routing calculation module Unit SR, multicast uplink data packet routing calculation unit UR, multicast downlink data packet routing calculation unit DR and output port storage unit; multicast uplink data packet routing calculation unit UR includes: two-stage split unit TS and common uplink routing calculation unit Unit RC; the common router output port registration unit includes: 5-bit transmission direction register port_1[4:0] and 5-bit omnidirectional register port_2[4:0]; the intermediate router output port registration unit includes: 6-bit transmission direction register port_1[5:0] and 6-bit omnidirectional register port_2[5:0]; the transmission direction registers of ordinary routers and intermediate routers are uniformly represented as transmission direction register port_1, and the omnidirectional registers are uniformly represented as omnidirectional register port_2; transmission direction registers port_1 is used to store the transmission direction of the current header microchip; the omnidirectional register port_2 is used to store the transmission direction of all the header microchips, and one bit in the omnidirectional register port_2 represents a transmission direction;

When an intermediate router or a common router in any area acts as the current routing node and receives data packets through its own input module, the input module of the current routing node sends the microchip data_in[38] in the data packet to its own multicast routing calculation module :0];

The classification decoding unit YM of the current routing node judges the received current microchip data_in[38:0], and judges whether the microchip data_in[36:35] microchip type flag is 2'b01, and if so, the current microchip If the slice is the head slice, if it is 2'b11, then the current slice is the body slice, if it is 2'b10, then the current slice is the tail slice; if the received current slice is the head slice, then classification translation The code unit YM judges the header flake again, and judges whether the data packet type flag of the header flake data_in[34] is 1'b1, if so, the header flit is a multicast data packet header flake, if not, it is unicast data Baotou microchips.

If the header flake is the header flake of the multicast data packet, then the transmission direction of the header flake of the multicast packet is judged, and whether the current transmission path of the header flake data_in[32] data packet is an upward transmission path 1' b1, if yes, the current transmission path is the upward transmission path, if not, the current transmission path is the downward transmission path; if it is the upward transmission direction, then send the header flake of the multicast data packet to the multicast upstream data packet routing calculation unit UR It is used to calculate the transmission direction; if it is the downward transmission direction, the header flake of the multicast data packet is sent to the multicast downlink data packet routing calculation unit DR for calculation of the transmission direction;

If the header flake is the header flake of the unicast data packet; then the header flake of the unicast data packet is sent to the unicast data packet routing calculation unit SR for calculating the transmission direction;

If the received current flit is a body flit, the output port register unit copies the transmission direction of all header flits from the omnidirectional register port_2 to the transmit direction register port_1, and the input module of the current routing node is based on the output port register unit The transmission direction of the medium transmission direction register port_1 transmits the microchip to the downstream routing node;

If the current flit received is the tail flit, the output port register unit will copy the transmission direction of all the head flits from the omnidirectional register port_2 to the transmit direction register port_1, and the input module of the current routing node is based on the output port register unit The transmission direction of the middle transmission direction register port_1 transmits the tail microchip to the downstream routing node; then, the classification decoding unit YM of the current routing node sends a data packet transmission end signal to the output port registration unit; the output port registration unit according to the received The data packet transmission end signal clears the output port register unit of the current routing node;

The two-level split unit TS of the multicast uplink data packet routing calculation unit UR compares the current routing node's own coordinates with the destination node's coordinates data_in[23:8] according to the received multicast data packet header slice ,

If the two coordinates are the same, it means that the current routing node is the destination node, and the obtained transmission direction is the local direction and stored in the output port storage unit;

If the two coordinates are adjacent, it means that the current routing node and the destination node are adjacent nodes, and the transmission direction is obtained as the adjacent direction. The two-level splitting unit TS then judges whether the output port of the current routing node is free. The adjacent direction is stored in the output port register unit; if it is not idle, the adjacent direction is not saved, and the header flake of the multicast data packet is transmitted to the common uplink routing calculation unit RC;

If the two coordinates are neither adjacent nor the same, the header flake of the multicast data packet is directly transmitted to the ordinary uplink routing calculation unit RC; the ordinary uplink routing calculation unit RC calculates The downstream transmission direction of the multicast packet header microchip, and save it to the output port storage unit of the current routing node;

The multicast downlink data packet routing calculation unit DR uses the XY routing algorithm to calculate the downstream transmission direction of the multicast data packet header microchip according to the received multicast data packet header microchip, and saves it to the output port of the current routing node for storage unit;

The unicast data packet routing calculation unit SR uses the XY routing algorithm to calculate the downstream transmission direction of the unicast data packet header microchip according to the received unicast data packet header microchip, and saves it to the output port storage unit of the current routing node ;

When the omnidirectional register port_2 receives the input direction of the current flit, it judges whether the transmission direction of the current flit already exists, and if it already exists, the multicast routing calculation module of the current routing node sends the re-arbitration request signal to its own arbitration module , used to open the corresponding output port of the crossbar module, otherwise, directly store the input direction of the current microchip.

In this embodiment, a routing algorithm for a two-stage split router applied to a hierarchical network-on-chip, where the hierarchical network-on-chip is composed of a 6×6 bottom two-dimensional network and a 2×2 upper layer network; the bottom two-dimensional network It is divided into 4 areas; each area contains an intermediate router and several ordinary routers; ordinary routers include five transmission directions; intermediate routers include five transmission directions and one upward transmission direction; the upper network is a transmission router; the transmission router Contains five transmission directions and one downward transmission direction; the intermediate router and the transmission router are connected to each other; when the intermediate router or ordinary router in any area is used as the current routing node and receives the data packet through its own input module, the routing algorithm is Proceed as follows:

Step 1, setting the intermediate router and several ordinary routers all include: 5-bit transmission direction register port_1[4:0] and 5-bit omnidirectional register port_2[4:0]; the intermediate router output port register unit includes: 6-bit The transmission direction register port_1[5:0] and the 6-bit omnidirectional register port_2[5:0]; the transmission direction registers of ordinary routers and intermediate routers are uniformly represented as transmission direction register port_1, and the omnidirectional registers are uniformly represented as omnidirectional register port_2; The transmission direction register port_1 is used to store the transmission direction of the current head microchip; the omnidirectional register port_2 is used to store the transmission directions of all the head microchips, and one bit in the omnidirectional register port_2 represents a transmission direction;

Step 2, the current routing node judges the current flit in the received data packet, if the received current flit is the header flit, then perform step 3; if the received current flit is the body flit slice, execute step 8; if the received current flit is the tail flit, execute step 9;

Step 3, the current routing node judges the header flake again; if the header flit is the header flit of the multicast data packet; then perform step 4; if the header flit is the header flake of the unicast data packet; then directly use XY The routing algorithm calculates the transmission direction downstream of the unicast packet header chip and saves it in the transmission direction register port_1 and the omnidirectional register port_2; then execute step 10;

Step 4, the current routing node judges the transmission direction of the header flake of the multicast data packet, if it is the upward transmission direction, then perform step 5; if it is the downward transmission direction, then perform step 7;

Step 5, the current routing node compares the current routing node's own coordinates with the coordinates of the destination node according to the header chip of the received multicast data packet, if the two coordinates are the same, it means that the current routing node is the destination node , get the transmission direction as the local direction and save it in the transmission direction register port_1 and the omnidirectional register port_2; then execute step 10;

If the two coordinates are adjacent, it means that the current routing node and the destination node are adjacent nodes, and the transmission direction is obtained as the adjacent direction, and judge whether the output port of the current routing node is free. If it is free, save the adjacent direction to the transmission direction In the register port_1 and the omnidirectional register port_2, go to step 10; otherwise go to step 6; if the two coordinates are neither adjacent nor the same, go to step 6 directly;

Step 6, the current routing node calculates the transmission direction downstream of the multicast packet header microchip according to the coordinates of the intermediate router in its own area and saves it in the transmission direction register port_1 and the omnidirectional register port_2; then execute step 10;

Step 7, the current routing node uses the XY routing algorithm to calculate the downstream transmission direction of the multicast packet header flake according to the received multicast packet header flake and saves it in the transmission direction register port_1 and the omnidirectional register port_2; Execute step 10 again;

Step 8. The current routing node copies the transmission direction of all header flits from the omnidirectional register port_2 to the transfer direction register port_1, so as to transmit the body flakes to the downstream routing node according to the transfer direction in the transfer direction register port_1; then return to the step 2;

Step 9, the current routing node copies the transmission direction of all head microchips from the omnidirectional register port_2 to the transmission direction register port_1, thereby transmitting the tail microchip to the downstream routing node according to the transmission direction in the transmission direction register port_1; when the tail microchip At the end of slice transmission, the current routing node clears the transmission direction register port_1 and the omnidirectional register port_2, and then returns to step 2;

Step 10: When the port_2 omnidirectional register receives the input direction of the current microchip, it is judged whether the transmission direction of the current microchip already exists. If it already exists, the current routing node sends the re-arbitration request signal to its own arbitration module, and uses To open the corresponding output port of the crossbar module, otherwise, directly store the input direction of the current microchip;

Step 11, return to step 2.

In a specific implementation, the number of detachable destination nodes on the multicast uplink path is changed. For the underlying 6×6 network, if each 3×3 is divided into an area, the multicast data packet has at most two splittable destination nodes on the uplink path. The experiment takes (1,1) as the source node, and the destination nodes are (2,1), (2,2) and (2,4) respectively, as shown in Figure 3. The data packet is composed of three head flits, three body flits and one tail flits, and a data packet is sent from the source node to the destination node. The delay results of packets under different conditions are shown in Figure 8.

When there is only one splittable node, the average packet delay is reduced by 15.9%; when there are two splittable nodes, the average packet delay is reduced by 22%. It can be seen from this that the more destination nodes on the path that split the transmission, the more the arrival delay of the data packet is reduced compared to the non-split transmission.

Under the same network conditions, the number of adjacent destination nodes of splittable paths is set to 1, 2, 3, 4 respectively.

The number of adjacent splittable nodes is 1: the experiment sets the source node as (3,4), the destination node as (2,2), (3,3), (2,6) and (2,1), one The data contains four head micro-slices, three body micro-slices and one tail micro-slice, as shown in Figure 4.

The number of adjacent splittable nodes is 2: the experiment sets the source node as (3,4), the destination node as (2,2), (3,3), (4,4) and (2,1), one The data contains four head micro-slices, three body micro-slices and one tail micro-slice, as shown in Figure 5.

The number of adjacent splittable nodes is 3: the experiment sets the source node as (3,4), the destination node as (2,2), (3,3), (4,4) and (3,5), one The data contains four head micro-slices, three body micro-slices and one tail micro-slice, as shown in Figure 6.

The number of adjacent splittable nodes is 4: the experiment sets the source node as (3,4), the destination node as (2,3), (3,3), (4,4) and (3,5), one The data contains four head micro-slices, three body micro-slices and one tail micro-slice, as shown in Figure 7.

Based on the experimental conditions set above, the obtained delay results are shown in Fig. 9 . The delay reduction results corresponding to the increase of the number of splittable adjacent nodes from 1 to 4 are 22.7%, 31.5%, 41.4% and 50.3%, respectively. It can be concluded that the more the number of adjacent nodes that can be split, the greater the average delay optimization of data packets.

Claims (2)

1. A two-level split router applied to a hierarchical network-on-chip, wherein the hierarchical network-on-chip is composed of an N×M bottom layer two-dimensional network and an L×S upper layer network; 1≤L<N, 1≤ S<M; the underlying two-dimensional network is divided into L×S areas; each area contains an intermediate router and several ordinary routers; the ordinary router includes five transmission directions; the intermediate router includes five transmission directions direction and an upward transmission direction; the upper network is a transmission router; the transmission router includes five transmission directions and a downward transmission direction; the intermediate router and the transmission router are connected to each other; it is characterized in that, The decoding module in the intermediate router and several ordinary routers is set as a multicast routing calculation module; the multicast routing calculation module includes a classification decoding unit YM, a unicast packet routing calculation unit SR, a multicast uplink data The packet routing calculation unit UR, the multicast downlink data packet routing calculation unit DR and the output port register unit; the multicast uplink data packet routing calculation unit UR includes: a two-stage split unit TS and an ordinary uplink routing calculation unit RC; the output port The register unit includes: m-bit transmission direction register port_1[m-1:0] and m-bit omnidirectional register port_2[m-1:0]; m is the number of transmission directions; the transmission direction register port_1[m- 1:0] is used to store the transmission direction of the current head flits; the omnidirectional register port_2[m-1:0] is used to store the transmission directions of all the head flits; When an intermediate router or common router in any zone is used as a current routing node and receives a data packet through its own input module, the input module of the current routing node sends the microchip in the data packet to its own multicast routing calculation module; The classification decoding unit YM of the current routing node judges the received current flit, if the received current flit is the header flit, the classification decoding unit YM judges the header flit again; If the header flake is the header flake of the multicast data packet; then the transmission direction of the header flake of the multicast data packet is judged, if it is the upward transmission direction, then the header of the multicast data packet is The microchip is sent to the multicast uplink data packet routing calculation unit UR for calculating the transmission direction; if it is the downward transmission direction, the header microchip of the multicast data packet is sent to the multicast downlink data packet routing calculation unit DR for calculation transmission direction; If the header flake is the header flake of the unicast data packet; then the header flake of the unicast data packet is sent to the unicast data packet routing calculation unit SR for calculating the transmission direction; If the received current flit is a body flit, then the output port register unit copies the transfer directions of all header flits from the omnidirectional register port_2[m-1:0] to the transfer direction register port_1[m-1 :0], the input module of the current routing node transmits the microchip to the downstream routing node according to the transmission direction of the transmission direction register port_1[m-1:0] in the output port register unit; If the received current flit is a tail flit, the output port register unit copies the transfer directions of all head flits from the omnidirectional register port_2[m-1:0] to the transfer direction register port_1[m-1 :0], the input module of the current routing node transmits the tail chip to the downstream routing node according to the transmission direction of the transmission direction register port_1[m-1:0] in the output port register unit; then, the classification decoding of the current routing node The unit YM sends a data packet transmission end signal to the output port registration unit; the output port registration unit clears the output port registration unit of the current routing node according to the received data packet transmission end signal; The two-level splitting unit TS of the multicast uplink data packet routing calculation unit UR compares the current routing node's own coordinates with the destination node's coordinates according to the header flake of the received multicast data packet, If the two coordinates are the same, it means that the current routing node is the destination node, and the obtained transmission direction is the local direction and stored in the output port storage unit; If the two coordinates are adjacent, it means that the current routing node and the destination node are adjacent nodes, and the transmission direction is obtained as an adjacent direction, and the two-stage splitting unit TS judges whether the output port of the current routing node is idle, if idle, Then store the adjacent direction in the output port register unit; if it is not idle, then do not store the adjacent direction, and transmit the header flake of the multicast data packet to the common uplink routing calculation unit RC; If the two coordinates are neither adjacent nor the same, then directly transmit the header flake of the multicast data packet to the common uplink routing calculation unit RC; Coordinates, calculate the transmission direction downstream of the multicast packet header chip, and save it to the output port storage unit of the current routing node; The multicast downlink data packet routing calculation unit DR uses the XY routing algorithm to calculate the downstream transmission direction of the multicast data packet header flake according to the received multicast data packet header flake, and saves it to the output of the current routing node Port register unit; The unicast data packet routing calculation unit SR uses the XY routing algorithm to calculate the downstream transmission direction of the unicast data packet header microchip according to the received unicast data packet header microchip, and saves it to the output port storage unit of the current routing node ; When the omnidirectional register port_2[m-1:0] receives the input direction of the current microchip, it is judged whether the transmission direction of the current microchip already exists, if it already exists, the multicast routing calculation module of the current routing node will re- The arbitration request signal is sent to its own arbitration module, which is used to open the corresponding output port of the crossbar module, otherwise, directly store the input direction of the current microchip. 2. A routing algorithm for a two-stage split router applied to a hierarchical network-on-chip, wherein the hierarchical network-on-chip is composed of a bottom two-dimensional network of N×M and an upper layer network of L×S; 1≤L<N , 1≤S<M; the underlying two-dimensional network is divided into L×S areas; each area contains an intermediate router and several ordinary routers; the ordinary router includes five transmission directions; the intermediate router includes Five transmission directions and one upward transmission direction; the upper layer network is a transmission router; the transmission router includes five transmission directions and one downward transmission direction; the intermediate router is connected to the transmission router; it is characterized in that , when using an intermediate router or common router in any zone as the current routing node and receiving data packets through its own input module, the routing algorithm is performed as follows: Step 1, setting described intermediate router and several ordinary routers all comprise: m-bit transmission direction register port_1[m-1:0] and m-bit omnidirectional register port_2[m-1:0]; m is the transmission direction register port_2[m-1:0]; number; the transfer direction register port_1[m-1:0] is used to store the transfer direction of the current head flits; the omnidirectional register port_2[m-1:0] is used to store the transfer directions of all head flits ; Step 2, the current routing node judges the current flit in the received data packet, if the received current flit is the header flit, then perform step 3; if the received current flit is the body flit slice, execute step 8; if the received current flit is the tail flit, execute step 9; Step 3, the current routing node judges the header flake again; if the header flake is the header flake of a multicast data packet; then perform step 4; if the header flake is the header of a unicast packet Microchip; then directly use the XY routing algorithm to calculate the transmission direction downstream of the unicast packet header microchip and save it in the transmission direction register port_1[m-1:0] and the omnidirectional register port_2[m-1:0]; then Execute step 10; Step 4, the current routing node judges the transmission direction of the header flake of the multicast data packet, if it is the upward transmission direction, then perform step 5; if it is the downward transmission direction, then perform step 7; Step 5, the current routing node compares the self coordinates of the current routing node with the coordinates of the destination node according to the header chip of the received multicast data packet, if the two coordinates are the same, it means that the current routing node is The destination node obtains the transmission direction as the local direction and saves it in the transmission direction register port_1[m-1:0] and the omnidirectional register port_2[m-1:0]; then execute step 10; If the two coordinates are adjacent, it means that the current routing node and the destination node are adjacent nodes, and the transmission direction is obtained as the adjacent direction, and judge whether the output port of the current routing node is free. If it is free, save the adjacent direction to the transmission direction In register port_1[m-1:0] and omnidirectional register port_2[m-1:0], go to step 10; otherwise go to step 6; if the two coordinates are neither adjacent nor the same, go to step 6 directly; Step 6. The current routing node calculates the transmission direction downstream of the multicast packet header chip according to the coordinates of the intermediate router in its own area and saves it in the transmission direction register port_1[m-1:0] and the omnidirectional register port_2[m-1 :0]; execute step 10 again; Step 7. The current routing node uses the XY routing algorithm to calculate the downstream transmission direction of the multicast packet header flake according to the received multicast packet header flake and saves it in the transmission direction register port_1[m-1:0] and in the omnidirectional register port_2[m-1:0]; then perform step 10; Step 8. The current routing node copies the transmission direction of all header flits from the omnidirectional register to the transmission direction register port_1[m-1:0], so that according to the transmission direction in the transmission direction register port_1[m-1:0] Transmit volume microchips to downstream routing nodes; return to step 2; Step 9, the current routing node copies the transmission direction of all header flits from the omnidirectional register port_2[m-1:0] to the transmission direction register port_1[m-1:0], thereby according to the transmission direction register port_1[m-1:0] 1:0] transfers the tail microchip to the downstream routing node; when the tail microchip transmission ends, the current routing node transmits the direction register port_1[m-1:0] and the omnidirectional register port_2[m-1 :0] to zero, and then return to step 2; Step 10, when the omnidirectional register port_2[m-1:0] receives the input direction of the current microchip, it is judged whether the transmission direction of the current microchip already exists, if it already exists, the arbitration request of the current routing node will be re-arbitrated The signal is sent to its own arbitration module to open the corresponding output port of the crossbar switch module, otherwise, directly store the input direction of the current microchip; Step 11, return to step 2.