CN106453072A - Greedy distribution method and device of on-chip network router channel resources and router - Google Patents

Abstract

The present invention provides a method for greedily allocating channel resources of a network-on-chip router, which is applicable to the field of network-on-chip technology. The greedy allocation method is performed before the internal input port and output port of the router are mapped in the crossbar allocation stage, including: In the preprocessing step, when the data packet enters the sub-channel and virtual channel of the input port, the data packet information is classified and processed to obtain a preprocessing information table; the execution step is based on the preprocessing information table and the data packet Corresponding to the size of the output port, select a maximum number of the data packets to match the sub-channel and the output port. At the same time, it also provides a device for greedily allocating channel resources of the on-chip network router. Thereby, the present invention uses the idea of greedy algorithm to match the channel between the input port and the output port, so as to achieve the mapping that tends to be optimal and improve the utilization rate of the channel.

Description

Greedy allocation method, device and router for on-chip network router channel resources

technical field

The present invention relates to the field of on-chip network technology, in particular to a greedy allocation method, device and router for on-chip network router channel resources.

Background technique

In large-scale many-core processors, in order to meet the data transmission requirements among many-cores, the network-on-chip is playing an increasingly important role. With the diversification and complexity of Internet-oriented, cloud computing and other service applications, the types of data packets transmitted in the network-on-chip are also becoming more diverse and complex. At the same time, in order to reduce Cache power consumption and improve Cache performance and utilization, fine-grained Cache management has been proposed by more and more research work. Therefore, the size of data packets transmitted in the network is no longer the regular Cache block size, and data packet sizes of various granularities (control information + small-grained memory access) shuttle in the network, seriously reducing the traditional fixed-width on-chip network channel. utilization rate. In response to this phenomenon, numerous research works have proposed a fine-grained on-chip network partition mechanism, which divides a fixed-width on-chip network into multiple fine-grained link channels, so that data packets of different sizes can be adaptively transmitted, and the network on a chip can be improved. effective utilization rate.

Among the related domestic and foreign researches that have been reported and can be consulted, the research on channel resource allocation algorithms of network-on-chip routers can be listed, analyzed, and summarized as follows:

Hesse et al. proposed to split wide-channel links into fine-grained channel widths, and at the same time, data packets also become packets consistent with the fine-grained channel widths. Moreover, the channel is set as a two-way variable channel, and the transmission direction of the channel is dynamically adjusted according to the flow pressure of the two-way data packets.

Krishna et al. based on the fact that a large number of data packets usually share some transmission channels, so they proposed to combine small data packets sharing the same route and then transmit them, split the merged data packets with different destinations and transmit them to different directions, and improve the channel. utilization rate. Typically such packets appear in a network-on-chip that supports a broadcast mechanism.

Jin et al. proposed to compress the data packets, and the compressed data packets can share the same transmission channel, thereby improving the utilization rate and throughput of the transmission channel.

Junghee Lee et al. proposed fine-grained on-chip channel control and combined with the "stealing" and "sharing" technology of data packets in different virtual channels to improve the utilization of port virtual channels, reduce the delay of data packet transmission, and improve transmission efficiency.

Reetuparna Das et al. proposed a flexible arbitration management mechanism between input ports and output ports inside a router. For input ports that apply for the same output port, if there are small data packets in both input ports, then the small data packets are transmitted to the output port at the same time, improving the parallelism of data transmission and improving the effective utilization of the channel .

With the gradual increase of on-chip data processing units, the transmission performance of on-chip networks will receive more and more attention and pressure. The emergence of new big data network service applications has put forward higher requirements for traditional on-chip networks. Therefore, how to further improve the transmission efficiency of the network on chip will also become one of the hot directions that researchers continue to explore.

In summary, there are obviously inconveniences and defects in the actual use of the prior art, so it is necessary to improve it.

Contents of the invention

In view of the above-mentioned defects, the purpose of the present invention is to provide a road network implementation method, device and router of a high-density network-on-chip. The efficient allocation of channel resources realizes the locally optimal arbitration mapping algorithm for the input port and output port inside the router.

In order to achieve the above object, the present invention provides a method for greedily allocating network-on-chip router channel resources. The greedy allocation method is carried out before the cross-bar switch allocation stage of the network-on-chip router is mapped to the internal input port and output port of the router, including :

A preprocessing step, when a data packet enters the sub-channel and the virtual channel of the input port, classify the data packet information to obtain a pre-processing information table;

Executing a step of selecting a maximum number of data packets to match the sub-channel and the output port according to the preprocessing information table and the size of the output port corresponding to the data packet.

According to the greedy allocation method of network-on-chip router channel resources of the present invention, the preprocessing step also includes:

When the data packet is transmitted to the input port, collecting routing calculation processing results;

Create an independent preprocessing information table according to the packet information calculated by routing according to the expected output port classification;

Updating the expected output port of the data packet of each subchannel to the corresponding preprocessing information table;

The preprocessing information table includes subport information of the output port sent to, size information of the data packet, and/or information of the subchannel occupied by the data packet.

According to the greedy allocation method of network-on-chip router channel resources of the present invention, the execution step also includes:

Polling and selecting one of the input ports as a reference port by a polling algorithm;

The polling algorithm polling includes selecting different input ports in turn, each selection is performed i=(i+1) mod n, and the i-th port is selected, and n is the total number of ports; all of the reference ports said data packets are preferentially transmitted to the same said output port.

According to the greedy allocation method of network-on-chip router channel resources of the present invention, the step of preferentially transmitting the data packets of the reference port to the same output port further includes:

If the sub-channels of the reference port all have the data packets expected to be sent to the same output port, then no longer select the data packets of the subsequent sub-channels of the input port;

If the data packets in the sub-channels of the reference port do not fill up the transmission link, sequentially select the data packets of the subsequent input ports.

According to the greedy allocation method of network-on-chip router channel resources of the present invention, it also includes:

Perform virtual channel allocation before the greedy allocation method of channel resources of the network-on-chip router;

The data packet is transmitted in the crossbar allocation stage according to the processing result of the greedy allocation method of the network-on-chip router channel resources.

The present invention is a greedy allocation device for network-on-chip router channel resources, the greedy allocation device is set in the router, and the greedy allocation device includes:

A pre-processing module, configured to classify the data packet information to obtain a pre-processing information table when the data packet enters the sub-channel and the virtual channel of the input port;

An execution module, configured to select a maximum number of data packets to match the sub-channel and the output port according to the preprocessing information table and the size of the output port corresponding to the data packet.

According to the greedy allocation device of network-on-chip router channel resources of the present invention, the preprocessing module further includes:

The routing collection submodule is used to collect the routing calculation processing results when the data packet is transmitted to the input port; the information processing submodule is used to classify the output port to which the data packet information according to the routing calculation is expected to be sent creating a separate table of said preprocessing information;

An information update submodule, configured to update the expected output port of the data packet of each subchannel to the corresponding preprocessing information table;

The preprocessing information table includes subport information of the output port sent to, size information of the data packet, and/or information of the subchannel occupied by the data packet.

According to the device for greedily allocating network-on-chip router channel resources of the present invention, the execution module further includes:

A reference selection sub-module, configured to use a polling algorithm to poll and select one of the input ports as a reference port;

The polling algorithm polling includes selecting different input ports in turn, each selection is performed i=(i+1) mod n, and the i-th port is selected, and n is the total number of ports;

The local priority sub-module is configured to preferentially transmit the data packets for the reference port to the same output port.

According to the device for greedily allocating network-on-chip router channel resources of the present invention, the execution module further includes:

The first selection sub-module is configured to no longer select the data of the subsequent sub-channels of the input port if the data packets in the sub-channels of the reference port are expected to be sent to the same output port Bag;

The second selection submodule is configured to sequentially select the data packets of the subsequent input ports if the data packets in the sub-channels of the reference port do not fill up the transmission link.

The present invention also provides a router including the device for greedily allocating network-on-chip router channel resources as described above.

The present invention adds a greedy allocation device with a preprocessing module and an execution module inside the router, and uses the idea of greedy algorithm to perform an optimal mapping between the input port and the output port inside the router, which is suitable for fine-grained channel networks. The traditional on-chip wide channel is divided into low-width sub-transmission channels. In the fine-grained on-chip network router, after the data packets of each sub-channel are routed and calculated, the information of the sub-channel is updated to the preprocessing information table, and the execution module Through the processing of the preprocessing table information, the channel matching between the input port and the output port is realized, the mapping tends to be optimal, and the utilization rate of the channel is improved.

Description of drawings

Fig. 1 is the greedy distribution device structure schematic diagram of the greedy distribution device of network-on-chip router channel resource of the present invention;

Fig. 2 is a schematic structural diagram of a preferred embodiment of the greedy allocation device of the greedy allocation device of the network-on-chip router channel resources of the present invention;

Fig. 3 is a schematic diagram of a specific embodiment of a router of a device for greedily allocating network-on-chip router channel resources according to the present invention;

Fig. 4 is a schematic flow chart of a greedy allocation method of network-on-chip router channel resources of the present invention;

Fig. 5 is a schematic diagram of an embodiment of a greedy allocation method of network-on-chip router channel resources in the present invention;

Fig. 6 is a schematic diagram of a mesh network of a specific embodiment realized by a method for greedy allocation of network-on-chip router channel resources;

Fig. 7 is a schematic diagram of a specific embodiment of the method for greedily allocating network-on-chip router channel resources of the present invention and a complete flow of data packet processing;

Fig. 8 is a schematic diagram of execution steps of a specific embodiment of a method for greedily allocating network-on-chip router channel resources of the present invention;

FIG. 9 is a schematic diagram of the transmission state of the method for greedy allocation of network-on-chip router channel resources according to the present invention.

detailed description

In order to make the object, technical solution and advantages of the present invention clearer, the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain the present invention, not to limit the present invention.

In order to solve the above-mentioned problems, the present invention provides a device for greedily allocating network-on-chip router channel resources. With reference to illustrations, as shown in FIGS. include:

A pre-processing module 41, configured to classify the data packet information to obtain a pre-processing information table when the data packet enters the sub-channel and the virtual channel of the input port;

The execution module 42 is configured to select a maximum number of the data packets to match the sub-channel and the output port according to the preprocessing information table and the size of the output port corresponding to the data packet.

Further, as shown in Figure 3, the greedy distribution device 40 also includes:

The routing collection sub-module 411 is used to collect routing calculation processing results when the data packet is transmitted to the input port;

Correspondingly, as shown in Figure 2, the preprocessing module 41 also includes:

The information processing sub-module 412 is configured to create an independent preprocessing information table according to the expected output port classification of the data packet information calculated by routing;

An information update submodule 413, configured to update the expected output port of the data packet of each subchannel to the corresponding preprocessing information table;

The preprocessing information table includes subport information of the output port sent to, size information of the data packet and/or information of the subchannel occupied by the data packet, specifically refer to FIG. 9 .

Further, the greedy allocation device 40, preferably, the execution module 42 also includes:

A reference selection submodule 421, configured to use a polling algorithm to poll and select one of the input ports as a reference port;

The reference selection sub-module 421 is also used to sequentially select different input ports in a polling manner, and execute i=(i+1) mod n each time to select the i-th port, where n is the total number of ports;

A local priority sub-module 422, configured to preferentially transmit the data packets of the reference port to the same output port;

The first selection sub-module 423 is configured to no longer select the sub-channel of the subsequent input port if the data packets in the sub-channels of the reference port are expected to be sent to the same output port. data pack;

The second selection sub-module 424 is configured to sequentially select the data packets of the subsequent input ports if the data packets in the sub-channel of the reference port do not fill up the transmission link.

Corresponding to the greedy allocating device 40, the present invention provides a router 100 including the greedy allocating device 40 for network-on-chip router channel resources as described above. A specific embodiment shown in Figure 3, router 100 also includes:

A route calculation module 20, configured to perform route calculation when the data packet is transmitted to the input port;

The virtual channel allocator 30 is used to perform virtual channel allocation before the greedy allocation method of the network-on-chip router channel resources; the crossbar allocator 50 is used to perform the virtual channel allocation according to the processing result of the greedy allocation method of the network-on-chip router channel resources. The data packet is transmitted in the allocation stage; the sub-channel of the router 100 and the output port adopt a full-associative mapping manner.

The general idea of the present invention is: generally there are virtual channel allocation (VirtualChannel Allocation, VA), route calculation (Route Computing, RC), crossbar allocation (SwitchAllocation, SA) and crossbar transmission (Switch Transfer, ST) in the internal assembly line of router 100. ), link transfer (Link Transfer, LT) and other stages. Wherein, in the crossbar assignment (SA) stage, the internal input port of the router is mapped to the output port, so as to prepare for the data transmission in the next stage. In the traditional implementation mechanism of network-on-chip, the packet size is consistent with the channel width, while in the implementation mechanism of network-on-chip with fine-grained management, the size of a certain number of data packets and some control information are much lower than the channel width. The number of sub-channels is allocated to the corresponding input buffer, crossbar switch, output buffer, virtual channel, multi-choice one selector and the link between the router and the router 100. The multi-choice one selector includes the two-choice One selector or four select one selector and other types of multi-select one selector.

As shown in FIG. 6 , the implementation mechanism of the fine-grained on-chip network channel, the traditional high-width channel is divided into fine-grained sub-channels 13, and the sub-channels and the output ports are mapped in a fully associative manner. It is assumed that it is an on-chip network router with a Mesh structure, and the input ports 11 and 12 are one of the five input ports. The sub-channel greedy algorithm mapping principle shown in Figure 6, in the input port, the 128bit wide data channel is divided into 4 sub-channels, and each sub-channel VC Creditchannel1 is 32bit wide, including 1 alternative selector 14 and 2 The virtual channels VC0 and VC1 are in the same position, and each input port has 4 alternative selectors and 8 virtual channels. During the transmission of data packets, in each of the input ports, such as input port 0, each of the sub-channels may transmit different data packets, and there is also the possibility that several different virtual channels transmit the same large data packet , that is, when a data packet is larger than the sub-channel width, it can occupy multiple adjacent sub-channels that meet its own required width. Therefore, for each input port, not all the data packets waiting to be sent to the output ports 0 to 8 in all input ports have a size of 128 bits, and each output port can only accept 128 bits of data transmission at a time. . So in the Crossbar Assignment (SA) phase, there is a Crossbar Assignor to perform the processing, the data packet is matched through the Crossbar 51, 5 input ports and 5 said output ports. However, when a traditional port is divided into fine-grained sub-channels, the mapping between the input port and the output port will become much more complicated, and algorithms such as the traditional round-robin (Round-Robin) algorithm do not necessarily It can ensure that the content selected each time is reasonable or tends to be optimal. A greedy algorithm mapping is proposed to maximize the utilization rate of the data channel, that is, the greedy allocation method of the router channel resources of the on-chip network realizes the mapping method of the greedy algorithm idea. The overall optimized input port to output port mapping is obtained by local optimization of the reference port to the non-reference port one by one.

Furthermore, in order to make the description of a greedy allocation method of network-on-chip router channel resources in the present invention clearer, based on the realization of the greedy allocation device 40 and the router 100, the greedy allocation method of network-on-chip router channel resources in the cross The switch allocation stage is performed before the internal input port and output port of the router are mapped, as shown in the flow chart in Figure 4, including:

Step S401, a preprocessing step, when a data packet enters the sub-channel and virtual channel of the input port, classify the data packet information to obtain a pre-processing information table;

Step S402, performing a step of selecting a maximum number of data packets to match the sub-channel and the output port according to the preprocessing information table and the size of the output port corresponding to the data packet;

These two steps are respectively carried out by the preprocessing module 41 and the execution module 42, the preprocessing information table is used as the basis for subsequent data packet and sub-channel management, and the execution module 42 obtains the size of the data packet, the sub-channel where it is located, and the destination to and from according to the preprocessing information table. output port.

Since each said output port can only accept data transmission of 128bit at most each time, for having 5 input ports, each said input port is divided into 4 sub-channels, so the number of each transmission of any one of said output ports The total size of the data packet cannot exceed 128bit, and because the data packet size is different, the number of each time can only be collected according to the size information of all data packets that can be transmitted to the same output port, and the following preprocessing information is obtained table, and transmit it to the output port until the sub-channel is full or the subsequent data packets cannot be combined and transmitted, so as to obtain the effect of local optimization.

In the preprocessing step, the preprocessing module 10 has obtained the data packet information, and in all sub-channels, the information of all data packets expected to be sent to the same output port is sent to the corresponding information table:

Preprocessing information table

As shown in the preprocessing information table, the attribute sub_channel in the first column represents which sub-port of the corresponding input port; the attribute size in the second column represents the size of the data packet; the third to fifth columns S0, S1, S2 represent if the size When it is greater than 1, which sub-channel is the other part of the data packet in, because the data packet is a whole and cannot be disassembled during transmission.

In the execution step, the function of the execution module 42 is to select as many data packets as possible with the output port as the center and the port size as the upper limit according to the result of the preprocessing process. However, in order to ensure fairness, the algorithm needs to follow certain rules, namely: 1. Polling to select the reference port; 2. Data packets in the reference port are transmitted preferentially.

Further, as shown in FIG. 5, in a preferred embodiment of the method for greedy allocation of network-on-chip router channel resources, the steps further include:

Step S501, when the data packet is transmitted to the input port, perform route calculation;

This step is realized by the route collection sub-module 411, which cooperates with the route calculation module of the router;

Step S502, creating an independent preprocessing information table according to the expected output port classification of the data packet information calculated according to the route; the information processing sub-module 412 classifies and creates different preprocessing information tables according to the output port, Easy to execute.

Step S503, updating the expected output port of the data packet of each sub-channel to the corresponding preprocessing information table;

The preprocessing information table includes subport information of the output port sent to, size information of the data packet, and/or information of the subchannel occupied by the data packet.

The information update sub-module 413 updates the expected output port of the data packet of each sub-channel to the corresponding pre-processing information table according to the route calculation result, and cooperates with other parts of the existing router.

Step S504 , polling and selecting one of the input ports as a reference port by using a round-robin algorithm; this step is executed by the reference selection sub-module 421 .

Preferably, in step S504:

The polling (Round-Robin) algorithm includes sequentially selecting different input ports in a polling manner, each selection is performed i=(i+1)mod n, and the i-th port is selected, and n is the total number of ports ; Select the reference port by round-robin algorithm. The reference selection sub-module 421 is used to poll and select one of the input ports as the reference port with a polling algorithm; the reference selection sub-module 421 selects different input ports in turn, and the local priority sub-module 422 selects all of the reference ports The above data packets are preferentially transmitted to the same output port; the so-called reference port is to use the data packet size of this input port as the initial size, select the data packets of other input ports through a greedy algorithm, and if the data packet size of the reference port and the link width Consistent, if the link width is 128bit, the data packet is 128bit, that is, the data packet has filled all the sub-channels (links), at this time, the data packets of other ports will not be selected, and finally the local optimal strategy will be obtained. The reason for polling to select the reference port is to prevent unfair port transmission, because if there is no polling, the first input port selected as the reference port is extremely likely to be selected as the reference port every time.

Step S505, the data packets of the reference port are preferentially transmitted to the same output port; this step is performed by the local priority sub-module 422;

Step S506, if all of the sub-channels of the reference port have the data packets expected to be sent to the same output port, then no longer select the data packets of the subsequent sub-channels of the input port;

In this step, the first selection sub-module 423 detects and executes the currently transmitted data packet;

Step S507, if the data packets in the subchannel of the reference port do not fill up the transmission link, sequentially select the data packets of the subsequent input ports. This step is realized by the second selection sub-module 424 .

For the first selection sub-module 423 to select data packets from the input port, it is selected from the devices before the crossbar allocation stage such as virtual channels and virtual channel buffers involved in all sub-channels. For a certain transmission, the selected The reference port (only one at a time) has the priority to transmit. The so-called priority transmission right means that when there are multiple data packets expected to be sent to the same output port in the virtual channel of the input port or in the buffer in the virtual channel, the data packets of each sub-channel in the reference port are preferentially combined, However, multiple data packets transmitted at the same time are regarded as a whole, so one of the data packets is very large and can occupy multiple sub-channels, and the data of one of the sub-channels is data fragmentation. For this, it is necessary to calculate the The size of the data fragments waiting to be transmitted in each sub-channel and the output port, if not filling all the sub-channels of the current input, the first selection sub-module 423 extracts a suitable size from the virtual channel and the virtual channel buffer. Data packet, until filling up sub-passage, if still can't fill up, then the second selection submodule 424 selects data packet from other sub-passages, promptly selects similar data packet from other input ports, sends to same described output port to achieve optimal transmission efficiency. The first selection sub-module 423 has the advantage of selecting the data packets of the same port sub-channel as far as possible to reduce the input port mapped by the output port once, and the reference port selection sub-module 421 has selected the reference port, so that other ports except the reference port can be compared with other ports except the reference port as much as possible. Mapping of other output ports other than the output port corresponding to the reference port improves port utilization and reduces complexity. If the data packets in the sub-channels of the reference port cannot fill the transmission link, select the data packets in the sub-channels of other input ports for combined transmission.

In a specific embodiment, based on the greedy allocation device 40 and the router 100, the greedy allocation method of the network-on-chip router channel resource is implemented, and the data packet realizes a complete process in this way, and the process includes:

Step 701, data packet input;

Step 702, virtual channel allocation;

Step 703, route calculation;

Step 704, a preprocessing step;

Step 705, execute the step;

Step 706, crossbar assignment (SA);

Step 707, crossbar transmission (ST);

Step 708, link transfer (LT) phase.

After being selected by the greedy algorithm, the ports can achieve a locally optimal transmission combination (that is, select as many data packets as possible so that they can fill the transmission link), and then pass through the crossbar allocation (SA), and the crossbar transmission ( ST) and link transmission (LT) stages, according to the processing result of the greedy algorithm mapping, the data packet is transmitted in the crossbar distribution stage, and the data packet is transmitted to the next-hop router.

Since the present invention adds the GA (Greedy Algorithm) stage to the traditional crossbar allocation (SA) stage on the basis of the steps in Fig. 4 and Fig. 5, the main purpose is to carry out mapping based on the greedy algorithm idea, and there is a greedy allocation device 40 accomplish. In the GA stage, the information of all input ports is collected, and the sub-channel corresponding to the input port is selected for each output port according to the local optimal principle of the greedy algorithm. In the on-chip routing transmission process where the greedy algorithm is applied, it is preferable to execute the steps in the same reference port, distinguish the data fragments of different sub-channels, and the data fragments of a single sub-channel, and the data fragments sent to the same input port are called In the same direction, as shown in the flowchart in Figure 8, the steps include:

Step S801, the Round-Robin algorithm selects the reference port;

Step S802, there are fragments in the same direction behind all sub-channels and all virtual channels of the reference port; if possible, perform step S803, if not, perform step S804;

Step S803, calculate whether the subsequent data fragmentation of the reference port is desirable; if yes, execute step S805; if not, execute step S804;

Step S804, calculate whether the data fragmentation of the sub-channel of the subsequent input port is desirable; if yes, execute step S805, if not, return;

Step S801, taking out data fragments. Go back to step S802;

As shown in FIG. 9 for a specific embodiment, each Router has five input ports, input port one 401, input port two 402, input port three 403, input port four 404, input port five 405, and five output ports ( omitted in the figure). Each input port is assumed to be divided into 4 sub-channels, and the buffer depth of each sub-channel is 2. The 4-to-1 chip selector 406 of each sub-channel is connected to four output ports. Shown in Fig. 9 is a certain moment, the transmission state of a certain router, and data packet 407 all expects to send to the same output port.

Firstly, after each data packet arrives at the input port, after routing calculation, it uniformly sends its expected output port information to the greedy algorithm preprocessing device. The preprocessing module 41 will classify and organize the collected port information. Among them, the preprocessing information table of the four sub-channels (the depth is two) of the input port 1 (taking port 1 as an example):

Preprocessing information table (input port 1)

After the preprocessing module 41 collects the information of all ports, the execution module 42 selects a locally optimal port mapping scheme for each output port.

Assuming that the reference port this time is input port 1 401, according to the principle of greedy algorithm execution, the selected data packets are input port 1 401, the right side is 1 data packet with depth 1 and the left side is 2 data packets with depth 2 The width of the data packet after combination is equal to the maximum width of the port and the link, so the data packets of other ports are not selected, that is, all the data packets of the input port one 401 can meet the optimal transmission, and there is no need to select other ports;

Assuming that the reference port this time is the input port 2 402, according to the execution principle of the greedy algorithm, it will sequentially select the data packets of the input port 3 403;

Assuming that the reference port this time is input port three 403, it will select a data packet from input port four 404 and then select a data packet from input port five 405;

Assuming that the reference port this time is input port 4 404 , it will select input port 5 405 , because the four sub-channels of input port 5 405 are filled with data packets, so there is no need to select data packets from other input ports.

In summary, the present invention adds a preprocessing module and an execution module inside the router, and uses the greedy algorithm idea to perform an optimal mapping between the input port and the output port inside the router, which is suitable for fine-grained channel networks. The traditional on-chip wide channel is divided into low-width sub-transmission channels. In the fine-grained on-chip network router, after the data packets of each sub-channel are routed and calculated, the information of the sub-channel is updated to the preprocessing information table, and the execution module Through the processing of the preprocessing table information, the greedy algorithm is used to match the channel between the input port and the output port, so as to achieve the mapping that tends to be optimal and improve the utilization rate of the channel.

Certainly, the present invention also can have other multiple embodiments, without departing from the spirit and essence of the present invention, those skilled in the art can make various corresponding changes and deformations according to the present invention, but these corresponding Changes and deformations should belong to the scope of protection of the appended claims of the present invention.

Claims (10)

1. the greedy distribution method of a network-on-chip router channel resource, it is characterised in that described greedy distribution method exists The cross bar switch allocated phase of network-on-chip router is that the input port of the inside of router carries out mapping it with output port Before carry out, including：

Packet information, when in the subchannel and Virtual Channel of the described input port of packet entrance, is carried out by pre-treatment step Classification processes and obtains pre-processing information table；

Step, according to the size of described pretreatment information table and the corresponding described output port of described packet, selects Multiple described data packet matched described subchannels and described output port to greatest extent.

2. the greedy distribution method of network-on-chip router channel resource according to claim 1, it is characterised in that described pre- Process step also to include：

When described packet reaches described input port, collect ＆ route calculates result；

Described packet information according to router-level topology is created independent described pre-by the expected described output port mailing to classification Process information table；

Desired for the described packet of each described subchannel described output port is updated to corresponding described pretreatment information Table；

The subport information of described output port that described pretreatment information table includes mailing to, the size information of packet and/or The described sub-channel information that described packet takies.

3. the greedy distribution method of network-on-chip router channel resource according to claim 2, it is characterised in that described hold Row step also includes：

Select input port described in as benchmark port using polling algorithm poll；

The including of described polling algorithm poll select different described input ports successively, select every time to perform i=(i+1) mod N, selects i-th port, and n is port sum；The described packet priority of described benchmark port is transferred to same described output Mouthful.

4. the greedy distribution method of network-on-chip router channel resource according to claim 3, it is characterised in that described base The step that the described packet priority of quasi-port is transferred to same described output port also includes：

The expectation if the described subchannel of described benchmark port has described packet mails to same described output port, then no longer Select the described packet of the subchannel of follow-up described input port；

If the described packet in the described subchannel of described benchmark port does not fill up transmission link, select follow-up described successively The described packet of input port.

5. the greedy distribution method of network-on-chip router channel resource according to claim 1, it is characterised in that also wrap Include：

Virtual Channel distribution is performed on said sheets before the greedy distribution method of network router channel resource；

The result of the greedy distribution method according to described network-on-chip router channel resource is distributed at described cross bar switch The described packet of stage transmission.

6. the greedy distributor of a network-on-chip router channel resource, it is characterised in that described greedy distributor sets Being placed in router, described greedy distributor includes：

Pretreatment module, for when in the subchannel and Virtual Channel of the described input port of packet entrance, by packet information Carry out classification process to obtain pre-processing information table；

Perform module, for the size according to described pretreatment information table and the corresponding described output port of described packet, Select multiple described data packet matched described subchannels and described output port to greatest extent.

7. the greedy distributor of network-on-chip router channel resource according to claim 6, it is characterised in that described pre- Processing module also includes：

Route collects submodule, and for when described packet reaches input port, collect ＆ route calculates result；At information Reason submodule, creates independent for the described packet information according to router-level topology by the expected described output port mailing to classification Described pretreatment information table；

Information updating submodule, right for being updated to the desired described output port of described packet of each described subchannel The described pretreatment information table answered；

The subport information of described output port that described pretreatment information table includes mailing to, the size information of packet and/or The described sub-channel information that described packet takies.

8. the greedy distributor of network-on-chip router channel resource according to claim 6, it is characterised in that described hold Row module also includes：

Selection of reference frame submodule, for selecting input port described in as benchmark port using polling algorithm poll；

The including of described polling algorithm poll select different described input ports successively, select every time to perform i=(i+1) mod N, selects i-th port, and n is port sum；

Local Priority submodule, the described packet priority for described benchmark port is transferred to same described output port.

9. the greedy distributor of network-on-chip router channel resource according to claim 8, it is characterised in that described hold Row module also includes：

First selection submodule, if the described subchannel for described benchmark port has the expectation of described packet to mail to same Described output port, the then described packet of the not subchannel of the follow-up described input port of reselection；

Second selection submodule, if not filling up chain for the described packet in the described subchannel of described benchmark port Road, selects the described packet of follow-up described input port successively.

10. the greedy distributor including network-on-chip router channel resource as described in any one of claim 6～9 Router.