CN111666139A - Scheduling method and device for MIMO multi-service-class data queue - Google Patents

Abstract

The invention discloses a multi-input multi-output multi-service level data queue scheduling method and device. The method of the invention includes adopting a random distribution mode or a differentiated service quality mode, and all input sources with data requests are sent to a round-robin arbiter to request The output channel is used, and the round-robin arbiter arbitrates the output channel based on the arbitration token round-robin rule. The output channel in the idle state in the random distribution mode will receive the input data of the input source in turn; distinguish all input sources and outputs in the quality of service mode. The channels are divided into different priorities, so that a certain group of output channels will only receive data from the input source of the corresponding priority. The invention can not only realize the random distribution of the data streams of multiple input data sources on the multiple output channels, but also realize the task distribution of distinguishing the service quality on the multiple output channels according to the different priorities of the input data, and has a relatively high performance. Low hardware implementation cost, especially suitable for ASIC chip logic implementation.

Description

A scheduling method and device for multiple input multiple output multiple service level data queues

technical field

The invention relates to an in-chip data transmission technology in the field of high-performance computing, in particular to a method and device for scheduling multiple-input multiple-output multiple service-level data queues, which are used for scheduling data streams from multiple input data sources according to multiple output queues. The resource occupancy situation is scientifically scheduled to achieve fair and efficient task distribution that supports multiple service levels.

Background technique

With the continuous improvement of the computing speed of high-performance computer systems (HPC, High Performance Computer) from petascale (P-level, Petascale) to tens of petascale (E-level, Exascale), microprocessor chips and interconnects The amount of data that network chips need to process increases exponentially. Usually, each ASIC (Application Specific Integrated Circuit) chip needs to use multiple processing components to process multiple input data sources, which involves the scheduling of multiple data queues.

There are various classifications of data queue scheduling types and scheduling methods. According to the number of output queues, there are multiple input single output scheduling, multiple input multiple output scheduling; according to the quality of service, there are RR (Round Robin, round-robin scheduling), SP (Strict Priority, strict priority), DRR (Deficit Round Robin, balance round-robin queue), WRR (Weighted Round Robin, weighted round-robin scheduling algorithm), WDRR (Weighted Deficit Round Robin, weighted round-robin scheduling) and so on. For the multiple-input multiple-output scheduling problem in an ASIC chip, the existing scheduling methods have certain limitations or deficiencies. Some methods can only complete the scheduling of single output; some methods cannot guarantee that all input data can get reasonable resources, and even starve to death; some methods cannot make high-priority input queues get priority scheduling; The algorithm is more complex and not suitable for ASIC chip logic implementation.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention: in view of the above-mentioned problems in the prior art, a method and device for scheduling data queues with multiple input, multiple output and multiple service levels are provided. The random distribution on the output channel can also realize the task distribution of differentiated service quality on multiple output channels according to the different priorities of the input data, and at the same time has a low hardware implementation cost, especially suitable for ASIC chip logic implementation.

In order to solve the above-mentioned technical problems, the technical scheme adopted in the present invention is:

A method for scheduling multiple-input multiple-output multiple service-level data queues, comprising the step of selecting a random distribution mode or a differentiated service quality mode for scheduling according to a control parameter mode_sel , wherein the random distribution mode and the differentiated service quality mode both combine all existing data The requested input source requests to use an output channel from a round-robin arbiter, and the round-robin arbiter arbitrates the output channel based on the arbitration token round-robin rule. The output channel in the idle state in the random distribution mode will receive the input of the input source in turn data; in the differentiated service quality mode, all input sources and output channels are divided into different priorities, and a certain group of output channels will only receive data from input sources with corresponding priorities.

Optionally, denote the number of input data sources as n , the n input sources are { I ₀ , I ₁ , I ₂ , ..., I _n-1 } in sequence, the number of output channels is m , and the m output channels are in sequence { O ₀ , O ₁ , O ₂ , …, O _m-1 }; denote the request vector of n input sources as { r ₀ , r ₁ , r ₂ , …, r _{n - 1 }} , where ri is 0 or 1, where i = 0, 1, 2, …, n -1, when ri is 0, it means that there is no data request for the _ith input source _, and when ri is 1, it means that there is a data request for the ith input source; mark m The busy and idle state vectors of the output channels are { v ₀ , v ₁ , v ₂ , …, v _m-1 }, v _i is 0 or 1, where i = 0, 1, 2, …, m -1, v When _i is 0, it means that the ith output channel is in a busy state and cannot currently receive new data processing requests. When v _i is 1, it means that the ith output channel is in an idle state, and new data processing requests can be received at this time; In distribution mode:

The arbitration token rotation rule of the rotation arbiter is as follows: after completing an arbitration response, the arbitration token will be passed to the next input source of the input source that currently obtains the token, that is, assuming that I _i has obtained the arbitration response, the arbitration order The card will be passed to I _{(i+1) mod n} ; the execution rules of the arbitration response are as follows: if all v _i are 0, it means that all output channels are not idle, then all input sources cannot get the arbitration response; When there is at least one v _i is 1, it means that at least one output channel can receive data processing requests, assuming that the arbitration token is at the position of I _i , if ri is 1, it means that there is a data request for I _{i ,} then I _i will Arbitration response is obtained; if ri is 0, it means that there is no data request for I _i , then look back at I _{i +1} , I _i+2 , I _i+3 , …, I _n-1, I ₀ , I ₁ , I _i-1 , the first input source that has a data request after I _i will get an arbitration response; the selection rule of the output channel is as follows: use an output channel selection token to realize the rotation of the output channel, in the initial state, The channel selection token is in the hands of O ₀ , and the first input source that gets the arbitration response will output data to O ₀ ; then the channel selection token will be rotated to O ₁ , and so on; when the channel selection token is rotated to O _i In hand, if v _i is 1, it means O _i is in an idle state, then the input source that has received the arbitration response will select O _i as the output channel; if v _i is 0, it means O _i is not in an idle state, then it is currently arbitrated The input source of the answer will select the first idle output channel after O _i (if O _i+1 is idle, then select O _i+1 ), and at the same time, the channel selection token will rotate to the next output channel after the currently selected output channel. an output channel.

Optionally, in the differentiated quality of service mode, all input sources and output channels are divided into different priorities. Specifically, the priority of each input source is configured through the configuration parameter priority_vector0 , and the configuration parameter priority_vector1 is used to configure each output channel. priority.

Optionally, denote the number of input data sources as n , the n input sources are { I ₀ , I ₁ , I ₂ , ..., I _n-1 } in sequence, the number of output channels is m , and the m output channels are in sequence { O ₀ , O ₁ , O ₂ , …, O _m-1 }; denote the request vector of n input sources as { r ₀ , r ₁ , r ₂ , …, r _{n - 1 }} , where ri is 0 or 1, where i = 0, 1, 2, …, n -1, when ri is 0, it means that there is no data request for the _ith input source _, and when ri is 1, it means that there is a data request for the ith input source; mark m The busy and idle state vectors of the output channels are { v ₀ , v ₁ , v ₂ , …, v _m-1 }, v _i is 0 or 1, where i = 0, 1, 2, …, m -1, v When _i is 0, it means that the i -th output channel is in a busy state and cannot currently receive new data processing requests. When v _i is 1, it means that the i -th output channel is in an idle state, and new data processing requests can be received at this time; In the differentiated quality of service mode described above:

The arbitration token rotation rule of the rotation arbiter is as follows: after completing an arbitration response, the arbitration token will be passed to the next input source of the input source that currently obtains the token, that is, assuming that I _i has obtained the arbitration response, the arbitration order The card will be passed to I _{(i+1) mod n} ; the execution rules of the arbitration response are as follows: if all v _i are 0, it means that all output channels are not idle, then all input sources cannot get the arbitration response; When there is at least one v _i is 1, it means that there is at least one output channel that can receive data processing requests, assuming that the arbitration token is at the position I _i at this time, if ri is 1 and all _outputs corresponding to q _j that are the same as p _i There is an idle channel in channel O _j , that is, v _j =1, which means that there is a data request in I _i and there is an idle channel in the output channel that supports the current priority, then I _i will get an arbitration response; if r _i is 0, Indicates that there is no data request for I _i , then look back at I _i+1 , I _i+2 , I _i+3 , …, I _n-1, I ₀ , I ₁ , I _i-1 in turn, until an I is found _k meets the following conditions: r _k is 1 and there is an idle channel in all output channels O _k corresponding to q _k that is the same as p _k , that is, v _k =1, then I _k will be answered; the selection rules of output channels are as follows: Each group of output channels with the same priority uses their own output channel selection tokens to implement the rotation of the output channels in this group; in the initial state, the channel selection tokens of each group of output channels with the same priority are in the first channel of the group. On one channel; when a data source in the group gets the arbitration response, if the output channel where the channel selection token of the priority group is located has v _i of 1, it means that the output channel O _i is in an idle state, then the current The input source of the arbitration response will select O _i as the output channel; if v _i is 0, it means that O _i is not in an idle state, then the input source that currently gets the arbitration response will select the first idle channel in the group after O _i . output channel, and the channel selection token rotates to the next output channel in this group after the currently selected output channel.

Optionally, the selecting to use the random distribution mode or the differentiated service quality mode for scheduling according to the control parameter mode_sel specifically refers to: judging the control parameter mode_sel , and using the random distribution mode for scheduling when the control parameter mode_sel is a first set value; When the parameter mode_sel is the second set value, the differentiated service quality mode scheduling is adopted.

In addition, the present invention also provides a scheduling device for multiple-input multiple-output multiple-level-of-service data queues, the scheduling device is programmed or configured to execute the steps of the scheduling method for the multiple-input multiple-output multiple-level-of-service data queues. In addition, the present invention also provides a microprocessor including a multiple-input multiple-output multiple-level-of-service data queue and scheduling means programmed or configured to execute the multiple-input multiple-output multiple-level-of-service data The steps of the queue's scheduling method. In addition, the present invention also provides a computer device comprising at least a microprocessor and a memory, the microprocessor including a multiple input multiple output multiple service level data queue and a scheduling device programmed or configured to execute the multiple Steps of a scheduling method for an input multiple output multiple class of service data queue. In addition, the present invention also provides a computer-readable storage medium on which a computer program programmed or configured to execute the scheduling method of the multiple-input multiple-output multiple-level-of-service data queue is stored.

Compared with the prior art, the present invention has the following advantages:

1. Wide range of application. By adjusting the configuration parameters, this method can not only realize a completely fair and balanced random distribution mode, but also realize a mode of differentiating the quality of service with multiple priorities;

2. Simple hardware implementation and low cost. All configuration modes (random distribution mode, differentiated service quality mode) are implemented with only one round-robin arbiter. By mapping the resource status information of the output channel to the corresponding input source according to different configurations, various modes under different modes are realized. Arbitration control logic.

Description of drawings

FIG. 1 is a schematic diagram of a basic flow of a method according to an embodiment of the present invention.

FIG. 2 is a schematic diagram of an example of a random distribution mode in an embodiment of the present invention.

FIG. 3 is a schematic diagram of an example of differentiating quality of service modes according to an embodiment of the present invention.

Detailed ways

As shown in FIG. 1 , the scheduling method of the multiple-input multiple-output multiple service level data queue in this embodiment includes the step of selecting random distribution mode or differentiated service quality mode for scheduling according to the control parameter mode_sel . All input sources with data requests request the use of output channels to a round-robin arbiter, and the round-robin arbiter arbitrates the output channels based on the arbitration token round-robin rule. The output channels in the idle state in random distribution mode will receive input sources in turn All input sources and output channels are divided into different priorities in differentiated service quality mode, and a group of output channels will only receive data from input sources with corresponding priorities.

In this embodiment, the resource status information of all output channels is integrated into the same round-robin arbiter, so that all input data sources only use one round-robin arbiter to implement task scheduling to all output channels. When the round-robin arbiter arbitrates multiple requests, it needs to be guided by the resource status information of the output channel to decide which request the arbitration response should be returned to, and which output the answered input data should be distributed to. aisle. For the random distribution mode, the resource status information of all output channels will guide all input sources, and the output channels in the idle state will receive input data in turn; for the mode of distinguishing service quality, different output channels have different priorities The resource status information of the output channel of a certain priority is only valid for the input source of the corresponding priority, and this output channel will only receive the data of the input source of the corresponding priority. For convenience of description, in this embodiment, the number of input data sources is n , the n input sources are { I ₀ , I ₁ , I ₂ , ..., I _n-1 } in sequence, and the number of output channels is m , m The output channels are { O ₀ , O ₁ , O ₂ , …, O _m-1 }; the request vector of n input sources is { r ₀ , r ₁ , r ₂ , …, r _{n - 1} }, r _i is 0 or 1, where i = 0, 1, 2, …, n -1, when ri is 0, it means that there is no data request for the _ith input source _, and when ri is 1, it means that there is data in the ith input source Request; remember the busy and idle state vectors of m output channels as { v ₀ , v ₁ , v ₂ , …, v _m-1 }, v _i is 0 or 1, where i = 0, 1, 2, …, m -1, when v _i is 0, it means that the ith output channel is in a busy state and cannot receive new data processing requests. When v _i is 1, it means that the ith output channel is in an idle state, and new data processing can be received at this time. ask.

In this embodiment, selecting the random distribution mode or the differentiated service quality mode for scheduling according to the control parameter mode_sel specifically refers to: judging the control parameter mode_sel , and using the random distribution mode for scheduling when the control parameter mode_sel is the first set value; When mode_sel is the second set value, the differentiated quality of service mode scheduling is adopted. When the control parameter mode_sel is 0, it indicates that the current working mode is the random channel mode (Random mode), that is, the output channel in the idle state will receive input data in turn; when the control parameter mode_sel is 1, it indicates that the current working mode is the differentiated service quality mode. (QoS mode), that is, all output channels are divided into multiple groups of channels with different priorities, and a certain group of output channels will only receive data from the input source of the corresponding priority.

In this embodiment, the random distribution mode is simply referred to as the random mode. As shown in FIG. 2 , in the random mode, the control parameter mode_sel needs to be set to 0, so that all the input data sources can use all the output channels fairly. In this embodiment, in the random distribution mode:

The arbitration token rotation rules of the round-robin arbiter are as follows: after completing an arbitration response, the arbitration token will be passed to the next input source of the input source that currently obtains the token, that is, assuming that I _i has obtained the arbitration response, the arbitration token will be It will be passed to I _{(i+1) mod n} ; the execution rules of the arbitration response are as follows: if all v _i are 0, it means that all output channels are not idle, then all input sources cannot get the arbitration response; when there is at least one When v _i is 1, it means that at least one output channel can receive data processing requests, assuming that the arbitration token is at the position of I _i , if ri is 1, it means that there is a data request for I _{i ,} then I _i will get an arbitration response; If ri is 0, it means that there is no data request for I _i , then look backwards in sequence I _{i +1} , I _i+2 , I _i+3 ,..., I _n-1, I ₀ , I ₁ , I _{i- 1.} The first input source with a data request after I _i will get an arbitration response; the selection rule of the output channel is as follows: use an output channel selection token to realize the rotation of the output channel. In the initial state, the channel selection token is at 0 . ₀ , the first input source that gets the arbitration response will output data to O ₀ ; then the channel selection token will be rotated to O ₁ , and so on; when the channel selection token is rotated to O _i , if v _i If it is 1, it means that O _i is in an idle state, then the input source that has received the arbitration response will select O _i as the output channel; if v _i is 0, it means that O _i is not in an idle state, then the input source that has received the arbitration response will select O i as the output channel. The first idle output channel after O _i (if O _i+1 is idle, select O _i+1 ), and at the same time, the channel selection token turns to the next output channel after the currently selected output channel.

The following takes the MIMO data queue (Arbiter) with 8 inputs and 4 outputs (ie, n =8, m =4) as an example to describe the scheduling method of the MIMO data queue in this embodiment.

As shown in Figure 2, in the initial state, ri = 0 (where _i = 0, 1, 2, ..., 7), v _i =1 (where i = 0, 1, 2, 3), the arbiter token On I ₀ , the channel selection token is on O ₀ ; configure the mode_sel control parameter to 0 to enter Random mode;

1. At time T0 (the case where the arbiter token is on the input source without data request), r ₁ , r ₂ , r ₄ become 1, since the token is on I ₀ , but r ₀ is 0, so I ₁ Get the arbitration reply, r ₁ will become 0 after getting the reply; since the channel selection token is on O ₀ , and v ₀ is 1, the I ₁ that gets the reply will select O ₀ output, and v ₀ will become 0; At the same time, the arbiter token is rotated to I ₂ , and the channel selection token is rotated to O ₁ ;

2. At time T1 (the arbiter token is located on the input source with data request), r ₂ , r ₄ are still waiting for the response of the round-robin arbiter, so r ₂ , r ₄ are still 1, in addition, r ₁ is due to the occurrence of It becomes 1 again due to a new data request, and r ₆ also becomes 1 because there is a data request; since the arbiter token is on I ₂ , and r ₂ is 1, I ₂ gets the arbitration response, and r ₂ gets the arbitration response. will become 0 after answering; since the channel select token is on O ₁ and v ₁ is 1, the I ₂ that gets the answer will select O ₁ output, and v ₁ will become 0; at the same time, the arbiter token rotates to On I ₃ , the channel selection token is rotated to O ₂ ;

3. At time T2 (when the channel selection token is located on a non-idle output channel), some output channels may become non-idle after a period of time, assuming that only v ₀ and v ₂ are 1 at this time. In addition, r ₀ , r ₃ , r ₄ , r ₆ are 1, the arbiter token is on I ₇ , and the channel selection token is on O ₃ ; since r ₇ is 0, the arbiter token is on I ₇ , so I ₀ get the arbitration answer, r ₀ will become 0 after getting the answer; since the channel select token is on O ₃ , but v ₃ is 0, the I ₀ getting the answer will select the next free O ₀ output, v ₀ will becomes 0; at the same time, the arbiter token is rotated to I ₁ , and the channel selection token is rotated to O ₁ ;

And so on, the round-robin arbiter continues to schedule jobs.

In this embodiment, the differentiated quality of service mode is referred to as QoS mode for short. As shown in FIG. 3 , in the QoS mode, the control parameter mode_sel needs to be set to 1, so that all input data sources can use all output channels fairly. In this embodiment, all input sources and output channels are divided into different priorities in the distinguishing quality of service mode. Specifically, the priority of each input source is configured by the configuration parameter priority_vector0 , and the priority of each output channel is configured by the configuration parameter priority_vector1 . priority. There are d different priorities in total. The configuration parameter priority_vector0 is used to configure the priority of each input data source, which is { p ₀ , p ₁ , p ₂ , …, p _n-1 } (where p _i = 0, 1, 2, …, d- 1, where i = 0, 1, 2, …, n- 1); the configuration parameter priority_vector1 is used to configure the priority of each output channel, in order { q ₀ , q ₁ , q ₂ , …, q _m-1 } (where q _i = 0, 1, 2, …, d-1 , where i = 0, 1, 2, …, m-1 ). Set the mode_sel control parameter to 1, so that the resource status information of the output channel of a certain priority is only valid for the input source of the corresponding priority, and this output channel will only receive the data of the input source of the corresponding priority. In addition, the priority_vector0 parameter is configured according to the application requirements, and the priority_vector1 parameter is configured at the same time, so that the task with higher priority can obtain more output channels. All input sources still use only one arbiter for data scheduling, but input sources with different priorities will be distinguished according to different priority_vector0/1 parameters.

In differentiated quality of service mode:

The arbitration token rotation rules of the round-robin arbiter are as follows: after completing an arbitration response, the arbitration token will be passed to the next input source of the input source that currently obtains the token, that is, assuming that I _i has obtained the arbitration response, the arbitration token will be It will be passed to I _{(i+1) mod n} ; the execution rules of the arbitration response are as follows: if all v _i are 0, it means that all output channels are not idle, then all input sources cannot get the arbitration response; when there is at least one When v _i is 1, it means that at least one output channel can receive data processing requests, assuming that the arbitration token is at the position of I _i at this time, if ri is 1 and all the output channels O _j corresponding to q _j that are the same as p _i are in the output channel O _j There is an idle channel, that is, v _j =1, which means that I _i has a data request and there is an idle channel in the output channel that supports the current priority, then I _i will get an arbitration response; if ri is 0, it means that I _i is not _. If there is a data request, then look backwards in sequence I _i+1 , I _i+2 , I _i+3 , ..., I _n-1, I ₀ , I ₁ , I _i-1 , until an I _k is found that meets the following conditions : If r _k is 1 and there is an idle channel in all output channels O _k corresponding to the same q _k as p _k , that is, v _k =1, then I _k will be answered; the selection rules of output channels are as follows: each group has the same The output channels of the priority use their respective output channel selection tokens to realize the rotation of the output channels in this group; in the initial state, the channel selection tokens of each group of output channels with the same priority are on the first channel of the group. ; After a certain data source of the group gets the arbitration response, if the output channel where the channel selection token of the priority group is located is 1, it means that the output channel O i _is in an idle state, then the input of the arbitration response is currently obtained _. The source will select O _i as the output channel; if v _i is 0, indicating that O _i is not in an idle state, the input source that has received the arbitration response will select the first idle output channel in the group after O _i , and at the same time The channel selection token rotates to the next output channel in the group after the currently selected output channel.

As shown in Figure 3, in the initial state, ri = 0 (where _i = 0, 1, 2, ..., 7), v _i =1 (where i = 0, 1, 2, 3), the arbiter token On I ₀ , the channel selection token is on O ₀ ; first configure the mode_sel control parameter to 1 to enter QoS mode. Second, configure priority_vector0 as {0, 0, 0, 0, 1, 1, 1, 1}, i.e. priority of I ₀ , I ₁ , I ₂ , I ₃ is 0, I ₄ , I ₅ , I ₆ , The priority of I ₇ is 1 (assuming a total of 2 priorities are supported); then configure priority_vector1 as {0, 0, 0, 1}, that is, O ₀ , O ₁ , O ₂ can receive input data with priority 0 , O ₃ can receive input data with priority 1.

1. At time T0 (the case where the arbiter token is on the input source without data request), r ₁ , r ₂ , r ₄ become 1, since the token is on I ₀ , but r ₀ is 0, so I ₁ get the arbitration reply, r ₁ will become 0 after getting the reply; since the priority of I ₁ is 0, and the channel selection token with priority 0 is on O ₀ , and v ₀ is 1, the I that gets the reply is 1 ₁ will select O ₀ output, v ₀ will become 0; at the same time, the arbiter token is rotated to I ₂ , the channel selection token of priority 0 is rotated to O ₁ , and the channel selection token of priority 1 is still on O ₃ on;

2. At time T1 (the arbiter token is located on the input source with data request), r ₂ , r ₄ are still waiting for the response of the round-robin arbiter, so r ₂ , r ₄ are still 1, in addition, r ₁ is due to the occurrence of It becomes 1 again due to a new data request, and r ₆ also becomes 1 because there is a data request; since the arbiter token is on I ₂ , and r ₂ is 1, I ₂ gets the arbitration response, and r ₂ gets the arbitration response. will become 0 after answer; since I ₂ has priority 0, and the channel selection token with priority 0 is on O ₁ , and v ₁ is 1, the I ₂ that gets the answer will select O ₁ output, v ₁ will become 0; at the same time, the arbiter token is rotated to I ₃ , the channel selection token of priority 0 is rotated to O ₂ , and the channel selection token of priority 1 is still on O ₃ ;

3. At time T2 (the case where the round-robin arbiter responds from priority 0 to priority 1), if r ₁ , r ₄ , and r ₆ are 1, because the arbiter token is on I ₃ , but r ₃ is 0, So I ₄ gets the arbitration answer, r4 will become 0 after getting the answer; since I ₄ has priority 1, and the channel selection token with priority 1 is on O ₃ , and v ₃ is 1, it gets the answer The I ₄ will select the O ₃ output, and v ₃ will become 0; at the same time, the arbiter token rotates to I ₅ , and the priority 0 channel selection token remains on O ₂ , due to the priority 1 output channel There is only O ₃ , so the channel selection token of priority 1 is still on O ₃ ;

4. At time T3 (the case where there is no idle channel for priority 1), if r ₁ and r ₆ are 1, since the arbiter token is on I ₅ , the priority of I ₅ is 1, and the input of priority 1 can be received The requested output channel is only O ₃ and is not in an idle state, so I ₆ with r ₆ of 1 cannot obtain an arbitration response. Furthermore, I ₁ with a priority of 0 obtains an arbitration response, and r ₁ will change after getting the response. is 0; since I ₁ has priority 0, and the channel selection token with priority 0 is on O ₂ , and v ₂ is 1, the I ₁ that gets the answer will select the O ₂ output, and v ₂ will become 0; at the same time, the arbiter token is rotated to I ₂ , the channel selection token of priority 0 is rotated to O ₀ , and the channel selection token of priority 1 is still on O ₃ ;

And so on, the round-robin arbiter continues to schedule jobs.

In addition, this embodiment also provides a scheduling apparatus for MIMO multi-level of service data queues, the scheduling apparatus is programmed or configured to execute the steps of the aforementioned scheduling method for MIMO multi-level of service data queues in this embodiment. In addition, the present embodiment also provides a microprocessor, which includes a multiple-input multiple-output multiple service level data queue and a scheduling device, and the scheduling device is programmed or configured to execute the aforementioned multiple-input multiple-output multiple-input multiple-output multiple Steps of a scheduling method for a class of service data queue. In addition, this embodiment also provides a computer device, including at least a microprocessor and a memory, the microprocessor including a multiple-input multiple-output multiple service level data queue and a scheduling device, the scheduling device being programmed or configured to execute the present embodiment For example, the steps of the scheduling method for the multiple-input multiple-output multiple service level data queues are described above. In addition, the present embodiment also provides a computer-readable storage medium, on which is stored a computer program programmed or configured to execute the aforementioned scheduling method of the MIMO multi-level of service data queue of the present embodiment.

As will be appreciated by those skilled in the art, the embodiments of the present application may be provided as a method, a system, or a computer program product. Accordingly, the present application may take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present application may take the form of a computer program product embodied on one or more computer-usable storage media (including, but not limited to, disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein. The present application refers to flowcharts of methods, apparatus (systems), and computer program products according to embodiments of the present application and/or processor-executed instructions generated for implementing a process or processes and/or block diagrams in a flowchart. A means for the function specified in a block or blocks. These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory result in an article of manufacture comprising instruction means, the instructions An apparatus implements the functions specified in a flow or flows of the flowcharts and/or a block or blocks of the block diagrams. These computer program instructions can also be loaded on a computer or other programmable data processing device to cause a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process such that The instructions provide steps for implementing the functions specified in one or more of the flowcharts and/or one or more blocks of the block diagrams.

The above are only the preferred embodiments of the present invention, and the protection scope of the present invention is not limited to the above-mentioned embodiments, and all technical solutions under the idea of the present invention belong to the protection scope of the present invention. It should be pointed out that for those skilled in the art, some improvements and modifications without departing from the principle of the present invention should also be regarded as the protection scope of the present invention.

Claims (9)

1. A method for scheduling MIMO multi-class data queues includes the steps of controlling parametersmode_selSelecting a random distribution mode or a differentiated service quality mode for scheduling, wherein the random distribution mode and the differentiated service quality mode both request all input sources with data requests to a round-robin arbiter for using output channels, the round-robin arbiter arbitrates the output channels based on an arbitration token round-robin rule, and the output channels in an idle state in the random distribution mode receive input data of the input sources in turn; all input sources and output channels in the differentiated service quality mode are divided into different priorities, and a certain group of output channels only receive data of the input sources with the corresponding priorities.

2. The MIMO multi-service class data queue scheduling method of claim 1,

number of input data sources is recorded asn，nThe input sources being sequentiallyI ₀ ,I ₁ ,I ₂ , …,I _n-1 The number of output channels ism，mThe output channels are sequentiallyO ₀ ,O ₁ ,O ₂ , …,O _m-1 }; note the booknA request vector of each input source beingr ₀ ,r ₁ ,r ₂ ,…,r _{n 1-}}，r _i Is 0 or 1, whereini=0, 1, 2, …,n-1，r _i When it is 0, it meansiThere is no data request for one input source,r _i when 1 is shown asiA data request exists for each input source; note the bookmThe busy-idle state vector of each output channel isv ₀ ,v ₁ ,v ₂ ,…,v _m-1 }，v _i Is 0 or 1, whereini=0, 1, 2, …,m-1，v _i When it is 0, it meansiThe output channel is busy, cannot receive new data processing request currently,v _i when 1 is shown asiEach output channel is in an idle state, and a new data processing request can be received at the moment; in the random distribution mode:

the arbitration token round robin rule of the round robin arbiter is as follows: the arbitration token will pass to the next input source of the currently token-derived input source after completing an arbitration response, assumingI _i Get arbitration response, the arbitration token will be passed toI _{(i+1) mod n} (ii) a The execution rule of the arbitration response is as follows: if all ofv _i All the input channels are 0, which means that all the output channels are not idle, and all the input sources cannot obtain arbitration response at this time; when at least one existsv _i A value of 1 indicates that at least one output channel can receive a data processing request, assuming that the arbitration token is presentI _i Position ifr _i Is 1, representsI _i There is a request for data, thenI _i Will get the arbitration response; if it is notr _i Is 0, representsI _i If there is no data request, then look backwards in turnI _i+1 ,I _i+2 ,I _i+3 , …,I _n-1, I ₀ ,I ₁ ,I _i-1 ，I _i The first subsequent input source of the presence data request will be arbitratedCutting and answering; the selection rule of the output channel is as follows: using one output channel selection token to realize the rotation of the output channel, wherein the channel selection token is in the initial stateO ₀ In the hand, the first input source to get arbitration response outputs data toO ₀ (ii) a The channel selection token then rotates toO ₁ In the hand, so on; when the channel selection token turns toO _i In the middle of the hand, ifv _i Is 1, representsO _i In the idle state, the input source currently receiving arbitration response will be selectedO _i As an output channel; if it isv _i Is 0, representsO _i If not, the input source currently receiving arbitration response will be selectedO _i The first idle output channel thereafter (e.g.O _i+1 When idle, then selectO _i+1 ) And meanwhile, the channel selection token turns to the next output channel of the output channels after being selected currently.

3. The method for scheduling mimo-qos data queues according to claim 1, wherein the dividing of all input sources and output channels into different priorities in the qos mode specifically means configuring parameterspriority_vector0Configuring the priority of each input source by configuring the parameterspriority_vector1For configuring the priority of each output channel.

4. The MIMO-SGSB scheduling method as claimed in claim 3, wherein the number of input data sources is recorded asn，nThe input sources being sequentiallyI ₀ ,I ₁ ,I ₂ , …,I _n-1 The number of output channels ism，mThe output channels are sequentiallyO ₀ ,O ₁ ,O ₂ , …,O _m-1 }; note the booknA request vector of each input source beingr ₀ ,r ₁ ,r ₂ , …,r _{n 1-}}，r _i Is 0 or 1, whereini=0, 1, 2, …,n-1，r _i When it is 0, it meansiThere is no data request for one input source,r _i when 1 is shown asiA data request exists for each input source; note the bookmThe busy-idle state vector of each output channel isv ₀ ,v ₁ ,v ₂ , …,v _m-1 }，v _i Is 0 or 1, whereini=0, 1, 2, …,m-1，v _i When it is 0, it meansiThe output channel is busy, cannot receive new data processing request currently,v _i when 1 is shown asiEach output channel is in an idle state, and a new data processing request can be received at the moment; in the differentiated quality of service mode:

the arbitration token round robin rule of the round robin arbiter is as follows: the arbitration token will pass to the next input source of the currently token-derived input source after completing an arbitration response, assumingI _i Get arbitration response, the arbitration token will be passed toI _{(i+1) mod n} (ii) a The execution rule of the arbitration response is as follows: if all ofv _i All the input channels are 0, which means that all the output channels are not idle, and all the input sources cannot obtain arbitration response at this time; when at least one existsv _i A value of 1 indicates that at least one output channel can receive a data processing request, assuming that the arbitration token is presentI _i Position ifr _i Is 1 and all arep _i Same asq _j Corresponding output channelO _j In which there is a free channel, i.e.v _j =1, this meansI _i There is one free channel in the output channel where there is a data request and the current priority is supported, thenI _i Will get the arbitration response; if it is notr _i Is 0, representsI _i If there is no data request, then look backwards in turnI _i+1 ,I _i+2 ,I _i+3 , …,I _n-1, I ₀ ,I ₁ ,I _i-1 Until one is foundI _k The following conditions are met:r _k is 1 and all arep _k Same asq _k Corresponding output channelO _k In which there is a free channel, i.e.v _k =1, thenI _k Will get a response; the selection rule of the output channels is as follows: each group of output channels with the same priority uses respective output channel selection tokens to realize the rotation of the output channels in the group; in an initial state, each group of channel selection tokens with output channels of the same priority is on a first channel of the group of channels; when a certain data source of the group obtains arbitration response, if the channel of the group priority selects the output channel of the tokenv _i Is 1, denotes the output channelO _i In the idle state, the input source currently receiving arbitration response will be selectedO _i As an output channel; if it isv _i Is 0, representsO _i If not, the input source currently receiving arbitration response will be selectedO _i Then the first idle output channel in the group, and the channel selection token turns to the next output channel in the group of the currently selected output channel.

5. The method of claim 1, wherein the scheduling is based on a control parametermode_selThe selecting the random distribution mode or the differentiated service quality mode for scheduling specifically includes: determining control parametersmode_selWhen controlling the parametersmode_selRandom when the first setting value is adoptedDispatching a distribution mode; when controlling the parametermode_selAnd adopting a differentiated service quality mode for scheduling when the second set value is the second set value.

6. A scheduling apparatus for a MIMO multi-class-of-service data queue, wherein the scheduling apparatus is programmed or configured to perform the steps of the method for scheduling a MIMO multi-class-of-service data queue according to any of claims 1 to 5.

7. A microprocessor comprising a MIMO multi-class-of-service data queue and scheduling means, wherein the scheduling means is programmed or configured to perform the steps of the method of scheduling a MIMO multi-class-of-service data queue as claimed in any one of claims 1 to 5.

8. A computer device comprising at least a microprocessor and a memory, characterized in that the microprocessor comprises a mimo multi-class of service data queue and scheduling means, characterized in that the scheduling means is programmed or configured to perform the steps of the method for scheduling mimo multi-class of service data queues according to any one of claims 1 to 5.

9. A computer-readable storage medium having stored thereon a computer program programmed or configured to perform a method of scheduling a mimo-qos data queue according to any of claims 1 to 5.

Images