Selecting, from a pool of items, a selected item to be associated with a given request

Patent metadata

Field	Value
Publication number	US-11720511-B2
Application number	US-202117336570-A
Country	US
Kind code	B2
Filing date	Jun 2, 2021
Priority date	Jun 2, 2021
Publication date	Aug 8, 2023
Grant date	Aug 8, 2023

Abstract

An apparatus comprises interface circuitry to receive requests and selection circuitry responsive to the interface circuitry receiving a given request to select, from a pool of items, at least one selected item to be associated with the given request. The selection circuitry comprises a plurality of nodes arranged in a tree structure, each node being configured to select m output signals from n input signals provided to that node, wherein n>m. The apparatus comprises control circuitry configured to output, in dependence on a type of the given request, a suppression signal, and the tree structure comprises a gate node configured to suppress, in response to the suppression signal having a first value, selection from input signals received from a given portion of the tree structure to prevent a subset of the pool of items from being selected for at least one type of request.

First claim

I claim:

1. An apparatus comprising:
interface circuitry to receive requests; and
selection circuitry responsive to the interface circuitry receiving a given request to select, from a pool of items, at least one selected item to be associated with the given request;
wherein the selection circuitry comprises a plurality of nodes, each configured to select m output signals from n input signals provided to that node, wherein n>m;
wherein the plurality of nodes are arranged in a tree structure comprising a plurality of layers including at least a first layer of nodes and a final layer comprising a final node, the first layer of nodes being configured to receive input signals indicative of items in the pool of items, and the final node being configured to output a signal indicative of the at least one selected item, the output signals from a given layer of nodes other than the final node being supplied as the input signals for a subsequent layer; and
wherein the apparatus comprises control circuitry configured to output, in dependence on a type of the given request, a suppression signal, and the tree structure comprises a gate node configured to suppress, in response to the suppression signal having a first value, selection from input signals received from a given portion of the tree structure to prevent a subset of the pool of items from being selected for at least one type of request,
wherein:
each node in the tree structure has the same values of n and m, wherein m=1;
the pool of items comprises p items and the subset of the pool of items comprises s items;
the gate node is positioned in a given layer which is y layers before the final layer, where when y=0 the given layer is the final layer itself and when y>0 the given layer is an earlier layer than the final layer;
the gate node is responsive to the suppression signal having the first value to prevent x of its input signals from being selected, wherein x<n; and
the position of the given layer is defined by x/n (y+1) =s/p.

2. The apparatus of claim 1 , wherein
the gate node is responsive to the suppression signal having a second value to prioritize selection from input signals indicative of items in the subset of the pool of items over selection from input signals indicative of items outside of the subset of the pool of items.

3. The apparatus of claim 1 , wherein
the final node comprises the gate node.

4. The apparatus of claim 1 , wherein
the gate node is positioned in a layer other than the final layer.

5. The apparatus of claim 1 , wherein
the selection circuitry is configured to use the same tree structure for the at least one type of request and at least one other type of request.

6. The apparatus of claim 1 , wherein
each node is configured to select the m output signals in dependence on an availability signal associated with each of the n input signals, each availability signal indicating whether an associated item in the pool of items is available for selection.

7. The apparatus of claim 6 , wherein:
the gate node comprises an AND gate to receive the availability signal associated with one of the n input signals supplied to the gate node; and
the AND gate is configured to combine the availability signal and the suppression signal to generate a selection signal to control whether said one of the n input signals is available for selection by the gate node.

8. The apparatus of claim 1 , wherein each node is configured to select them output signals in dependence on at least one of:
a least-recently-used (LRU) policy wherein the m output signals for each node are selected in dependence on which of the items represented by the n input signals were least recently assigned to a request;
a priority policy wherein the m output signals for each node are selected in dependence on a priority associated with at least one of the n input signals; and
a most-recently-used (MRU) policy wherein the m output signals for each node are selected in dependence on which of the items represented by the n input signals were most recently assigned to a request.

9. The apparatus of claim 1 , wherein:
each item in the pool of items comprises a hardware resource selectable for allocating to a request;
for the at least one type of request, the selection circuitry is restricted to selection of a hardware resource outside said subset of the pool of items, and for another type of request, the selection circuitry is capable of selecting any of the hardware resources in the pool of items.

10. An apparatus comprising:
interface circuitry to receive requests; and
selection circuitry responsive to the interface circuitry receiving a given request to select, from a pool of items, at least one selected item to be associated with the given request;
wherein the selection circuitry comprises a plurality of nodes, each configured to select m output signals from n input signals provided to that node, wherein n>m;
wherein the plurality of nodes are arranged in a tree structure comprising a plurality of layers including at least a first layer of nodes and a final layer comprising a final node, the first layer of nodes being configured to receive input signals indicative of items in the pool of items, and the final node being configured to output a signal indicative of the at least one selected item, the output signals from a given layer of nodes other than the final node being supplied as the input signals for a subsequent layer; and
wherein the apparatus comprises control circuitry configured to output, in dependence on a type of the given request, a suppression signal, and the tree structure comprises a gate node configured to suppress, in response to the suppression signal having a first value, selection from input signals received from a given portion of the tree structure to prevent a subset of the pool of items from being selected for at least one type of request,
wherein:
each item in the pool of items comprises an identifier;
the selected item comprises a selected identifier to be associated with the given request;
the interface is configured to receive the requests from at least one agent, and to transmit responses to the at least one agent in response to the requests; and
the interface is responsive to receiving the given request to send an outgoing request and the selected identifier to a completer agent coupled to the interconnect, and to receive a given response and the selected identifier from the completer agent.

11. The apparatus of claim 10 , wherein:
the subset of the pool of items comprises identifiers with a value greater than or equal to a threshold identifier value specifiable for requests of said at least one type.

12. The apparatus of claim 10 , wherein:
the interface is configured to send the outgoing request according to an outgoing request protocol, wherein the outgoing request protocol is selected in dependence on whether the given request is of a first type or a second type; and
the at least one type of request comprises the first type.

13. The apparatus of claim 10 , wherein:
the outgoing request protocol comprises a first request protocol when the given transaction is of the first type and a second request protocol different to the first request protocol when the given transaction is of the second type.

14. The apparatus of claim 12 , wherein:
the interface is configured to send the outgoing request according to a first configuration of the outgoing request protocol when the given transaction is of the first type and to send the outgoing request according to a second configuration of the outgoing request protocol when the transaction is of

Assignees

• Advanced Risc Mach Ltd

Inventors

• Laughton Arthur Brian

Classifications

• G06F13/4027 Primary

  using bus bridges (G06F13/4022 takes precedence) · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F9/5061 Primary

  Partitioning or combining of resources · CPC title

• G06F7/76 Primary

  Arrangements for rearranging, permuting or selecting data according to predetermined rules, independently of the content of the data · CPC title

• G06F9/4843

  by program, e.g. task dispatcher, supervisor, operating system · CPC title