SELECTING AN ITH LARGEST OR A PTH SMALLEST NUMBER FROM A SET OF N M-BIT NUMBERS

• US 20200133637A1
• Filed: 10/31/2019
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Application

• Current Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Original Assignee: Imagination Technologies Limited (Imagination Technologies Group Ltd.)
• Inventors: Rose, Thomas
• Application Number:
  US16/670,482
• Publication Number:
  US 20200133637A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence
• CPC Class Codes: G06F 7/026 Magnitude comparison, i.e. determining the relative order of operands based on their numerical value, e.g. window comparator
• CPC Class Codes: G06F 7/06 Arrangements for sorting, selecting, merging, or comparing data on individual record carriers
• CPC Class Codes: G06F 7/24 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 generalG06F7/36 takes precedence
• CPC Class Codes: G06F 7/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 Class Codes: G06F 7/78 for changing the order of data flow, e.g. matrix transposition or LIFO buffers; Overflow or underflow handling therefor

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.

Claims

1. A method of selecting, in hardware logic, 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,

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.

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 selectively updating a bit in the m-bit number occupying a next bit position based on the outcome of the comparison and a value of the bit from the m-bit number comprises:

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; 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.

8. The method according to claim 7, wherein 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 comprises:

in response to determining that the summation result exceeds the threshold value and that the value of the bit is zero, setting a min 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 a max flag associated with the m-bit number,

and wherein 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 comprises;

in response to determining that the max flag associated with the m-bit number is set, setting the bit in the m-bit number occupying the next bit position to one;

in response to determining that the min flag associated with the m-bit number is set, setting the bit in the m-bit number occupying the next bit position to zero; and

in response to determining that neither the max flag nor the min flag associated with the m-bit number is set, leaving the bit in the m-bit number occupying the next bit position unchanged.

9. The method according to claim 7, wherein 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 comprises:

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 wherein 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 comprises;

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.

10. The method according to claim 7, 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.

11. The method according to claim 1, wherein selectively updating a bit in the m-bit number occupying a next bit position based on the outcome of the comparison and a value of the bit from the m-bit number comprises:

in response to determining that the summation result exceeds the threshold value and that the value of the bit is zero, updating all bits in the m-bit number to zero; and

in response to determining that the summation result does not exceed the threshold value and that the value of the bit is one, updating all bits in the m-bit number to one.

12. The method according to claim 1, wherein selectively updating a bit in the m-bit number occupying a next bit position based on the outcome of the comparison and a value of the bit from the m-bit number comprises:

in response to determining that the summation result exceeds the threshold value and that the value of the bit is zero, updating all bits in the m-bit number to zero; and

in response to determining that the summation result does not exceed the threshold value and that the value of the bit is one, updating all bits in the m-bit number to zero and reducing the threshold value by an amount equal to the summation result.

13. A hardware logic unit 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 hardware logic unit being arranged to operate iteratively and comprising:

summation logic 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 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;

updating logic 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; and

an output arranged to output data indicative of the selected number.

14. The hardware logic unit according to claim 13, further comprising:

flag control logic 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;

and 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.

15. The hardware logic unit according to claim 14, wherein the flag control logic comprises:

a min flag logic block 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 min flag associated with the m-bit number; and

a max flag logic block arranged to, in response to determining that the summation result is less than the threshold value and that the value of the bit is one, set a max flag associated with the m-bit number,

and wherein the updating logic is arranged to;

in response to determining that the max flag associated with the m-bit number is set, set the bit in the m-bit number occupying the next bit position to one;

in response to determining that the min flag associated with the m-bit number is set, set the bit in the m-bit number occupying the next bit position to zero; and

in response to determining that neither the max flag nor the min flag associated with the m-bit number is set, leave the bit in the m-bit number occupying the next bit position unchanged.

16. The hardware logic unit according to claim 14, 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,

and wherein the updating logic is arranged to;

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.

17. The hardware logic unit according to claim 14, further comprising:

an early exit hardware logic block 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.

18. The hardware logic unit according to claim 13, wherein the updating 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, update all bits in the m-bit number to zero; and

in response to determining that the summation result does not exceed the threshold value and that the value of the bit is one, update all bits in the m-bit number to one.

19. The hardware logic unit according to claim 13, wherein the updating 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, update all bits in the m-bit number to zero; and

in response to determining that the summation result does not exceed the threshold value and that the value of the bit is one, update all bits in the m-bit number to zero and reduce the threshold value by an amount equal to the summation result.

20. 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 hardware logic unit;

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 hardware logic unit; and

an integrated circuit generation system configured to manufacture the hardware logic unit according to the circuit layout description,

wherein the hardware logic unit is arranged to operate iteratively and comprises;

summation logic 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 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;

updating logic 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; and

an output arranged to output data indicative of the selected number.