BACKGROUND

Arbiters (and arbitration schemes) are used in computer systems where resources receive more requests at one time (e.g. in a cycle) than can be granted (e.g. processed) at the same time (e.g. in the particular cycle). This often occurs where multiple requesting entities (or requestors) share the same resource(s), where the shared resources may, for example, be memory or storage within the computer system or a computational resource. An arbiter uses a pre-defined set of rules or other criteria, referred to as an arbitration scheme, to decide which of the received requests are granted and which of the received requests are not granted (e.g. are delayed or refused).

A round robin arbiter may use a rotating priority scheme to ensure that, over a period of time, all requestors have some requests granted, i.e. that they are granted some access to the shared resource. However, this is complicated by the fact that not all requestors may submit a request in any cycle (e.g. clock cycle) and so it is not possible to strictly grant requests for each of the requestors in turn without impacting utilisation and efficiency. Furthermore, as the number of requestors increases, delay resulting from the arbitration scheme and time taken to determine which requests are granted in any clock cycle may also increase and this may reduce the throughput and efficiency of the arbitration scheme. Alternatively, to mitigate these effects, the overall size of the hardware may be increased.

The embodiments described below are provided by way of example only and are not limiting of implementations which solve any or all of the disadvantages of known arbiters and arbitration schemes.

SUMMARY

This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter.

Methods of arbitrating between requestors and a shared resource are described. The method comprises generating a vector with one bit per requestor, each initially set to one. Based on a plurality of select signals (one per decision node in a first layer of a binary decision tree, where each select signal is configured to be used by the corresponding decision node to select one of two child nodes), bits in the vector corresponding to non-selected requestors are set to zero. The method is repeated for each subsequent layer in the binary decision tree, based on the select signals for the decision nodes in those layers. The resulting vector is a one-hot vector (in which only a single bit has a value of one). Access to the shared resource is granted, for a current processing cycle, to the requestor corresponding to the bit having a value of one.

A first aspect provides a method of arbitrating between a plurality of ordered requestors and a shared resource in a computing system, the method comprising: generating a vector comprising one bit corresponding to each requestor and setting each bit in the vector to one; based on a plurality of select signals, each select signal corresponding to a different decision node in a first layer of a binary decision tree implemented in hardware logic, setting bits in the vector corresponding to non-selected requestors to zero, wherein each select signal is configured to be used by the corresponding decision node in the binary decision tree to select one of two child nodes; and for each subsequent layer in the binary decision tree and based on one or more select signals corresponding to different decision nodes in the subsequent layer of the binary decision tree, setting bits in the vector corresponding to non-selected requestors to zero, wherein the resulting vector is a one-hot vector comprising a plurality of bits having a value of zero and a single bit having a value of one and wherein the method further comprises: granting access to the shared resource to the requestor corresponding to the bit having a value of one, wherein access is granted for a current processing cycle.

A second aspect provides an arbiter configured to arbitrate between a plurality of ordered requestors and a shared resource in a computing system, the arbiter comprising requestor selection logic and the requestor selection logic comprising: a binary decision tree implemented in hardware logic and comprising a plurality of input nodes and a plurality of decision nodes, each input node corresponding to one of the requestors; and hardware logic arranged to generate a vector comprising one bit corresponding to each requestor and set each bit in the vector to one; wherein each decision node in the binary decision tree is arranged, based on a select signal, to select one of two child nodes and based on the selection to update one or more bit in the vector such that bits in the vector corresponding to non-selected requestors are zero, the resulting vector, after update by all the decision nodes in the binary decision tree, is a one-hot vector comprising a plurality of bits having a value of zero and a single bit having a value of one and the arbiter is further arranged to grant access to the shared resource to the requestor corresponding to the bit having a value of one, wherein access is granted for a current processing cycle.

The arbiter may further comprise select signal generation logic arranged to generate a select signal.

The arbiter may further comprise an input arranged to receive a plurality of valid bits for each processing cycle, each valid bit corresponding to one of the plurality of requestors and indicating whether, in the processing cycle, the requestor is requesting access to the shared resource; and wherein the select signal generation logic comprises: an input arranged to receive a plurality of priority bits for each processing cycle, each priority bit corresponding to one of the plurality of requestors and indicating whether, in the processing cycle, the requestor has priority; hardware logic comprising a plurality of AND logic elements and arranged to generate a plurality of valid_and_priority bits for each processing cycle, each valid_and_priority bit corresponding to one of the plurality of requestors, by combining, for each of the requestors, the corresponding valid bit and priority bits in one of the AND logic elements; a first OR-reduction tree arranged, in each processing cycle, to perform pair-wise OR-reduction on the valid bits and to generate, at each level of the OR-reduction tree, one or more additional valid bits, each corresponding to a different non-overlapping set of requestors; a second OR-reduction tree arranged, in each processing cycle, to perform pair-wise OR-reduction on the valid_and_priority bits and to generate, at each level of the OR-reduction tree, one or more additional valid_and_priority bits, each corresponding to a different non-overlapping set of the requestors; and hardware logic arranged, for each processing cycle and each decision node, to: determine a value of the valid_and_priority bit for a set of requestors comprising all the requestors connected to a left child node of the decision node; determine a value of the valid_and_priority bit for a set of requestors comprising all the requestors connected to a right child node of the decision node; in response to determining that the value of the valid_and_priority bit for the set of requestors comprising all the requestors connected to the right child node of the decision node is equal to one, set a select signal for the node equal to zero; in response to determining that the value of the valid_and_priority bit for the set of requestors comprising all the requestors connected to the left child node of the decision node is equal to one and the value of the valid_and_priority bit for the set of requestors comprising all the requestors connected to the right child node of the decision node is equal to zero, set the select signal for the node equal to one; and in response to determining that both the value of the valid_and_priority bit for the set of requestors comprising all the requestors connected to the left child node of the decision node and the value of the valid_and_priority bit for the set of requestors comprising all the requestors connected to the right child node of the decision node are equal to zero, determine a value of the valid bit for a set of requestors comprising all the requestors connected to the right child node of the decision node and set the select signal for the node equal to an inverse of the valid bit.

A third aspect provides an arbiter configured to perform a method as described herein.

The arbiter may be embodied in hardware on an integrated circuit. There may be provided a method of manufacturing, at an integrated circuit manufacturing system, an arbiter. There may be provided an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the system to manufacture an arbiter. There may be provided a non-transitory computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed, causes a layout processing system to generate a circuit layout description used in an integrated circuit manufacturing system to manufacture an arbiter.

There may be provided an integrated circuit manufacturing system comprising: a non-transitory computer readable storage medium having stored thereon a computer readable integrated circuit description that describes the arbiter; a layout processing system configured to process the integrated circuit description so as to generate a circuit layout description of an integrated circuit embodying the arbiter; and an integrated circuit generation system configured to manufacture the arbiter according to the circuit layout description.

There may be provided computer program code for performing any of the methods described herein. There may be provided non-transitory computer readable storage medium having stored thereon computer readable instructions that, when executed at a computer system, cause the computer system to perform any of the methods described herein.

The above features may be combined as appropriate, as would be apparent to a skilled person, and may be combined with any of the aspects of the examples described herein.

