CN118377743B

CN118377743B - Arbitration method, device, equipment, medium and product for input request

Info

Publication number: CN118377743B
Application number: CN202410823782.2A
Authority: CN
Inventors: 李树青; 冯小康; 孙华锦; 陈静静
Original assignee: Shandong Yunhai Guochuang Cloud Computing Equipment Industry Innovation Center Co Ltd
Current assignee: Shandong Yunhai Guochuang Cloud Computing Equipment Industry Innovation Center Co Ltd
Priority date: 2024-06-25
Filing date: 2024-06-25
Publication date: 2024-08-23
Anticipated expiration: 2044-06-25
Also published as: CN118377743A

Abstract

The invention discloses an arbitration method, a device, equipment, a medium and a product of an input request, which relate to the technical field of hardware and are applied to an arbiter connected with any output channel, wherein the arbiter is connected with at least two input channels and comprises the following steps: detecting each input channel in the current clock period to determine whether valid input requests exist in each input channel; if at least one input channel has an input request meeting the preset effective request condition, marking the input request of the at least one input channel by using the current sequence number generated by the first sequence number generator in the current clock period, and storing the marked input request into a cache; and checking the input request output by the cache by using the current expected sequence number generated by the second sequence number generator, generating an arbitration request for the checked input request, and transmitting the arbitration request to an output channel for processing. The maximum delay of the request can be reduced, the resource overhead can be saved, and the streaming processing of the request can be realized.

Description

Arbitration method, device, equipment, medium and product for input request

Technical Field

The present invention relates to the field of hardware technologies, and in particular, to an arbitration method, apparatus, device, medium, and product for an input request.

Background

A multi-stage interconnect network is generally formed of a plurality of switching nodes that are divided into multiple stages and interconnected together to complete the exchange of data between input ports and output ports, as is typical of a multi-stage interconnect network in fig. 1. An arbiter is an indispensable logic in a multi-stage interconnect network for arbitrating multiple input channels, selecting an appropriate one as an output. Conventional arbiters often employ Round-Robin (Round Robin) algorithms, where an output port starts from the last authorized input port, queries the next valid input port and grants, then starts from that input port the next time, and so on. However, since the polling arbitration is inherently random, the input data that arrives at the node first will not get the first response on a large probability, but will need to wait. Thus, the poll arbitration, although not changing the total latency of all requests, will increase the maximum latency of the requests, which also means that the system needs to prepare more cache resources, compared to the first-come first-served.

The conventional first-request first-service method can effectively solve the above problem, and this method needs to record the arrival time of the lower request when the node receives the request, and then the arbiter sorts the arrival times of all the requests to select the request with the earliest time for priority service. This approach is suitable for processor-based software implementations, but for digital logic circuit-based chip implementations, there are the following problems: the recording time stamp needs larger data bit width, which brings higher resource expense; the minimum value is found out in a sequence in a plurality of data, which generally needs a plurality of clock cycles to realize, so that the request cannot be processed in a streaming mode, and the throughput rate of the internet is greatly reduced; it is a relatively complex matter to implement a minimum look-up in a hardware circuit, since it requires comparing a number of numbers two by two to find the minimum, each value being an input signal for the hardware circuit, which means that a circuit path needs to exist between every two signals, which complicates the circuit.

Accordingly, the above technical problems are to be solved by those skilled in the art.

Disclosure of Invention

In view of the above, the present invention aims to provide an arbitration method, an apparatus, a device, a medium and a product for inputting a request, which can reduce the maximum delay of the request, save the resource overhead, and realize the streaming processing of the request. The specific scheme is as follows:

In a first aspect, the present invention discloses a method for arbitrating input requests, which is applied to an arbiter connected with any one of output channels, wherein the arbiter is connected with at least two input channels, and comprises:

Detecting each input channel in the current clock period to determine whether an input request meeting a preset valid request condition exists in each input channel;

if at least one input channel has an input request meeting the preset effective request condition, marking the input request of at least one input channel by utilizing a current sequence number generated by a first sequence number generator in the current clock period, and storing each marked input request into a cache;

And checking the input request output by the cache by using the current expected sequence number generated by the second sequence number generator to generate an arbitration request for the checked input request, and transmitting the arbitration request to the output channel for processing according to a preset rule.

Optionally, after the input request meeting the preset valid request condition exists in the at least one input channel, the method further includes:

And sending a first sequence number switching instruction to the first sequence number generator, so that when the first sequence number generator detects that an input request meeting a preset valid request condition exists in at least one input channel in the next clock period, generating a next sequence number corresponding to the current sequence number according to a preset sequence number sequence, and marking the input request of the input channel by using the next sequence number.

Optionally, after determining whether the input request meeting the preset valid request condition exists in each input channel, the method further includes:

And if the input request meeting the preset valid request condition does not exist in each input channel, prohibiting sending the first sequence number switching instruction to the first sequence number generator, so that the first sequence number generator generates the current sequence number when detecting that the input request meeting the preset valid request condition exists in at least one input channel in the next clock period, and marking the input request of the input channel by utilizing the current sequence number.

Optionally, when the first sequence number generator acquires the first sequence number switching instruction, sequentially generating a preset number of sequence numbers with different values according to the preset sequence number sequence; the preset sequence number sequence comprises a first sequence number sequence which generates the sequence number from small to large in value, a second sequence number sequence which generates the sequence number from large to small in value and a third sequence number sequence which generates the sequence number according to the sequence number of the self-defined value.

Optionally, the arbitration method of the input request further includes:

determining that the cache supports storing a maximum number of the input requests;

setting the preset number based on the maximum number; wherein the preset number is not less than the maximum number.

Optionally, the manner of generating the serial number by the second serial number generator is the same as the manner of generating the serial number by the first serial number generator, and the type of a counter used by the second serial number generator is the same as that of the counter used by the first serial number generator, and the initial value of the counter is the same.

Optionally, after the transmitting the arbitration request to the output channel according to a preset rule for processing, the method further includes:

After each arbitration request is detected to be processed, a second sequence number switching instruction is sent to the second sequence number generator, so that the second sequence number generator generates a next expected sequence number corresponding to the current expected sequence number according to the preset sequence number sequence, and the input request output by the cache is checked by using the next expected sequence number.

Counting the total number of input requests meeting the preset effective request conditions, and storing the total number into a target memory;

Accordingly, checking whether each of the arbitration requests is processed, includes:

Retrieving the total number from the target memory;

Detecting whether the number of the processed arbitration requests is the same as the total number;

if the arbitration requests are the same, determining that all the arbitration requests are processed.

Optionally, each input channel is connected with a different cache;

correspondingly, the storing the marked input requests in the cache includes:

storing each marked input request into a cache connected with a corresponding output channel.

Optionally, the buffer memory is a first-in first-out memory, and the first-out memory is used for outputting each input request after the marking written in the current clock cycle in the same clock cycle.

Optionally, the determining whether the input request meeting the preset valid request condition exists in each input channel includes:

detecting whether a data packet starting mark corresponding to a valid input request exists in each input channel;

If the data packet starting mark exists, judging whether a target input request with the data packet starting mark and a corresponding cache finish data handshake according to the preset flag bit of the cache;

and if the data handshake is completed, determining the target input request as the input request meeting the preset valid request condition.

Optionally, the sending a first sequence number switching instruction to the first sequence number generator includes:

performing exclusive OR operation on the data packet start mark and the preset flag bit;

If the exclusive OR operation result is a preset value, a first serial number switching instruction is generated, and the first serial number switching instruction is sent to the first serial number generator.

Optionally, the verifying the input request output by the buffer with the current expected sequence number generated by the second sequence number generator to generate an arbitration request for the input request passing the verification includes:

acquiring a current expected sequence number generated by a second sequence number generator;

comparing the serial numbers of the input requests output by the cache with the current expected serial numbers to screen out the input requests with the serial numbers identical to the current expected serial numbers;

An arbitration request is generated for an input request having a sequence number that is the same as the current expected sequence number.

Optionally, the transmitting the arbitration request to the output channel according to a preset rule for processing includes:

if the number of the arbitration requests is one, directly transmitting the arbitration requests to the output channel for processing;

and if the number of the arbitration requests is a plurality of, sequentially transmitting each arbitration request to the output channel for processing according to a preset multi-request processing rule.

Optionally, the transmitting each arbitration request to the output channel in turn according to a preset multi-request processing rule for processing includes:

Determining the channel number of the input channel corresponding to each arbitration request;

And sequentially polling the arbitration requests according to the sequence from the channel number to the large number so as to transmit the arbitration requests to the output channel for processing.

Determining a current value of a target register; the current value is determined based on the sum of the channel number of the input channel corresponding to the first polled arbitration request in the last round and the preset channel number interval;

And from the current value, sequentially polling each arbitration request based on the channel number of the input channel corresponding to each arbitration request so as to transmit each arbitration request to the output channel for processing.

In a second aspect, the present invention discloses an arbitration device for input requests, applied to an arbiter connected to any one of output channels, the arbiter being connected to at least two input channels, the device comprising:

The request detection module is used for detecting each input channel in the current clock cycle so as to determine whether an input request meeting the preset valid request condition exists in each input channel;

The serial number marking module is used for marking the input request of at least one input channel by utilizing the current serial number generated by the first serial number generator in the current clock period if the input request meeting the preset valid request condition exists in the at least one input channel, and storing each marked input request into a cache;

and the verification module is used for verifying the input request output by the cache by utilizing the current expected sequence number generated by the second sequence number generator so as to generate an arbitration request for the input request passing the verification, and transmitting the arbitration request to the output channel for processing according to a preset rule.

In a third aspect, the present invention discloses an electronic device, comprising:

A memory for storing a computer program;

A processor for executing the computer program to implement the steps of the previously disclosed arbitration method for input requests.

In a fourth aspect, the invention discloses a computer program product comprising computer programs/instructions which, when executed by a processor, implement the steps of the previously disclosed method of arbitrating input requests.

In a fifth aspect, the present invention discloses a computer-readable storage medium for storing a computer program; wherein the computer program, when executed by a processor, implements the steps of the previously disclosed method of arbitrating input requests.

It can be seen that the present invention discloses an arbitration method for input requests, applied to an arbiter connected with any one of the output channels, the arbiter being connected with at least two of the input channels, the method comprising: detecting each input channel in the current clock period to determine whether an input request meeting a preset valid request condition exists in each input channel; if at least one input channel has an input request meeting the preset valid request condition, marking the input request of the at least one input channel by using a current sequence number generated by a first sequence number generator in the current clock cycle, and storing each marked input request into a cache; and checking the input request output by the cache by using the current expected sequence number generated by the second sequence number generator to generate an arbitration request for the checked input request, and transmitting the arbitration request to the output channel for processing according to a preset rule.

The beneficial effects are that: any output channel of the invention is connected with a corresponding arbiter, and the arbiter is connected with at least two input channels, namely the arbiter is applicable to a multi-input-single-output scene. Firstly, the arbiter detects each input channel in the current clock cycle to determine whether an input request meeting the preset valid request condition exists in each input channel, namely, whether valid requests exist in each input channel is judged. If at least one input channel has an input request meeting the preset valid request condition, marking the input request of the at least one input channel by using the current sequence number generated by the first sequence number generator in the current clock period, and storing each marked input request into a cache. That is, first, the present invention does not use the time stamp of the arrival of the request to mark, but uses the current sequence number generated by the first sequence number generator to mark the request, and the data bit width of the sequence number is far lower than the data bit width of the time stamp, so the resource cost is saved; second, the present invention checks all input channels in the current clock cycle, and when there are input requests with preset valid request conditions in multiple input channels, the input requests are marked with the same mark through the current serial number, so that the subsequent requests with the same mark can be processed together. Furthermore, the invention checks the input request output by the buffer memory by using the current expected sequence number generated by the second sequence number generator instead of adopting the sequencing circuit, thereby reducing the clock period of processing, enabling the request to be processed in a streaming mode, generating an arbitration request for the input request which passes the check, and transmitting the arbitration request to an output channel for processing according to a preset rule. By adopting the scheme, the maximum delay of the request can be reduced on the premise of not increasing the average delay based on the arbitration policy of first arrival first service.

Drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings that are required to be used in the embodiments or the description of the prior art will be briefly described below, and it is obvious that the drawings in the following description are only embodiments of the present invention, and that other drawings can be obtained according to the provided drawings without inventive effort for a person skilled in the art.

FIG. 1 is a schematic diagram of a multi-level interconnect network of the present disclosure;

FIG. 2 is a flow chart of an arbitration method for an input request according to the present invention;

FIG. 3 is a schematic diagram of an arbiter according to the present disclosure;

FIG. 4 is a schematic diagram of a sequence number switching logic according to the present disclosure;

FIG. 5 is a schematic diagram illustrating a connection of a cache according to the present disclosure;

FIG. 6 is a flow chart of an arbitration method for an input request according to one embodiment of the present disclosure;

FIG. 7 is a schematic diagram of a sequence number checking logic according to the present disclosure;

FIG. 8 is a flow chart illustrating an arbitration request processing process according to the present disclosure;

FIG. 9 is a schematic diagram of an arbitration device for inputting requests according to the present invention;

fig. 10 is a block diagram of an electronic device according to the present disclosure.

Detailed Description

The following description of the embodiments of the present invention will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present invention, but not all embodiments. All other embodiments, which can be made by those skilled in the art based on the embodiments of the invention without making any inventive effort, are intended to be within the scope of the invention.

FIG. 1 is a schematic illustration of a typical multi-level interconnect network comprised of three levels of nodes, each of the first level nodes having 4 inputs connected to 4 input ports, respectively, and 5 outputs connected to each of the second level nodes, respectively; each node of the second level nodes has 4 inputs respectively connected with each node of the first level nodes, and 5 outputs respectively connected with each node of the third level nodes; the third-season nodes each have 5 inputs respectively connected to each of the second-stage nodes, and 4 outputs respectively connected to 4 output ports. It can be seen that since the nodes perform the function of multiple-input multiple-output data exchange, an arbiter is required to arbitrate the input data, and switch the input data to the appropriate output channel.

Conventional arbiters often employ a round robin scheduling algorithm, where an output port starts from the last authorized input port, queries the next valid input port and grants, then starts from that input port the next time, and so on. However, since the polling arbitration is inherently random, the input data that arrives at the node first will not get the first response on a large probability, but will need to wait. Thus, the poll arbitration, although not changing the total latency of all requests, will increase the maximum latency of the requests, which also means that the system needs to prepare more cache resources, compared to the first-come first-served. While for delay sensitive applications such as audio, video or feedback control systems, the increase in maximum delay is less acceptable. Even more serious, for multi-level interconnection networks, cascading of each level further worsens the maximum delay increase effect described above.

Therefore, the embodiment of the invention discloses an arbitration method, an arbitration device, arbitration equipment, arbitration media and arbitration products for input requests, which can reduce the maximum delay of the requests, save the resource cost and realize the streaming processing of the requests.

Referring to fig. 2, an embodiment of the present invention discloses an arbitration method for an input request, which is applied to an arbiter connected to any one of output channels, the arbiter being connected to at least two input channels, the method comprising:

step S11: and detecting each input channel in the current clock cycle to determine whether an input request meeting the preset valid request condition exists in each input channel.

In this embodiment, any output channel is connected with a corresponding arbiter, and the arbiter is connected with at least two input channels, that is, the arbiter in the present invention is suitable for a multiple input-single output scenario. For a multi-level interconnect network, each mimo switching node may be abstracted as shown in fig. 3 into multiple mimo channels, where each output channel includes a mimo arbiter, i.e., as shown in fig. 3, there are N input channels, M output channels, each output channel is connected to an arbiter, and the arbiter is connected to N input channels.

The sequence number switching logic in the arbiter of the current clock cycle detects each input channel to determine whether there is an input request satisfying the preset valid request condition in each input channel, that is, to determine whether there is a valid request in each input channel.

In a specific embodiment, the determining whether there is an input request that meets a preset valid request condition in each input channel includes: detecting whether a data packet starting mark corresponding to a valid input request exists in each input channel; if the data packet starting mark exists, judging whether a target input request with the data packet starting mark and a corresponding cache finish data handshake according to the preset flag bit of the cache; and if the data handshake is completed, determining the target input request as the input request meeting the preset valid request condition. That is, for each input channel, it is determined whether a data packet start tag corresponding to a valid input request exists in each input channel of the current clock cycle, that is, whether the channel is a valid request, and whether the valid request completes data handshake with a corresponding cache, if the data handshake is completed, the target input request is determined to be an input request meeting the preset valid request condition, and the start tag of the valid request is determined to not only identify the valid request, but also ensure that the multi-cycle request with data is calculated only once. It will be appreciated that special bytes are typically defined in the data transfer protocol to indicate the start of a packet, i.e. a packet start tag, and if a packet start tag is detected, it is determined whether the channel is a valid request; in addition, when the buffer memory can receive data, the value of the preset flag bit is set, so that handshake can be completed with the request. Then, when there is a valid request on the input channel and the data handshake is completed, the input request is considered to satisfy the preset valid request condition.

It should be noted that if the request cannot be written because the cache is full, the above-described preset valid request condition is not satisfied even if it is a valid request, and that for a request with data, if the packet is long, it is only necessary to confirm whether the request is written. In addition, it should be noted that, each input request meeting the condition can only be calculated once, that is, after a certain clock cycle determines that a certain input request meets the preset valid request condition, a certain action needs to be taken to ensure that the request is not calculated as meeting the condition again in the next clock cycle.

The specific method comprises the following steps: first a state machine is set which has two states, an idle state and a packet receiving state. After the circuit is reset, the state machine is set to be in an idle state, when a valid request is received and the valid request is successfully written into the cache, the state machine jumps into a packet receiving state in the next clock cycle, when the end of the packet is detected, the state machine jumps back to the idle state in the next clock cycle, and if the packet starting condition and the packet ending condition are met at the same time, the state machine is kept in the idle state in the next clock cycle. In addition, a packet counter is set, each clock cycle, if one data handshake is completed, the count value is added together and written into the counter in the next clock cycle; if the end of the packet is detected, the counter is cleared in the next clock cycle, and if the above conditions are satisfied at the same time, the counter is cleared in the next clock cycle. Wherein the condition for detecting the end of the packet is that if the data handshake is completed in the current clock cycle and the value of the packet counter is increased by an equal packet length, the packet is ended. After implementing the above steps, the method of ensuring that the request is not written multiple times is to consider a request meeting the requirements only when the following conditions are met: when the state machine is in an idle state, and a valid request is received.

Step S12: if at least one input channel has an input request meeting the preset valid request condition, marking the input request of the at least one input channel by using a current sequence number generated by a first sequence number generator in the current clock cycle, and storing each marked input request into a cache.

In this embodiment, if there is an input request satisfying a preset valid request condition in at least one input channel, the input request of at least one input channel is marked by using a current sequence number generated by a first sequence number generator in a current clock cycle, and then each marked input request is stored in a cache. That is, first, the present invention does not use the time stamp of the arrival of the request to mark, but uses the current sequence number generated by the first sequence number generator to mark the request, and the data bit width of the sequence number is far lower than the data bit width of the time stamp, so the resource cost is saved; second, the present invention checks all input channels in the current clock cycle, and when there are input requests with preset valid request conditions in multiple input channels, the input requests are marked with the same mark through the current serial number, so that the subsequent requests with the same mark can be processed together.

In a specific embodiment, after the input request meeting the preset valid request condition exists in the at least one input channel, the method further includes: and sending a first sequence number switching instruction to the first sequence number generator, so that when the first sequence number generator detects that an input request meeting a preset valid request condition exists in at least one input channel in the next clock period, generating a next sequence number corresponding to the current sequence number according to a preset sequence number sequence, and marking the input request of the input channel by using the next sequence number. That is, if any one of all the input channels has an input request satisfying a preset valid request condition, a first sequence number switching instruction is sent to the first sequence number generator, so that when a valid request also exists in the next clock cycle, the sequence numbers are switched according to the preset sequence number sequence. For example, assuming that the preset sequence number sequence is 0, 1,2 … N and the current sequence number is 2, then the next clock cycle is switched to the next sequence number 3.

Specifically, sending a first sequence number switching instruction to the first sequence number generator includes: performing exclusive OR operation on the data packet start mark and the preset flag bit; if the exclusive OR operation result is a preset value, a first serial number switching instruction is generated, and the first serial number switching instruction is sent to the first serial number generator. That is, the input request and the data handshake signal are sent to the sequence number switching logic, so that the sequence number switching logic performs an exclusive-or operation on the start flag of the data packet and the preset flag bit, if the exclusive-or operation result is a preset value, a first sequence number switching instruction is generated and sent to the first sequence number generator, and an implementation example of the sequence number switching logic is specifically shown in fig. 4, that is, the judging logic output of each channel generates the sequence number switching instruction through the exclusive-or logic.

In another embodiment, after determining whether there is an input request that satisfies the preset valid request condition in each of the input channels, the method further includes: and if the input request meeting the preset valid request condition does not exist in each input channel, prohibiting sending the first sequence number switching instruction to the first sequence number generator, so that the first sequence number generator generates the current sequence number when detecting that the input request meeting the preset valid request condition exists in at least one input channel in the next clock period, and marking the input request of the input channel by utilizing the current sequence number. That is, if no one input channel has an input request meeting the preset valid request condition, the first sequence number switching instruction cannot be sent to the first sequence number generator, and the sequence number generated by the first sequence number generator needs to be kept unchanged, then the first sequence number generator still generates the current sequence number when detecting that at least one input channel has an input request meeting the preset valid request condition in the next clock period, and marks the input request of the input channel by using the current sequence number.

When the first serial number generator acquires the first serial number switching instruction, sequentially generating a preset number of serial numbers with different values according to the preset serial number sequence; the preset sequence number sequence comprises a first sequence number sequence which generates the sequence number from small to large in value, a second sequence number sequence which generates the sequence number from large to small in value and a third sequence number sequence which generates the sequence number according to the sequence number of the self-defined value. That is, a first sequence number generator is used to generate sequence numbers, which needs to be able to sequentially generate a preset number (L) of sequence numbers having different values, and then loop. The preset sequence of the serial numbers can be generated in a mode of from small to large in value, can be generated in a mode of from large to small in value, and can be generated according to a self-defined sequence of values.

Further, the method further comprises the following steps: determining that the cache supports storing a maximum number of the input requests; setting the preset number based on the maximum number; wherein the preset number is not less than the maximum number. That is, the preset number L needs to be equal to or greater than the maximum number of input requests that can be held by the cache. A simple sequence number generator is an N Bit counter, wherein 2 ^N is greater than or equal to L, and when the counter is equal to 2 ^N -1 and a switch instruction is received, the counter returns to zero.

As shown in fig. 5, each input channel is connected with different caches; correspondingly, the storing the marked input requests in the cache includes: storing each marked input request into a cache connected with a corresponding output channel. That is, the incoming request is saved to the cache along with the current sequence number. In a specific embodiment, the buffer is a first-in first-out memory (FIFO), and the FIFO is configured to output each of the input requests after the tag written in the current clock cycle in the same clock cycle. That is, if the input requests of any of the plurality of input channels complete a data handshake with the corresponding cache, i.e., the same clock cycle, the plurality of input requests are written to the cache, the fifo may cause the plurality of input requests to appear at the output of the cache at the same clock cycle (which may be several clock cycles later). It should be noted that caching is an optional component for improving multi-level internet performance, and that if caching is not used, data may be passed through to the next level, or several levels of pipelining may be used.

Step S13: and checking the input request output by the cache by using the current expected sequence number generated by the second sequence number generator to generate an arbitration request for the checked input request, and transmitting the arbitration request to the output channel for processing according to a preset rule.

In this embodiment, the current expected sequence number generated by the second sequence number generator is used to check the input request output by the cache, instead of using the sequencing circuit, so that the clock cycle of processing is reduced, so that the request can be processed in a streaming manner, finally, an arbitration request is generated for the input request that passes the check, and the arbitration request is transmitted to the output channel for processing according to a preset rule.

The method for generating the serial number by the second serial number generator is the same as that for generating the serial number by the first serial number generator, the type of a counter used by the second serial number generator is the same as that of a counter used by the first serial number generator, and the initial value of the counter is the same. That is, the second sequence number generator needs to generate the same sequence number as the first sequence number generator and has the same initial state as the first sequence number generator. For example, when the first sequence number generator is implemented using an N Bit counter, the second sequence number generator also needs to be implemented using an N Bit counter, and both counters have the same initial value. When the second sequence number generator receives a sequence number switching instruction in a certain clock cycle, it will switch to the next sequence number.

In a specific embodiment, after the transmitting the arbitration request to the output channel according to a preset rule for processing, the method further includes: after each arbitration request is detected to be processed, a second sequence number switching instruction is sent to the second sequence number generator, so that the second sequence number generator generates a next expected sequence number corresponding to the current expected sequence number according to the preset sequence number sequence, and the input request output by the cache is checked by using the next expected sequence number. That is, after checking that each arbitration request is processed, a second sequence number switching instruction is sent to the second sequence number generator so that the second sequence number generator switches sequence numbers in a preset sequence number order. The embodiment may adopt synchronous FIFO, i.e. the same clock is used for input and output, so as to ensure that the input requests marked with the same serial number appear at the output end of the buffer memory at the same time, and then generate the arbitration request through verification processing. Thus, when multiple input requests with the same sequence number are not identical at the arrival of the buffer output end, the situation that all arbitration requests are considered to be processed and the expected sequence number is switched to the next one, so that the input requests arriving later are locked without passing the verification is avoided.

The further embodiment specifically provides a scheme for determining whether the arbitration requests are processed completely, and specifically, after the input request meeting the preset valid request condition exists in at least one input channel, the method further includes: counting the total number of input requests meeting the preset effective request conditions, and storing the total number into a target memory; accordingly, checking whether each of the arbitration requests is processed, includes: retrieving the total number from the target memory; detecting whether the number of the processed arbitration requests is the same as the total number; if the arbitration requests are the same, determining that all the arbitration requests are processed. That is, the number of all valid requests in the input channel is counted, the total number is stored in the target memory, when checking whether all the arbitration requests are processed, the total number is obtained from the target memory, and whether the number of the processed arbitration requests is the same as the total number is detected, if so, the processing of all the arbitration requests is completed, otherwise, the processing is not completed.

Referring to fig. 6, an embodiment of the present invention discloses a specific method for arbitrating an input request, and compared with the previous embodiment, the present embodiment further describes and optimizes a technical solution. The method specifically comprises the following steps:

step S21: and detecting each input channel in the current clock cycle to determine whether an input request meeting the preset valid request condition exists in each input channel.

Step S22: if at least one input channel has an input request meeting the preset valid request condition, marking the input request of the at least one input channel by using a current sequence number generated by a first sequence number generator in the current clock cycle, and storing each marked input request into a cache.

Step S23: acquiring a current expected sequence number generated by a second sequence number generator; comparing the serial numbers of the input requests output by the cache with the current expected serial numbers to screen out the input requests with the serial numbers identical to the current expected serial numbers; an arbitration request is generated for an input request having a sequence number that is the same as the current expected sequence number.

In this embodiment, the sequence number of the input request output from the buffer memory will pass through the sequence number checking logic, and the sequence number checking logic compares the sequence number of the input request with the current expected sequence number generated by the second sequence number generator, so as to ensure that only the input request equal to the current expected sequence number can issue an arbitration request. Verifying that a passing request will generate an arbitration request, verifying that an failed request will not generate an arbitration request temporarily, the arbiter processing the valid requests for response based only on the arbitration request, to avoid time stamp based ordering logic,

It will be appreciated that conventional approaches use time stamping and ordering circuitry, which is complex and requires multiple clock cycles to select the earliest request. The embodiment of the invention does not use a time stamp, but uses a serial number, so that the request which is the same as the current expected serial number is the earliest request at the output port of the cache, and needs to be processed first, and the requests which are not equal need to wait. Therefore, the core of the serial number checking logic circuit is a comparator circuit with equal comparison values, and the serial number checking logic circuit has a very simple structure. An example of sequence number verification logic is shown in fig. 7, which is similar to sequence number switching logic, and which also requires a determination of packet start for multi-cycle request packets, and generates an arbitration request when a valid request packet start tag is detected, a data handshake is completed, and the sequence number of the incoming request is equal to the current expected sequence number.

Step S24: if the number of the arbitration requests is one, the arbitration requests are directly transmitted to the output channel for processing.

In this embodiment, the arbiter processes the arbitration requests from all channels and generates a sequence number switching instruction after the processing is completed. As shown in fig. 8, when the arbiter receives only one arbitration request, the input channel of the arbitration request is granted, the arbitration request is directly transmitted to the output channel for processing, and the expected sequence number is switched after the processing is completed.

Step S25: and if the number of the arbitration requests is a plurality of, sequentially transmitting each arbitration request to the output channel for processing according to a preset multi-request processing rule.

In this embodiment, when the arbiter receives a plurality of arbitration requests, all the arbitration requests are sequentially transmitted to the output channels for processing according to a preset multi-request processing rule, that is, the input channels corresponding to the arbitration requests are sequentially authorized according to the preset multi-request processing rule, and the expected sequence numbers are switched after all the arbitration requests are processed, as shown in fig. 8.

In one embodiment, the transmitting each of the arbitration requests to the output channel in turn according to a preset multi-request processing rule for processing includes: determining the channel number of the input channel corresponding to each arbitration request; and sequentially polling the arbitration requests according to the sequence from the channel number to the large number so as to transmit the arbitration requests to the output channel for processing. That is, when there are a plurality of arbitration requests, one of the most straightforward methods is to use polling, that is, determining the channel number of the input channel corresponding to each arbitration request, and polling each arbitration request sequentially in order from smaller channel number to larger channel number. The polling may be performed in order from the largest to the smallest, and this is not limited to this embodiment.

In another embodiment, the sequentially transmitting each of the arbitration requests to the output channel for processing according to a preset multi-request processing rule includes: determining a current value of a target register; the current value is determined based on the sum of the channel number of the input channel corresponding to the first polled arbitration request in the last round and the preset channel number interval; and from the current value, sequentially polling each arbitration request based on the channel number of the input channel corresponding to each arbitration request so as to transmit each arbitration request to the output channel for processing. It will be appreciated that if the polling method is adopted, the priority of the channel is potentially determined by the channel number, for example, if the polling is performed from small to large, the channel with small channel number will have natural advantage, and this advantage will make the delay of the channel with small value number always smaller than that of the channel with large value number, which is essentially to always increase the delay of the channel with large value number to get the low delay of the channel with low value number. Therefore, the invention sets a target register with an initial value of 0, and when a plurality of arbitration requests exist, polling is started from the channel represented by the current value of the target register; the preset lane number interval is 1, that is, the lane number is a series of consecutive numbers, and after each polling is completed, the value of the target register is set to be the first polled lane number+1 in the previous round. In this way, the first processed channel of each poll will get the lowest priority at the next poll, so the channel with the current lowest delay will get the maximum delay with a high probability at the next time. Thus, the equalization of delay among channels is facilitated, the maximum delay is reduced, and the delay distribution is optimized.

For more specific processing procedures in the steps S21 and S22, reference may be made to the corresponding contents disclosed in the foregoing embodiments, and no detailed description is given here.

It can be seen that the present invention uses a relatively simple comparator circuit to determine the precedence relationship of the input requests, and has the core that the second serial number generator which is the same as the first serial number generator is used to process only the input requests which are the same as the current expected serial number each time, and after all the requests which are the same as the current expected serial number are processed, the present invention switches to the next expected serial number. For the first request first service method adopting the time stamp, the invention has simpler circuit structure and fewer hardware resources, the comparison logic can be easily completed in one clock period, the streaming processing of the request can be realized, and the throughput rate is far higher than that of the traditional method. The invention marks the input requests in sequence by using the serial numbers, and is characterized in that the data bit width of the serial numbers is greatly lower than the data bit width of the time stamp, and the input requests in the same clock cycle are marked with the same serial numbers, and the input requests in different clock cycles are marked with different serial numbers; and each sequence number is used for at least one input request, and the situation that certain sequence numbers are skipped is avoided. For the traditional method using polling arbitration, the scheme of the invention can not increase average delay, and can obviously reduce the maximum delay of the request to be served, and under a random scene, the delay distribution of the service is more concentrated on the average delay, so the distribution characteristic is better.

Referring to fig. 9, an embodiment of the present invention discloses an arbitration device for input requests, which is applied to an arbiter connected to any one of output channels, the arbiter being connected to at least two input channels, the device comprising:

a request detection module 11, configured to detect each of the input channels in a current clock cycle, so as to determine whether an input request satisfying a preset valid request condition exists in each of the input channels;

A serial number marking module 12, configured to mark an input request of at least one input channel by using a current serial number generated by a first serial number generator in the current clock cycle if there is an input request satisfying the preset valid request condition in the at least one input channel, and store each marked input request in a cache;

And the verification module 13 is configured to verify the input request output by the cache by using the current expected sequence number generated by the second sequence number generator, so as to generate an arbitration request for the input request passing the verification, and transmit the arbitration request to the output channel for processing according to a preset rule.

It can be seen that the present invention discloses an arbitration device for input requests, which is applied to an arbiter connected with any one of the output channels, wherein the arbiter is connected with at least two input channels, and comprises: the request detection module is used for detecting each input channel in the current clock cycle so as to determine whether an input request meeting the preset valid request condition exists in each input channel; the serial number marking module is used for marking the input request of at least one input channel by utilizing the current serial number generated by the first serial number generator in the current clock period if the input request meeting the preset valid request condition exists in the at least one input channel, and storing each marked input request into a cache; and the verification module is used for verifying the input request output by the cache by utilizing the current expected sequence number generated by the second sequence number generator so as to generate an arbitration request for the input request passing the verification, and transmitting the arbitration request to the output channel for processing according to a preset rule.

In some embodiments, after the input request meeting the preset valid request condition exists in at least one input channel, the apparatus is further configured to send a first sequence number switching instruction to the first sequence number generator, so that when the first sequence number generator detects that the input request meeting the preset valid request condition exists in at least one input channel in a next clock period, a next sequence number corresponding to the current sequence number is generated according to a preset sequence number sequence, and the input request of the input channel is marked by using the next sequence number.

In some embodiments, after determining whether there is an input request satisfying a preset valid request condition in each input channel, the apparatus is further configured to prohibit sending the first sequence number switching instruction to the first sequence number generator if there is no input request satisfying a preset valid request condition in each input channel, so that the first sequence number generator generates the current sequence number when detecting that there is an input request satisfying a preset valid request condition in at least one input channel in a next clock cycle, and marks the input request of the input channel with the current sequence number.

In some specific embodiments, when the first sequence number generator acquires the first sequence number switching instruction, sequentially generating a preset number of sequence numbers with different values according to the preset sequence number sequence; the preset sequence number sequence comprises a first sequence number sequence which generates the sequence number from small to large in value, a second sequence number sequence which generates the sequence number from large to small in value and a third sequence number sequence which generates the sequence number according to the sequence number of the self-defined value.

In some embodiments, the apparatus further comprises:

a maximum number determining unit configured to determine a maximum number of the input requests that the cache supports to store;

A setting unit configured to set the preset number based on the maximum number; wherein the preset number is not less than the maximum number.

In some specific embodiments, the second sequence number generator generates a sequence number in the same manner as the first sequence number generator generates a sequence number, and the second sequence number generator uses the same type of counter as the first sequence number generator, and the initial value of the counter is the same.

In some embodiments, after the arbitration request is transmitted to the output channel for processing according to a preset rule, the apparatus is further configured to send a second sequence number switching instruction to the second sequence number generator after detecting that each arbitration request is processed, so that the second sequence number generator generates a next expected sequence number corresponding to the current expected sequence number according to the preset sequence number order, and uses the next expected sequence number to verify the input request output by the cache.

In some embodiments, if there is an input request in at least one input channel that satisfies the preset valid request condition, the apparatus further includes:

The quantity counting unit is used for counting the total quantity of input requests meeting the preset effective request conditions and storing the total quantity into the target memory;

Correspondingly, the device is further used for acquiring the total number from the target memory; detecting whether the number of the processed arbitration requests is the same as the total number; if the arbitration requests are the same, determining that all the arbitration requests are processed.

In some embodiments, each of the input channels is coupled to a different cache;

Correspondingly, the device is further used for storing each marked input request into a cache connected with a corresponding output channel.

In some embodiments, the buffer is a first-in first-out memory, and the first-out memory is configured to output each of the input requests after the marking written in the current clock cycle in the same clock cycle.

In some embodiments, the device is further configured to perform an exclusive-or operation on the packet start flag and the preset flag; if the exclusive OR operation result is a preset value, a first serial number switching instruction is generated, and the first serial number switching instruction is sent to the first serial number generator.

In some embodiments, the verification module further comprises:

An expected sequence number obtaining unit, configured to obtain a current expected sequence number generated by the second sequence number generator;

The comparison unit is used for comparing the serial numbers of the input requests output by the cache with the current expected serial numbers so as to screen out the input requests with the serial numbers identical to the current expected serial numbers;

And the arbitration request generation unit is used for generating an arbitration request for the input request with the sequence number identical with the current expected sequence number.

In some specific embodiments, the verification module may specifically include:

the single request processing unit is used for directly transmitting the arbitration request to the output channel for processing if the number of the arbitration requests is one;

And the multi-request processing unit is used for sequentially transmitting each arbitration request to the output channel for processing according to a preset multi-request processing rule if the number of the arbitration requests is multiple.

In some embodiments, the multi-request processing unit is specifically configured to determine a channel number of an input channel corresponding to each of the arbitration requests; and sequentially polling the arbitration requests according to the sequence from the channel number to the large number so as to transmit the arbitration requests to the output channel for processing.

In some embodiments, the multi-request processing unit is specifically configured to determine a current value of a target register; the current value is determined based on the sum of the channel number of the input channel corresponding to the first polled arbitration request in the last round and the preset channel number interval; and from the current value, sequentially polling each arbitration request based on the channel number of the input channel corresponding to each arbitration request so as to transmit each arbitration request to the output channel for processing.

Fig. 10 is a schematic structural diagram of an electronic device according to an embodiment of the present invention. Specifically, the method comprises the following steps: at least one processor 21, at least one memory 22, a power supply 23, a communication interface 24, an input output interface 25, and a communication bus 26. Wherein the memory 22 is configured to store a computer program that is loaded and executed by the processor 21 to implement relevant steps in the method for arbitrating an input request performed by an electronic device as disclosed in any of the foregoing embodiments.

In this embodiment, the power supply 23 is configured to provide an operating voltage for each hardware device on the electronic device; the communication interface 24 can create a data transmission channel between the electronic device and the external device, and the communication protocol to be followed is any communication protocol applicable to the technical solution of the present invention, which is not limited herein in detail; the input/output interface 25 is used for acquiring external input data or outputting external output data, and the specific interface type thereof may be selected according to the specific application requirement, which is not limited herein.

Processor 21 may include one or more processing cores, such as a 4-core processor, an 8-core processor, etc. The processor 21 may be implemented in at least one hardware form of DSP (DIGITAL SIGNAL Processing), FPGA (Field-Programmable gate array), PLA (Programmable Logic Array ). The processor 21 may also include a main processor, which is a processor for processing data in an awake state, also called a CPU (Central Processing Unit ), and a coprocessor; a coprocessor is a low-power processor for processing data in a standby state. In some embodiments, the processor 21 may integrate a GPU (Graphics Processing Unit, image processor) for rendering and drawing of content required to be displayed by the display screen. In some embodiments, the processor 21 may also include an AI (ARTIFICIAL INTELLIGENCE ) processor for processing computing operations related to machine learning.

The memory 22 may be a carrier for storing resources, such as a read-only memory, a random access memory, a magnetic disk, or an optical disk, and the resources stored thereon include an operating system 221, a computer program 222, and data 223, and the storage may be temporary storage or permanent storage.

The operating system 221 is used for managing and controlling various hardware devices on the electronic device and the computer program 222, so as to implement the operation and processing of the processor 21 on the mass data 223 in the memory 22, which may be Windows, unix, linux. The computer program 222 may further include a computer program that can be used to perform other specific tasks in addition to the computer program that can be used to perform the arbitration method of an input request performed by an electronic device as disclosed in any of the previous embodiments. The data 223 may include, in addition to data received by the electronic device and transmitted by the external device, data collected by the input/output interface 25 itself, and so on.

Further, the embodiment of the invention also discloses a computer readable storage medium, wherein the storage medium stores a computer program, and when the computer program is loaded and executed by a processor, the method steps of the input request disclosed in any embodiment are realized.

Further, the embodiment of the invention also discloses a computer program product, which comprises a computer program/instruction, and the computer program/instruction realizes the steps of the input request arbitration method disclosed in any of the previous embodiments when being executed by a processor.

In this specification, each embodiment is described in a progressive manner, and each embodiment is mainly described in a different point from other embodiments, so that the same or similar parts between the embodiments are referred to each other. For the device disclosed in the embodiment, since it corresponds to the method disclosed in the embodiment, the description is relatively simple, and the relevant points refer to the description of the method section.

Those of skill would further appreciate that the various illustrative elements and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both, and that the various illustrative elements and steps are described above generally in terms of functionality in order to clearly illustrate the interchangeability of hardware and software. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the solution. Those skilled in the art may implement the described functionality using different approaches for each particular application, but such implementation is not intended to be limiting.

The steps of a method or algorithm described in connection with the embodiments disclosed herein may be embodied directly in hardware, in a software module executed by a processor, or in a combination of the two. The software modules may be disposed in random access Memory (Random Access Memory, i.e., RAM), memory, read-Only Memory (ROM), electrically programmable ROM, electrically erasable programmable ROM, registers, hard disk, a removable disk, a compact disc Read-Only Memory (Compact Disc Read-Only Memory, i.e., CD-ROM), or any other form of storage medium known in the art.

Finally, it is further noted that relational terms such as first and second, and the like are used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Moreover, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus. Without further limitation, an element defined by the phrase "comprising one … …" does not exclude the presence of other like elements in a process, method, article, or apparatus that comprises the element.

The foregoing has described in detail the method, apparatus, device, medium and article of manufacture for arbitration of an input request, and specific examples have been used herein to illustrate the principles and embodiments of the present invention, the above examples being provided only to assist in understanding the method and core idea of the present invention; meanwhile, as those skilled in the art will have variations in the specific embodiments and application scope in accordance with the ideas of the present invention, the present description should not be construed as limiting the present invention in view of the above.

Claims

1. A method of arbitrating input requests, applied to an arbiter coupled to any one of the output channels, the arbiter coupled to at least two of the input channels, the method comprising:

If at least one input channel has an input request meeting the preset valid request condition, marking the input request of the at least one input channel by using a current sequence number generated by a first sequence number generator in the current clock cycle, and storing each marked input request into a cache;

2. The method for arbitrating input requests according to claim 1, wherein after the input request satisfying the preset valid request condition exists in the at least one input channel, the method further comprises:

3. The method for arbitrating input requests according to claim 2, wherein after determining whether there is an input request satisfying a preset valid request condition in each of the input channels, further comprising:

4. The arbitration method of input requests according to claim 2, wherein the first sequence number generator sequentially generates a preset number of sequence numbers with different values according to the preset sequence number sequence when acquiring the first sequence number switching instruction; the preset sequence number sequence comprises a first sequence number sequence which generates the sequence number from small to large in value, a second sequence number sequence which generates the sequence number from large to small in value and a third sequence number sequence which generates the sequence number according to the sequence number of the self-defined value.

5. The method of arbitration for an input request as recited in claim 4, further comprising:

6. The arbitration method for input requests according to claim 4, wherein the second sequence number generator generates a sequence number in the same manner as the first sequence number generator generates a sequence number, and the second sequence number generator uses the same type of counter as the first sequence number generator, and the initial value of the counter is the same.

7. The method according to claim 4, wherein after the transmission of the arbitration request to the output channel for processing according to a preset rule, further comprising:

8. The method for arbitrating input requests according to claim 7, wherein after the input request satisfying the preset valid request condition exists in the at least one input channel, further comprising:

Retrieving the total number from the target memory;

9. The method of claim 2, wherein each of the input channels is connected to a different cache;

correspondingly, the storing the marked input requests in the cache includes:

10. The method according to claim 9, wherein the buffer is a first-in first-out memory, and the first-out memory is configured to output each of the input requests after the marking written in the current clock cycle in the same clock cycle.

11. The method of claim 9, wherein determining whether there is an input request satisfying a preset valid request condition in each of the input channels comprises:

12. The method of arbitration for an input request as recited in claim 11, wherein said sending a first sequence number switch instruction to said first sequence number generator comprises:

13. The method according to claim 1, wherein the verifying the input request output by the cache using the current expected sequence number generated by the second sequence number generator to generate an arbitration request for the input request that passes the verification, comprises:

14. The method according to any one of claims 1 to 13, wherein transmitting the arbitration request to the output channel for processing according to a preset rule comprises:

15. The method according to claim 14, wherein the sequentially transmitting each of the arbitration requests to the output channel for processing according to a preset multi-request processing rule comprises:

16. The method according to claim 14, wherein the sequentially transmitting each of the arbitration requests to the output channel for processing according to a preset multi-request processing rule comprises:

17. An arbitration device for input requests, characterized by being applied to an arbiter connected to any one of the output channels, said arbiter being connected to at least two of the input channels, said device comprising:

18. An electronic device, comprising:

A memory for storing a computer program;

a processor for executing the computer program to implement the steps of the method of arbitration of input requests according to any of claims 1 to 16.

19. A computer program product comprising computer program/instructions which, when executed by a processor, implement the steps of the method of arbitration of an input request as claimed in any one of claims 1 to 16.

20. A non-volatile storage medium for storing a computer program; wherein the computer program when executed by a processor implements the steps of the method of arbitration of input requests according to any of claims 1 to 16.