Selecting an Ith largest or a Pth smallest number from a set of n m-bit numbers

Patent metadata

Field	Value
Publication number	US-12086566-B2
Application number	US-201916670482-A
Country	US
Kind code	B2
Filing date	Oct 31, 2019
Priority date	Oct 31, 2018
Publication date	Sep 10, 2024
Grant date	Sep 10, 2024

Abstract

A method of selecting, in hardware logic, an i th largest or a p th smallest number from a set of n m-bit numbers is described. The method is performed iteratively and in the r th iteration, the method comprises: summing an (m−r) th bit from each of the m-bit numbers to generate a summation result and comparing the summation result to a threshold value. Depending upon the outcome of the comparison, the r th bit of the selected number is determined and output and additionally the (m−r−1) th bit of each of the m-bit numbers is selectively updated based on the outcome of the comparison and the value of the (m−r) th bit in the m-bit number. In a first iteration, a most significant bit from each of the m-bit numbers is summed and each subsequent iteration sums bits occupying successive bit positions in their respective numbers.

First claim

The invention claimed is:

1. A method of selecting, in fixed function hardware circuitry, a number from a set of n m-bit numbers, wherein the selected number is either an i th largest or a p th smallest number from the set of n m-bit numbers, where i, p, m and n are integers, the method comprising a plurality of iterations and each of the iterations comprising:
summing a bit from each of the m-bit numbers to generate a summation result, wherein all the bits being summed occupy an identical bit position within their respective number;
comparing the summation result to a threshold value, wherein the threshold value is calculated based on i or p;
setting, based on an outcome of the comparison, a bit of the selected number; and
for each of the m-bit numbers, based on the outcome of the comparison and a value of the bit from the m-bit number, selectively updating a bit in the m-bit number occupying a next bit position, by
selectively setting a flag associated with the m-bit number based on the outcome of the comparison and a value of the bit from the m-bit number, said selectively setting a flag comprising:
in response to determining that the summation result exceeds the threshold value and that the value of the bit is zero, setting a particular flag associated with the m-bit number, and
in response to determining that the summation result is less than the threshold value and that the value of the bit is one, setting the particular flag associated with the m-bit number and updating the threshold value by an amount equal to the summation result; and
selectively updating a bit in the m-bit number occupying a next bit position based on values of one or more flags associated with the m-bit number, said selectively updating a bit in the m-bit number occupying a next bit position comprising:
in response to determining that the particular flag is set, setting the bit in the m-bit number occupying the next bit position to a predefined value, and
in response to determining that the particular flag associated with the m-bit number is not set, leaving the bit in the m-bit number occupying the next bit position unchanged;

wherein in a first iteration, a most significant bit from each of the m-bit numbers is summed and a most significant bit of the selected number is set and each subsequent iteration sums bits occupying successive bit positions in their respective numbers and sets a next bit of the selected number, and
wherein the method comprises outputting data indicative of the selected number, and using the outputted data for sorting a list of items corresponding to the set of n m-bit numbers.

2. The method according to claim 1 , wherein outputting data indicative of the selected number comprises either:
outputting the selected number; or
outputting an indication of the position, within the n m-bit numbers, of the selected number.

3. The method according to claim 1 , wherein setting, based on an outcome of the comparison, a bit of the selected number comprises:
in response to determining that the summation result exceeds the threshold value, setting the bit of the selected number to one; and
in response to determining that the summation result is less than the threshold value, setting the bit of the selected number to zero.

4. The method according to claim 1 , wherein, in a r th iteration, summing a bit from each of the m-bit numbers to generate a summation result, comprises summing a bit having a bit index m-r from each of the m-bit numbers to generate a summation result, wherein each bit is either an original bit from one of the m-bit numbers or an updated bit from a previous iteration.

5. The method according to claim 1 , wherein the selected number is the i th largest number from the set of n m-bit numbers and the threshold value is equal to i.

6. The method according to claim 1 , wherein the selected number is the p th smallest number from the set of n m−bit numbers and the threshold value is equal to (n−p) or (n−p+1).

7. The method according to claim 1 , wherein the method further comprises:
determining how many of the m-bit numbers have an associated flag that is set; and
in response to determining that n−1 of the m-bit numbers have an associated flag set, outputting data indicative of the m-bit number without an associated flag set.

8. A fixed function hardware circuit arranged to select an i th largest or p th smallest number from a set of n m-bit numbers, where i, p, m and n are integers, the fixed function hardware circuit being arranged to operate iteratively and comprising:
summation logic, implemented in fixed function hardware circuitry, arranged to, in each iteration, sum a bit from each of the m-bit numbers to generate a summation result, wherein all the bits being summed occupy an identical bit position within their respective number such that in a first iteration, a most significant bit from each of the m-bit numbers is summed and each subsequent iteration sums bits occupying successive bit positions in their respective numbers;
comparison logic, implemented in fixed function hardware circuitry, arranged to, in each iteration, compare the summation result generated by the summation logic in that iteration to a threshold value and set a bit of the selected number based on an outcome of the comparison, wherein the threshold value is calculated based on i or p;
flag control logic, implemented in fixed function hardware circuitry, arranged to selectively set a flag associated with the m-bit number based on the outcome of the comparison and a value of the bit from the m-bit number, wherein the flag control logic is arranged to:
in response to determining that the summation result exceeds the threshold value and that the value of the bit is zero, set a particular flag associated with the m-bit number; and in response to determining that the summation result is less than the threshold value and that the value of the bit is one, set the particular flag associated with the m-bit number and updating the threshold value by an amount equal to the summation result;
updating logic, implemented in fixed function hardware circuitry, arranged to, in each iteration and for each of the m-bit numbers, selectively update a bit in the m-bit number occupying a next bit position based on the outcome of the comparison in that iteration and a value of the bit from the m-bit number, wherein the updating logic is arranged to:
selectively update a bit in the m-bit number occupying a next bit position based on values of one or more flags associated with the m-bit number, and
in response to determining that the particular flag is set, set the bit in the m-bit number occupying the next bit position to a predefined value; and in response to determining that the particular flag is not set, leave the bit in the m-bit number occupying the next bit position unchanged; and

an output arranged to output data indicative of the selected number, said data being used for sorting a list of items corresponding to the set of n m-bit numbers.

9. The fixed function hardware circuit according to claim 8 , further comprising:
an early exit hardware logic block, implemented in fixed function hardware circuitry, arranged to determine how many of the m-bit numbers have an associated flag that is set; and in response to determining that n−1 of the m-bit numbers have an associated flag set, to output the m-bit number without an associated flag set as the selected number.

10. An integrated circuit manufacturing system comprising:
a computer readable storage medium having stored thereon a computer readable description of an integrated circuit that describes a fixed function hardware circuit as set forth in claim 8 ;
a layout proces

Assignees

• Imagination Tech Ltd

Inventors

• Rose Thomas

Classifications

• G06F7/78

  for changing the order of data flow, e.g. matrix transposition or LIFO buffers; Overflow or underflow handling therefor · CPC title

• G06F7/57

  Arithmetic logic units [ALU], i.e. arrangements or devices for performing two or more of the operations covered by groups G06F7/483 – G06F7/556 or for performing logical operations {(G06F7/49, G06F7/491 take precedence)} · CPC title

• G06F7/24 Primary

  Sorting, i.e. extracting data from one or more carriers, rearranging the data in numerical or other ordered sequence, and rerecording the sorted data on the original carrier or on a different carrier or set of carriers {sorting methods in general}(G06F7/36 takes precedence) · CPC title

• G06F7/02

  Comparing digital values (G06F7/06, {G06F7/22,} G06F7/38 take precedence) · CPC title

• G06F7/06

  Arrangements for sorting, selecting, merging, or comparing data on individual record carriers · CPC title