CN118301061A

CN118301061A - On-chip network data packet transmission method based on recursive partitioning

Info

Publication number: CN118301061A
Application number: CN202410394790.XA
Authority: CN
Inventors: 欧阳一鸣; 张怡鹤; 李建华; 梁华国
Original assignee: Hefei University of Technology
Current assignee: Hefei University of Technology
Priority date: 2024-04-02
Filing date: 2024-04-02
Publication date: 2024-07-05

Abstract

The invention discloses a network-on-chip data packet transmission method based on recursive partitioning, which comprises an A X B two-dimensional mesh network with the scale of A X B, wherein the two-dimensional mesh network consists of A X B routers and A X B processing units; through a multicast routing algorithm of the recursive partitioning, the network is partitioned continuously in the data packet transmission process, and the average hop count of multicast data packets is reduced effectively; meanwhile, the invention adds a data packet processing unit to provide single-period per-hop transmission between the source router and the destination router for multicast data packets, thereby improving the transmission efficiency of the data packets.

Description

On-chip network data packet transmission method based on recursive partitioning

Technical Field

The invention belongs to the technical field of integrated circuit chip design and application, and particularly relates to a network-on-chip data packet transmission method based on recursive partitioning.

Background

With the continued development of very large scale integrated circuits, the number of transistors integrated on a chip has reached several billions. This has prompted researchers to integrate multiple IP cores on one integrated circuit, forming a multi-core system. Multi-core systems are popular with increasingly multi-chip designers due to their good parallelism and scalability. Network on chip (NoC) has attracted attention by researchers as a new communication structure. The method uses a router to connect Processing Elements (PE) by referring to the communication mode of the distributed computing system, and adopts a packet switching technology to support a plurality of IP cores to simultaneously carry out data transmission, thereby remarkably improving the throughput of the system and realizing better flexibility and lower power consumption.

A typical network-on-chip consists of routers (responsible for data communications), processing units (performing computing tasks), channels and resource network interfaces. The connection between the processing unit and the router is called topology, and the planar silicon geometry is matched with the 2D mesh topology, so that it is the most common choice, and it also improves the scalability and throughput of the system. Under a given topology, the routing algorithm is responsible for determining the transmission path of a data packet from a source router to a destination router. When the input buffer receives a packet, the routing algorithm selects the appropriate output port for it and forwards it to the next router. The balanced traffic capability of the routing algorithm directly affects the performance and throughput of the network on chip.

With the proliferation of parallel applications, multicast services are becoming more and more necessary. Common multicast strategies are path-based and tree-based. In the path-based method, a data packet shares a path connecting all destinations in the transmission process, and after reaching one destination router, the data packet is started to be copied and transmitted to the next destination router. The path-based multicast routing algorithm has the characteristics of simple hardware implementation, strong expansibility and the like, but when the network scale is increased, the path-based multicast routing algorithm can cause communication congestion, and the average hop count of the data packet is also increased. In tree-based routing algorithms, packets are first transmitted along a common path, and the packets are replicated as the branches are encountered. The tree-based routing algorithm reduces the average packet hops to some extent, however the efficiency and deadlock issues of the algorithm require further optimization by researchers.

While tree-based multicast routing algorithms have been the choice for most researchers due to their high efficiency and flexibility, the following problems remain with the prior art: firstly, determining when and where to replicate multicast packets, an inefficient replication strategy can reduce network performance and increase link overhead; and secondly, the problem of routing the data packet, how to find the most efficient path in a complex network to transmit the data packet to a destination node, is required to be continuously and optimally solved by researchers.

Disclosure of Invention

The invention aims to avoid the defects in the prior art and provides a network-on-chip data packet transmission method based on recursive partitioning, so as to improve the utilization rate of system bandwidth, reduce the average hop count of data packets and improve the transmission efficiency of the system.

The invention adopts the following technical scheme for solving the technical problems:

the invention relates to a recursive partitioning-based network-on-chip data packet transmission method, wherein the network-on-chip comprises an A X B two-dimensional mesh network with the scale of A X B, which is composed of A X B routers and A X B processing units; wherein A and B are integers greater than 2; the router includes: east, west, south, north and local input and output ports, an input buffer, a routing table, a route calculation unit, a reconfigurable crossbar, a 4:1 multiplexer, three demultiplexers and a link configuration unit; the processing unit includes: the system comprises a processing core, an input interface and an output interface; the local input and output ports of the A X B routers are respectively connected with the output and input interfaces of the A X B processing units; the first two demultiplexers are connected through an input buffer area; the data packets are divided into multicast data packets and unicast data packets; the fields of the multicast data packet include: packet type, destination router address vector; the address vector of the destination router is an A multiplied by B bit address, each bit address corresponds to the position of the router, and when one bit address is 1, the router at the corresponding position is the destination router of the data packet; the fields of the unicast data packet include: the type of the data packet, the address vector of the destination router and the timestamp; the router is characterized in that a data packet processing unit is arranged in the router, and the data packet transmission method is carried out according to the following steps:

Step 1, when an input port of a current router receives a data packet, a data packet processing unit of the current router judges whether the current data packet is a unicast data packet or a multicast data packet according to the type of the data packet;

if the data packet type is multicast, executing the step 2; otherwise, executing the step 9;

Step 2, the data packet processing unit firstly detects whether the address vectors of the destination routers are all 0, if so, the multicast data packet is deleted, and the step 1 is returned; otherwise, executing the step 3;

step 3, comparing the coordinates stored in the routing table of the current router with the address vector of the destination router to judge whether the data packet reaches the destination router;

If the data packet reaches the destination router, executing the step 4; otherwise, executing the step 5;

Step 4, the data packet processing unit performs non-operation on '1' in the address vector of the destination router so that the address vectors of the router are all '0', establishes a multicast bypass bypassing the input buffer area between the first two demultiplexers, and sends the data packet processing unit to the 4:1 multiplexer through the multicast bypass after generating a gating signal; transmitting the gating signal to a local output port of the current router through a 4:1 multiplexer, and transmitting the data packet to a processing core through an input interface of a processing unit by the local output port according to the gating signal, thereby completing the transmission of the data packet;

Step 5, the data packet processing unit sends the data packet to the route calculation unit together with the coordinates in the route table of the current router;

step 6, the route calculation unit decodes the address vector of the destination router in the received multicast data packet to obtain a destination list, thereby identifying the number of the router where the destination router is located;

Step 7, the route calculation unit takes the current router as a center, uniformly divides the two-dimensional mesh network into eight areas, and copies the multicast data packet according to the number of the destination routers in the destination list, so that the multicast data packet and a plurality of copies thereof are sent to the reconfigurable crossbar switch through a multicast bypass, the route calculation unit generates a gating signal and sends the gating signal to the later demultiplexer, and the demultiplexer sends the gating signal to the reconfigurable crossbar switch;

Step 8, the reconfigurable crossbar establishes a path which directly reaches the direction of an output port for the multicast data packet and a plurality of copies of the multicast data packet through a link configuration unit according to the gating signal, so that the multicast data packet and the plurality of copies of the multicast data packet are respectively and correspondingly sent to an input port of a next-hop router with a destination router area by using a YX routing algorithm, and the next-hop router continues to execute according to the step 1;

Step 9, the data packet processing unit transmits the unicast data packet to an input buffer area of the current router and stores the unicast data packet in a first-in first-out mode;

If the input port of the unicast data packet participates in the establishment of the multicast bypass and the path, the unicast data packet waits for the path to be idle and then is sent to the reconfigurable crossbar switch along the multicast bypass, so that the unicast data packet is transmitted to the corresponding output port along the path in the reconfigurable crossbar switch, and is continuously executed according to the step 1 after being received by the input port of the next hop router;

If the input port of the unicast data packet does not participate in the establishment of the multicast bypass and the path, the data packet processing unit checks whether the time stamp of the unicast data packet is full, if so, the unicast data packet reaches the reconfigurable crossbar switch after passing through the demultiplexer from the input buffer area and is finally sent to the output port, and after being received by the input port of the next hop router, the unicast data packet is continuously executed according to the step 1; if not, the unicast packet continues to be queued in the input buffer.

The electronic device of the invention comprises a memory and a processor, wherein the memory is used for storing a program for supporting the processor to execute the network-on-chip data packet transmission method, and the processor is configured to execute the program stored in the memory.

The invention relates to a computer readable storage medium, on which a computer program is stored, characterized in that the computer program, when being executed by a processor, performs the steps of the network-on-chip data packet transmission method.

Compared with the prior art, the invention has the following effects:

1. according to the flow characteristics of the network-on-chip platform, the invention designs a multicast algorithm based on the network-on-chip recursive partitioning, the network is divided into eight areas according to the position of the central router, and after the data packet reaches a new partition, the network is continuously recursively partitioned by taking the current router as the center until all the destination routers are traversed, thereby improving the transmission efficiency of the multicast data packet.

2. In order to reduce the copying times of the data packet to the maximum extent and improve the network bandwidth efficiency, the invention defines the copying priority of the data packet in the transmission direction.

3. The invention adds the data packet processing unit on the basis of the traditional router architecture, provides single-period per-hop transmission for the multicast data packet from the source router to the destination router, and reduces the transmission delay of the data packet.

Drawings

FIG. 1 is a schematic diagram of a router architecture of the present invention;

FIG. 2 is a diagram of two packet formats according to the present invention;

Fig. 3 is a schematic diagram of a multicast path transmission procedure according to the present invention;

FIG. 4 is a schematic diagram of a router partition of the present invention;

FIG. 5 is a schematic diagram of a routing priority rule of the present invention;

fig. 6 is a schematic diagram of multicast packet transmission according to the present invention.

Detailed Description

In this embodiment, a network-on-chip in a method for transmitting a network-on-chip packet based on recursive partitioning is a two-dimensional mesh network with a size of a×b, which is composed of a×b routers and a×b processing units; wherein A and B are integers greater than 2; the router includes: east, west, south, north and local input, output ports, packet processing units, input buffers, routing tables, route calculation units, reconfigurable crossbar switches, 4:1 multiplexers, three demultiplexers, link configuration units, as shown in fig. 1; the input/output port is used for connecting other routers or processors; the input buffer is used for storing data packets or flits which cannot be immediately sent to the output port; the routing table stores the coordinate information of the current router; the route calculation unit calculates the output port of the unicast data packet; the invention adds a data packet processing unit based on the traditional router architecture, and is mainly responsible for identifying the multicast data packet type and modifying the address information of the multicast data packet. Meanwhile, the traditional crossbar is replaced by a reconfigurable crossbar, a special link can be formed among a plurality of routers, and when a data packet arrives at a destination router, the data packet is directly sent to an output port from an output port multiplexer without passing through the crossbar. The processing unit includes: the system comprises a processing core, an input interface and an output interface; the local input and output ports of the A X B routers are respectively connected with the output and input interfaces of the A X B processing units; the first two demultiplexers are connected through an input buffer area;

The data packets are divided into multicast data packets and unicast data packets, and the data packet structure is shown in fig. 2; the fields of the multicast data packet include: packet type, destination router address vector, VN identifier, source router coordinates, payload; the data packet type field occupies 1bit and is used for identifying the data packet type, and when the data packet type field is 1, the data packet type is multicast; if 0, unicast is adopted; the address vector of the destination router is an A x B bit address, each bit vector corresponds to routers in the network one by one, and when one bit is 1, the corresponding router is the destination router of the data packet.

After the data packet reaches one of the destination routers and is output, the data packet processing unit sets 1 in the destination address corresponding to the router to 0; the invention adopts a bit string coding mode to put the destination router identifier of the multicast data packet into the header. A one-bit VN identifier is used in the packet header to indicate the different VN partitions and this bit is defined during the route calculation phase as shown in part (a) of fig. 2. This bit is defined as either 0 or 1 depending on whether the destination is above or below the source router. At the same time, the intermediate router does not change the VN identifier. When the destination router is on the left and right sides of the current router, the current router will make two copies and send corresponding VN identifiers to the left and right sides, respectively. In this way, some steering of the data packet is forbidden in the transmission process, so that the network deadlock is effectively avoided. The source router coordinates record the start address of the packet, the payload data carried by the payload packet, and its number of bits varies with the particular application.

As in part (b) of fig. 2, the fields of the unicast packet include: the data packet type, destination router address vector, timestamp, source router coordinates, payload; the address vector of the destination router of the unicast data packet occupies 12 bits in total and represents the destination coordinate of the destination router in the mesh network; the time stamp occupies (n-12) bits, and since the multicast packet priority is specified to be higher than that of the unicast packet in this embodiment, in order to prevent the unicast packet from waiting all the time in the network, when the time stamp of a certain unicast packet is higher than the set maximum value, the unicast packet will be sent preferentially. The source router coordinates and the payload are used to record the initial sending address of the data packet and the valid data carried by the data packet, respectively.

The router is provided with a data packet processing unit, and the data packet transmission method comprises the following steps:

if the data packet reaches the destination router, executing the step 4; otherwise, step 5 is performed.

Step 4, the data packet processing unit performs non-operation on '1' in the address vector of the destination router so that the address vectors of the router are all '0', establishes a multicast bypass bypassing the input buffer area between the first two demultiplexers, and sends the multicast bypass to the 4:1 multiplexer after generating a gating signal; transmitting the strobe signal to an output port local to the current router via a 4:1 multiplexer, the transmission path being as shown in FIG. 3; the local output port sends the data packet to the processing core through the input interface of the processing unit according to the gating signal, thereby completing the transmission of the data packet.

And 7, if the data packet is transmitted by adopting a traditional unicast mode, a large number of repeated data packets are generated in the network, so that network bandwidth is consumed, and network congestion and data packet delay are caused. Therefore, the present invention proposes a multicast routing algorithm based on recursive partitioning, which first divides the whole network into at most eight parts according to the locations of the source router and the destination router, and the partitioning manner is shown in fig. 4. And recursively calling the partition function in the data packet transmission process, and continuously dividing the rest network. Each time a packet arrives at one of the destination routers, a copy of the packet is created for the output port and destination routing information for the copy is updated, and this process is repeated until all of the destination routers are accessed. Typically during the route calculation phase, the route calculation component needs to determine the identifier of the output port from the destination list of the header. For unicast packets, the route calculation component may directly calculate its output port, but this approach is not applicable to multicast packets. A multicast packet may contain more than one output port. In order to reduce the copying times of the data packet to the maximum extent and improve the network bandwidth efficiency, the invention defines the copying priority of the data packet.

The following is shown:

in the northeast direction (part 0), the north direction has a higher priority than the eastern direction; in the northwest direction (part 2), the western direction has a higher priority than the northern direction, as shown in part (a) of fig. 5;

in the southwest direction (part 4), the southwest direction has a higher priority than the southwest direction; in the southeast direction (part 6), the southward direction has a higher priority than the eastern direction as shown in part (b) of fig. 5;

When there are destination routers in both northeast and northwest parts, both parts use northbound replication. Likewise, the destination routers in the southeast and southwest parts all use southwest replication, as shown in part (c) of fig. 5;

When there is a destination router in part 0, part 1 and no part 2, the destination router in part 1 will use northbound replication. The same applies in the south, as shown in part (d) and part (e) in fig. 5.

In order to prevent the same router from being repeatedly grouped in the partitioning process, the invention provides that the data packet can only detect the destination router in the moving direction, thereby realizing simultaneous transmission in multiple directions. Fig. 6 illustrates the operation of the algorithm, assuming that router 10 is the source router of the 4 x 4 network, when it initiates a multicast packet, the algorithm divides the entire network into 8 parts, centered around router 10, according to the destination list described above. Wherein the target router is located in 4 parts (0, 2, 4, 5). According to the priority rule, router 10 first replicates a copy of the packet and sends the original packet and copy to north router No. 6 and south router No. 14, respectively.

The algorithm then partitions the network with router 6 as the central router. In this embodiment it is provided that it only sees the target routers (0, 3, 5) in the north direction, which are located in parts 0, 2, 3. Router 6 replicates the copy, the original packet is sent to router No. 2 north, and the copy is sent to router No. 5 (destination). The packet on router 14 also needs to replicate a copy and, because it is the destination router, can send the copy directly to the pop-up window and another packet to the western-style router No. 13.

The destination router 0, 3 of the router 2 is located in the 0, 1 part. Thus, a copy of the packet is made, and the original packet and copy are sent to the east and west, respectively. The router 13 finds that the target router 12 is located in section 5 and directly sends the packet to the west without any duplication. The partition transfer operation is continued in the next router route calculation stage until all destination routers receive the data packet.

After obtaining the data packet output port information, the routing computation unit sends the multicast data packet and a plurality of copies thereof to the reconfigurable crossbar through a multicast bypass, the routing computation unit generates a gating signal and sends the gating signal to the later demultiplexer, and the demultiplexer sends the gating signal to the reconfigurable crossbar;

Step 8, the reconfigurable crossbar establishes a path which directly reaches the direction of the output port for the multicast data packet and a plurality of copies thereof through a link configuration unit according to the gating signal, so that the multicast data packet and the plurality of copies thereof are respectively and correspondingly transmitted to the input port of the next-hop router with the destination router area by using a YX routing algorithm, and the next-hop router continues to execute according to the step 1;

step 9, the data packet processing unit transmits the unicast data packet to the input buffer area of the current router and stores the unicast data packet in a first-in first-out mode;

If the input port of the unicast data packet participates in the establishment of the multicast bypass and the path, the unicast data packet is sent to the reconfigurable cross switch along the multicast bypass after waiting for the idle path, so that the unicast data packet is transmitted to the corresponding output port along the path in the reconfigurable cross switch, and is continuously executed according to the step 1 after being received by the input port of the next hop router;

In this embodiment, an electronic device includes a memory for storing a program supporting the processor to execute the above method, and a processor configured to execute the program stored in the memory.

In this embodiment, a computer-readable storage medium stores a computer program that, when executed by a processor, performs the steps of the method described above.

The multicast scheme based on the recursion partition defines the replication priority of the data packet in the transmission direction, and increases the path diversity and improves the system bandwidth. Meanwhile, a router architecture of each hop of a single period is designed, and the transmission efficiency of multicast data packets is effectively improved.

Claims

1. A network-on-chip data packet transmission method based on recursive partitioning, wherein the network-on-chip is a two-dimensional mesh network with the size of A×B, which consists of A×B routers and A×B processing units; wherein A and B are integers greater than 2; the router includes: east, west, south, north and local input and output ports, an input buffer, a routing table, a route calculation unit, a reconfigurable crossbar, a 4:1 multiplexer, three demultiplexers and a link configuration unit; the processing unit includes: the system comprises a processing core, an input interface and an output interface; the local input and output ports of the A X B routers are respectively connected with the output and input interfaces of the A X B processing units; the first two demultiplexers are connected through an input buffer area; the data packets are divided into multicast data packets and unicast data packets; the fields of the multicast data packet include: packet type, destination router address vector; the address vector of the destination router is an A multiplied by B bit address, each bit address corresponds to the position of the router, and when one bit address is 1, the router at the corresponding position is the destination router of the data packet; the fields of the unicast data packet include: the type of the data packet, the address vector of the destination router and the timestamp; the router is characterized in that a data packet processing unit is arranged in the router, and the data packet transmission method is carried out according to the following steps:

2. An electronic device comprising a memory and a processor, wherein the memory is configured to store a program that supports the processor to perform the network-on-chip packet transmission method of claim 1, the processor being configured to execute the program stored in the memory.

3. A computer readable storage medium having stored thereon a computer program, characterized in that the computer program when executed by a processor performs the steps of the network-on-chip data packet transmission method of claim 1.