Item selection apparatus

Patent metadata

Field	Value
Publication number	US-10691701-B2
Application number	US-201715678430-A
Country	US
Kind code	B2
Filing date	Aug 16, 2017
Priority date	Aug 16, 2017
Publication date	Jun 23, 2020
Grant date	Jun 23, 2020

Abstract

An apparatus comprises: selection circuitry to select the two most preferred items from a set of items having ranking information indicative of an order of preference for the set of items. The selection circuitry comprises at least one selection node circuit, each selection node circuit to receive as inputs an indication of a first pair of items and a second pair of items among the set of items, and comprises first selection circuitry and second selection circuitry. The first selection circuitry to first selection circuitry to select as a first selected item a most preferred one of: a most preferred ranked item of the first pair, and a least preferred item of the second pair. The second selection circuitry to select as a second selected item a most preferred one of: a least preferred item of the first pair, and a most preferred item of the second pair.

First claim

I claim:

1. An apparatus comprising:
at least one of: a processor and a memory; and
selection circuitry to select two most preferred items from a set of items having associated ranking information indicative of an order of preference for the set of items, said selection circuitry comprising at least one selection node circuit, each selection node circuit to receive as inputs an indication of a first pair of items and a second pair of items among the set of items, and comprising:
first selecting circuitry to select as a first selected item a most preferred one of:
a most preferred item of the first pair, and
a least preferred item of the second pair, and

second selecting circuitry to select as a second selected item a most preferred one of:
a least preferred item of the first pair, and
a most preferred item of the second pair;

wherein the first selecting circuitry is configured to select the first selected item in parallel with the second selecting circuitry selecting the second selected item.

2. The apparatus according to claim 1 , comprising a 4:2 compression tree comprising a plurality of said selection node circuits arranged in a tree structure to reduce a set of N items to two most preferred items, whereN>4.

3. The apparatus according to claim 1 , wherein a mapping between said two most preferred items and said first and second selected items selected by said at least one selection node circuit is dependent on an initial arrangement of the items within said set.

4. The apparatus according to claim 1 , wherein said selection circuitry is configured to receive, for each of said set of items, item information comprising:
an item index of the item; and
an item ranking mask indicative of a relative ranking between the item and each other item of the set.

5. The apparatus according to claim 4 , wherein the item index for a valid item is one-hot encoded.

6. The apparatus according to claim 5 , wherein the item index for a given item comprises a valid bit indicating the validity of the given item shifted by a number of bit positions corresponding to an item number associated with the given item.

7. The apparatus according to claim 1 , wherein said set of items comprises a set of instructions and the apparatus comprises issue circuitry to issue the two most preferred instructions for processing by first and second processing elements.

8. The apparatus according to claim 7 , wherein the set of instructions comprises instructions capable of being processed by both the first and second processing elements.

9. The apparatus according to claim 1 , comprising memory control circuitry to control access to memory in response to memory transactions, wherein said set of items comprises a set of pending memory transactions.

10. The apparatus according to claim 1 , wherein the set of items comprises cache entries of a cache.

11. The apparatus according to claim 1 , wherein the associated ranking information ranks the set of items according to one of:
item age; and
item priority.

12. The apparatus according to claim 1 , wherein said most preferred items comprise higher ranking items.

13. The apparatus according to claim 1 , wherein said most preferred items comprises lower ranking items.

14. An apparatus comprising:
at least one of: a processor and a memory
means for selecting two most preferred items from a set of items having associated ranking information indicative of an order of preference for the set of items, said means for selecting comprising at least one selection node circuit means, each selection node circuit means to receive as inputs an indication of a first pair of items and a second pair of items among the set of items, and comprising:
means for performing a first selection, to select as a first selected item a most preferred one of:
a most preferred item of the first pair of items, and
a least preferred item of the second pair, and

means for performing a second selection, to select as a second selected item a most preferred one of:
a least preferred item of the first pair, and
a most preferred item of the second pair;

wherein the means for performing a first selection is configured to select the first selected item in parallel with the means for performing a second selection selecting the second selected item.

15. A method for selecting two most preferred items from a set of items having ranking information indicative of an order of preference for the set of items, said method comprising:
processing the set of items using at least one selection node circuit in an apparatus comprising at least one of: a processor and a memory:
each selection node circuit receiving as inputs an indication of a first pair of items and a second pair of items among the set of items, and each selection node circuit performing:
selecting as a first selected item a most preferred one of:
a most preferred item of the first pair, and
a least preferred item of the second pair, and

selecting as a second selected item a most preferred one of:
a least preferred item of the first pair, and
a most preferred item of the second pair;

wherein the first selected item and the second selected item are selected in parallel.

Assignees

• Advanced Risc Mach Ltd

Inventors

• Craske Simon John

Classifications

• G06F7/22 Primary

  Arrangements for sorting or merging computer data on continuous record carriers, e.g. tape, drum, disc · CPC title

• G06F2207/226

  Priority queue, i.e. 1 word in, 1 word out sorter; Output word, i.e. min or max of words in memory · CPC title

• G06F7/00

  Methods or arrangements for processing data by operating upon the order or content of the data handled (logic circuits H03K19/00) · CPC title

• G06F16/24578 Primary

  using ranking · CPC title

• G06F16/2246

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