SELECTING AN ITH LARGEST OR A PTH SMALLEST NUMBER FROM A SET OF N MBIT NUMBERS

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
1
Assignment
First Claim
1. A method of selecting, in hardware logic, a number from a set of n mbit numbers, wherein the selected number is either an i^{th }largest or a p^{th }smallest number from the set of n mbit 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 mbit 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 mbit numbers, based on the outcome of the comparison and a value of the bit from the mbit number, selectively updating a bit in the mbit number occupying a next bit position,wherein in a first iteration, a most significant bit from each of the mbit 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, andwherein the method comprises outputting data indicative of the selected number.
1 Assignment
0 Petitions
Accused Products
Abstract
A method of selecting, in hardware logic, an i^{th }largest or a p^{th }smallest number from a set of n mbit 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 mbit 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 mbit numbers is selectively updated based on the outcome of the comparison and the value of the (m−r)^{th }bit in the mbit number. In a first iteration, a most significant bit from each of the mbit numbers is summed and each subsequent iteration sums bits occupying successive bit positions in their respective numbers.
0 Citations
No References
No References
20 Claims
 1. A method of selecting, in hardware logic, a number from a set of n mbit numbers, wherein the selected number is either an i^{th }largest or a p^{th }smallest number from the set of n mbit 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 mbit 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 mbit numbers, based on the outcome of the comparison and a value of the bit from the mbit number, selectively updating a bit in the mbit number occupying a next bit position, wherein in a first iteration, a most significant bit from each of the mbit 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.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
 13. A hardware logic unit arranged to select an i^{th }largest or p^{th }smallest number from a set of n mbit 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 mbit 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 mbit 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 mbit numbers, selectively update a bit in the mbit number occupying a next bit position based on the outcome of the comparison in that iteration and a value of the bit from the mbit number; and an output arranged to output data indicative of the selected number.  View Dependent Claims (14, 15, 16, 17, 18, 19)
 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 mbit 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 mbit 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 mbit numbers, selectively update a bit in the mbit number occupying a next bit position based on the outcome of the comparison in that iteration and a value of the bit from the mbit number; and an output arranged to output data indicative of the selected number.
1 Specification
There are many situations where hardware is required to sort two or more input binary numbers, i.e. to arrange them in order of size. Such sorters are typically constructed from a number of identical logic blocks as shown in
Each of the logic blocks 102 receives two nbit integer inputs (a,b) and comprises a comparator that returns a Boolean that indicates whether a>b. The output of the comparator, which may be referred to as the ‘select’ signal, is then used to control a plurality of nbit wide multiplexers that each choose between nbits from a or nbits from b. If the logic block 102 outputs both the maximum and minimum values (from a and b, as shown in the examples in
In the arrangement described above, the select signal is used to power a plurality of logic elements (e.g. logic gates) within a logic block 102 and this results in a large propagation delay. This effect of a delay is caused by a single gate output wire having to charge the transistors in a large number of gates (before these latter gates can propagate their outputs) and may be referred to as ‘fanout’. Whilst this delay may be acceptable when only sorting two input numbers, where these logic blocks 102 are concatenated (e.g. as in the sorter 100 shown in
A solution to this delay is to include a large number of buffers (e.g. at least n buffers, which may be arranged in a tree structure) with each of the buffers being driven by the select signal; however, this results in a hardware arrangement that is significantly larger (e.g. in terms of area of logic).
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 hardware and methods for sorting numbers and/or selecting a number from a set of numbers based on its ordered position in the set.
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.
A method of selecting, in hardware logic, an i^{th }largest or a p^{th }smallest number from a set of n mbit numbers is described. The method is performed iteratively and in the r^{th }iteration, where r is between 1 and m, the method comprises: summing the (m−r)^{th }bit, where the (m−1)^{th }bit is the most significant bit, from each of the mbit numbers to generate a summation result and comparing the summation result to a threshold value. Depending upon the outcome of the comparison, the (m−r)^{th }bit of the selected number is determined and output and additionally the (m−r−1)^{th }bit of each of the mbit numbers is selectively updated based on the outcome of the comparison and the value of the (m−r)^{th }bit in the mbit number. In a first iteration, r=1 and the most significant bit from each of the mbit numbers is summed and the most significant bit of the selected number is output. Each subsequent iteration sums the most significant bits of the numbers yet to be summed, which are the bits occupying successive bit positions in their respective numbers (for r=2 bits in position m−2, for r=3 bits in position m−3, etc.) and outputs the next bit of the selected number. There are examples of this method which also output the index of the i^{th }largest or a p^{th }smallest number.
A first aspect provides a method of selecting, in hardware logic, a number from a set of n mbit numbers, wherein the selected number is either an i^{th }largest or a p^{th }smallest number from the set of n mbit 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 mbit 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 mbit numbers, based on the outcome of the comparison and a value of the bit from the mbit number, selectively updating a bit in the mbit number occupying a next bit position, wherein in a first iteration, a most significant bit from each of the mbit 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.
A second aspect provides a hardware logic unit arranged to select an i^{th }largest or p^{th }smallest number from a set of n mbit 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 mbit 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 mbit 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 mbit numbers, selectively update a bit in the mbit number occupying a next bit position based on the outcome of the comparison in that iteration and a value of the bit from the mbit number; and an output arranged to output data indicative of the selected number.
A third aspect provides a hardware logic unit configured to perform the method described above.
A fourth aspect provides a method of manufacturing, using an integrated circuit manufacturing system, a hardware logic unit as detailed above.
A fifth aspect provides an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture a hardware logic unit as detailed above.
A sixth aspect provides a computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture a hardware logic unit as detailed above.
A seventh aspect provides 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 as detailed above; 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.
An eighth aspect provides a method, implemented in hardware logic, for generating and selecting a number, the method comprising: performing a MSBfirst (most significant bit first) iterative generating process for generating a set of n numbers; concurrently with performing the MSBfirst iterative generating process for generating the set of n numbers, performing a MSBfirst iterative selection process to select either an i^{th }largest or a p^{th }smallest number from the set of n numbers, where i, p and n are integers; and in response to the MSBfirst iterative selection process determining that a particular one of the numbers of said set of n numbers will not be the selected number, halting the generation of said particular number by said MSBfirst iterative generating process after at least one of the bits of said particular number has been generated and before all of the bits of said particular number have been generated, wherein the method comprises outputting data indicative of the selected number.
A ninth aspect provides a processing unit configured to generate and select a number, the processing unit comprising: a generation logic unit, implemented in hardware, configured to perform a MSBfirst iterative generating process for generating a set of n numbers; a selection logic unit, implemented in hardware, configured to operate concurrently with the generation logic unit, and configured to perform a MSBfirst iterative selection process to select either an i^{th }largest or a p^{th }smallest number from the set of n numbers, where i, p and n are integers; and an output arranged to output data indicative of the selected number, wherein the processing unit is configured to, in response to the selection logic unit determining that a particular one of the numbers of said set of n numbers will not be the selected number, cause the generation logic unit to halt the generation of said particular number by said MSBfirst iterative generating process after at least one of the bits of said particular number has been generated and before all of the bits of said particular number have been generated.
A tenth aspect provides a processing unit configured to perform the method for generating and selecting a number, as detailed above.
An eleventh aspect provides a method of manufacturing, using an integrated circuit manufacturing system, a processing unit as detailed above.
A twelfth aspect provides an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture a processing unit as detailed above.
A thirteenth aspect provides a computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture a processing unit as detailed above.
A fourteenth aspect provides 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 processing unit as detailed above; 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 processing unit; and an integrated circuit generation system configured to manufacture the processing unit according to the circuit layout description.
The number sorting hardware logic unit and/or processor comprising hardware logic configured to perform one of the methods as described herein may be embodied in hardware on an integrated circuit. There may be provided a method of manufacturing, at an integrated circuit manufacturing system, a number sorting hardware logic unit and/or a processor comprising hardware logic configured to perform one of the methods as described herein. There may be provided an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the system to manufacture an number sorting hardware logic unit and/or a processor comprising hardware logic configured to perform one of the methods as described herein. There may be provided a nontransitory 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 a number sorting hardware logic unit and/or a processor comprising hardware logic configured to perform one of the methods as described herein.
There may be provided an integrated circuit manufacturing system comprising: a nontransitory computer readable storage medium having stored thereon a computer readable integrated circuit description that describes the number sorting hardware logic unit and/or processor comprising hardware logic configured to perform one of the methods as described herein; 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 number sorting hardware logic unit and/or processor comprising hardware logic configured to perform one of the methods as described herein; and an integrated circuit generation system configured to manufacture the number sorting hardware logic unit and/or processor comprising hardware logic configured to perform one of the methods as described herein 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 nontransitory 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.
Examples will now be described in detail with reference to the accompanying drawings in which:
The accompanying drawings illustrate various examples. The skilled person will appreciate that the illustrated element boundaries (e.g., boxes, groups of boxes, or other shapes) in the drawings represent one example of the boundaries. It may be that in some examples, one element may be designed as multiple elements or that multiple elements may be designed as one element. Common reference numerals are used throughout the figures, where appropriate, to indicate similar features.
The following description is presented by way of example to enable a person skilled in the art to make and use the invention. The present invention is not limited to the embodiments described herein and various modifications to the disclosed embodiments will be apparent to those skilled in the art.
Embodiments will now be described by way of example only.
There are many applications where it is useful to select the i^{th }largest or p^{th }smallest integer from a set of integers. Typically this is implemented using a sorting algorithm, or sorting network (e.g. as described above with reference to
Described herein is a method and hardware for selecting the i^{th }largest or p^{th }smallest number from a set of n mbit numbers without first sorting the set of numbers. Using the methods described herein, the hardware is smaller than a sorting network, e.g. it scales in area as O(n*m) rather than O(m*n*(ln(n)^{2})). Furthermore, as the method is iterative, the area of the hardware used to implement the method can be made even smaller by trading performance/throughput (e.g. by synthesizing only one iteration or less than m iterations and then reusing the hardware logic over multiple cycles). Additionally, the method enables performance/throughput to be increased at a cost of additional area (e.g. by increasing the number of bits that are assessed in each iteration above 1).
The methods described herein may be adapted to apply to numbers represented in signed or unsigned fixed point format, floating point format and signed or unsigned normalised format. For example, for signed and floating point numbers, the top bit of each number is negated on both input to the method and output from the method. For unsigned fixed point numbers, no changes are required to the methods. For normalised formats, the bit string is treated as a normal unsigned (or signed) number. In various examples, the numbers may be integers. In various examples, the numbers may be binary approximations of values with no finite binary representation in the standard fixed point format (e.g. ⅓ or the square root of 2), where the binary approximations are generated one bit at a time.
The method involves examining the most significant bit (MSB) from each of the numbers in the set and based on the outcome of the analysis setting one or more flags or mask bits. The method is then repeated, selecting the next bit from each of the numbers in the set, adjusting the bit values dependent upon the flags or mask bits and then performing the same analysis (or very similar analysis) as was performed on the MSB. As with the first iteration (that involved the MSBs), based on the outcome of the analysis, one or more flags or mask bits may be set. The method may iterate through each of the m bits in the numbers in order to determine which of the numbers is the i^{th }largest or p^{th }smallest number. In each iteration, a bit from the output number (i.e. the i^{th }largest or p^{th }smallest number) is set and the output from the method may be either the output number itself or other data that identifies (or indicates) the output number from within the set of n mbit numbers (e.g. in the form of an index of the output number within the set of n numbers).
In describing the various embodiments and examples below, the following notation is used, which can be described with reference to
 n is the number of numbers in the set 200,
 k is the number index and ranges between 0 and (n−1),
 N_{k }are the numbers in the set 200, such that the first number 202 in the set 200 is N_{0 }and the last number 204 in the set 200 is N_{n1},
 m is the number of bits in each of the numbers in the set and each number in the set comprises the same number of bits,
 j is the bit index and ranges between (m−1) for the MSB 206 and 0 for the least significant bit (LSB) 208 in each number, and in examples where the method analyses a single bit from each number in the set in each iteration (from the MSB to the LSB), j may also be referred to as the iteration index,
 r is the iteration number that ranges between one (for the first iteration, where j=m−1) and m (for the last iteration, where j=0), hence j=m−r in examples in which one bit position is considered per iteration.
 x_{k}[j] refers to bit j of the number N_{k}, where j=m−1 for the MSB and j=0 for the LSB,
 z_{k}[j] refers to the modified bit j of the number N_{k},
 i and p are integers in the range 1 to n and the methods described herein identify the i^{th }largest or p^{th }smallest number from the set of numbers, and the desired number, i.e. the i^{th }largest or p^{th }smallest number, is referred to herein as the output number,
 min_{k}[j] is the minimum flag (or min_flag) for the number N_{k }following analysis of the j^{th }bit of the number N_{k},
 min_{k}[m] is the initial (i.e. starting) value of the minimum flag for the number N_{k},
 max_{k}[j] is the maximum flag (or max_flag) for the number N_{k }as set following analysis of the j^{th }bit of the number N_{k},
 max_{k}[m] is the initial (i.e. starting) value of the maximum flag for the number N_{k},
 flag_{k}[j] is the flag for the number N_{k }as set following analysis of the j^{th }bit of the number N_{k }in examples where a single flag is used, and
 flag_{k}[m] is the initial (i.e. starting) value of the single flag for the number N_{k}.
The methods and hardware described herein may be used to find the i^{th }largest or p^{th }smallest number from the set 200 of n mbit numbers without first sorting the set of numbers.
In the first iteration (r=1, j=m−1) the MSBs 206 of each number are summed and if the sum of the MSBs is greater than or equal to i (‘Yes’ in block 302) then this means that the MSB of the i^{th }largest number from the input set (i.e. the MSB of the output number) is a one and the MSB of the output number may be set to one (block 305). However, if the sum of the MSBs is less than i (‘No’ in block 302), then this means that the MSB of the i^{th }largest number from the input set (i.e. the MSB of the output number) is a zero and the MSB of the output number may be set to zero (block 307). Additionally, in response to determining that the sum of the MSBs is greater than or equal to i (‘Yes’ in block 302), the min_flag is set for all those numbers with an MSB=0 (block 304) and in response to determining that the sum of the MSBs is not greater than or equal to i (‘No’ in block 302), the max_flag is set for all those numbers with an MSB=1 (block 306).
The second iteration (r=2, j=m−2) starts by taking the next bit from each of the numbers and modifying the bits using the flag values (block 308). In particular, the value of the bits may be altered where either the min_flag or the max_flag is set for the number (i.e. the value of the bits are selectively updated based on the flags and the values of the bits)), as shown in
The alteration of the bits (in block 308, as shown in detail in
z_{k}[j]=x_{k}[j]·
where · represents a logical AND operation and + represents a logical OR operation. The corresponding hardware arrangement 320, which may be replicated ntimes (one for each number in the set 200) is shown in
The altered bits (as generated in block 308) are then summed and if the sum is greater than or equal to i (‘Yes’ in block 302) then this means that the next bit of the i^{th }largest number from the input set (i.e. the next bit of the output number) is a one and the next bit of the output bit may be set to one (block 305); however, if the sum is less than i (‘No’ in block 302), then this means that the next bit of the i^{th }largest number from the input set (i.e. the next bit of the output number) is a zero and the next bit of the output number may be set to zero (block 307). In this way the method builds the output number (in blocks 305 and 307), one bit at a time and one bit per iteration. In response to determining that the sum is greater than or equal to i (‘Yes’ in block 302), the min_flag is set for all those numbers with an altered bit equal to zero (block 304) and in response to determining that the sum is not greater than or equal to i (‘No’ in block 302), the max_flag is set for all those numbers with an altered bit equal to one (block 306).
The summing of the bits (in block 302) can also be described by the following logic equation:
sum_{j}=Σ_{k=0}^{n1}z_{k}[j]
The corresponding hardware arrangement 328 comprises a plurality of adders (e.g. a plurality of full adders 330 which each add together three bits, i.e. for three different values of k, followed by one or more ripple carry adders 332). An example hardware arrangement is shown in
The updating of the minimum flag (in block 304) and maximum flag (in block 306) can also be described by the following logic equations:
y[j]=(sum_{j}≥i)?1:0
min_{k}[j]=min_{k}[j+1]+(y[j]·
max_{k}[j]=max_{k}[j+1]+(
In these last two equations, the first terms refer to the flag values from the previous iteration and are used to ensure that the flag is not changed if it has already been set by an earlier bit within a number. The same two last equations may also be used when referring to the altered bits (z_{k}[j]) by simply replacing x_{k}[j] by z_{k}[j], as x_{k}[j]=z_{k}[j] when both flags are 0 and if either of the flags are 1 then the value of x_{k}[j] is irrelevant in the equations above, however the hardware implementation using the altered bits may be larger (in terms of area of hardware logic) than using the original bits. The corresponding hardware arrangements 336, 338 are shown in
The method of
Performing a bitwise OR on the min_{k}[j] and max_{k}[j] signals and then negating the result yields a signal which has a 1 in the k^{th }bit if, and only if, bits m−1 to j of the output number matches bits m−1 to j in the number N_{k}.
The method of
In the second iteration, the next bits in each of the 5 numbers are first modified based on the flag values (block 308) to get the z_{k}[m−2] values and in this example, as only the flags for numbers N_{1 }and N_{4 }are set, only these bits are modified from a one to a zero. The modified bits 404 are then summed and the result is 1. As the sum is less than i (‘No’ in block 302), the next bit of the output number is set to zero (block 307) and the max_flag is set for those numbers where the modified bit is one (block 306). In the example shown, the max_flag is set for number N_{2}.
The third iteration again starts by modifying the next bits in each of the 5 numbers based on the flag values (block 308) to get the z_{k}[m−3] values and in this example, as the flags for numbers N_{1}, N_{2 }and N_{4 }are set, only these bits are affected, although as shown in
It can be appreciated that if m=8 in the example of
Whilst
In another example method of calculating the p^{th }smallest number from the input set of n mbit numbers, all the input numbers N_{k }may be bitwise inverted (N_{k}→
The second iteration (j=m−2) starts by taking the next bit from each of the numbers (block 508), where some of these numbers may be the original numbers and others are the numbers that were modified in the first iteration (e.g. in block 504 or 506). The bits are summed and dependent upon the whether the sum is greater than or equal to i (in block 302), one or more of the remaining, original numbers may be set to all zeros (in block 504) or all ones (in block 506) and a further bit is added to the output number (in block 305 or 307).
The updating of the numbers (in blocks 504 and 506) can also be described by the following logic equations:
z_{k}[h]=y[j]·(x_{k}[j]·x_{k}[h])+
for h=0, 1, . . . , m−1.
The method of
The method of
In the second iteration 604, the next bits in each of the 5 numbers (original numbers N_{0}, N_{2}, N_{3 }and modified numbers N_{1 }and N_{4}) are summed and the result is 1. As the sum is less than i (‘No’ in block 302), the next most significant bit of the output number 603 is set to zero (block 307) and those numbers where the bit is one are modified so that all their bits are equal to one (block 506) and in the example shown number N_{2 }is modified in this way.
In the third iteration 606, the next bits in each of the 5 numbers (original numbers N_{0 }and N_{3 }and modified numbers N_{1 }N_{2 }and N_{4}) are summed and in this case the result is 2. As the sum is less than i (‘No’ in block 302), the next bit of the output number 603 is set to one (block 307) and those numbers where the bit is one have all their bits set equal to one (block 506) and in the example shown number No is modified in this way. At this point there is only one original number in the set (i.e. one number that is not all ones or all zeros), number N_{3}, and this is therefore the output number, i.e. the i^{th }largest number from the input set. The method may stop at this point (e.g. if logic is provided to assess the flags and determine when only one original, unmodified number remains in the set) or the method may continue until all bits have been assessed and all bits of the output number generated (one bit per iteration).
Whilst
In another example method of calculating the p^{th }smallest number from the input set of n mbit numbers, all the input numbers N_{k }may be bitwise inverted (N_{k}→
The second iteration (j=m−2) starts by taking the next bit from each of the numbers (block 508), where some of these numbers may be the original numbers and others are the numbers that were modified (e.g. to be all zeros) in the first iteration. The bits are summed and dependent upon the whether the sum is greater than or equal to i (in block 302), the next bit in the output integer is set (in block 305 or 307) and different numbers from the remaining, original numbers may be set to all zeros (in block 504 or 706). Only if the sum was less than i (‘No’ in block 302), is the value of i is further decremented by the total of the summation in that iteration (block 707). The method of
The updating of the numbers (in blocks 504 and 706) can also be described by the following logic equations:
z_{k}[h]=
for h=0, 1, . . . , m−1.
The method of
In the second iteration 804, the next bits in each of the 5 numbers (original numbers N_{0}, N_{2}, N_{3 }and modified numbers N_{1 }and N_{4}) are summed and the result is 1. As the sum is less than i (‘No’ in block 302), the next bit in the output number is set to zero (block 307) and those numbers where the bit is one are modified so that all their bits are equal to zero (block 706) and in the example shown number N_{2 }is modified in this way. The value of i is then decremented by the result of the summation (i.e. by one) so that for the next iteration i=2.
In the third iteration 806, the next bits in each of the 5 numbers (original numbers N_{0 }and N_{3 }and modified numbers N_{1 }N_{2 }and N_{4}) are summed and in this case the result is 1. As the sum is less than i (‘No’ in block 302), the next bit in the output number is set to zero (block 307) and those numbers where the bit is one are modified so that all their bits are equal to zero (block 706) and in the example shown number N_{0 }is modified in this way. The value of i may be decremented again by the result of the summation (i.e. by one) so that i=1. At this point there is only one original number in the set, number N_{3}, and this is therefore the output number, i.e. the i^{th }largest number from the input set. The method may stop at this point (e.g. if logic is provided to assess the flags and determine when only one original, unmodified number remains in the set) or the method may continue until all bits have been assessed.
Whilst
The second iteration (j=m−2) starts by taking the next bit from each of the numbers and modifying the bits using the flag values (block 908). If the flag is set for a number, then the bit is set to a predefined value, e.g. zero, irrespective of whether the bit value is actually a one or a zero. If the flag is not set, then the value of the bit is left unchanged.
The alteration of the bits (in block 908) can also be described by the following logic equation:
z_{k}[j]=x_{k}[j]·
The corresponding hardware arrangement 340, which may be replicated ntimes (one for each number in the set 200) is shown in
The altered bits (as generated in block 908) are then summed and dependent upon the whether the sum is greater than or equal to i (in block 302), one or more further flags may be set (in block 904 or 906). If the predefined value is zero and the sum was less than i (‘No’ in block 302), the value of i is updated by decrementing the threshold value by the total of the summation in that iteration (block 707). Letting i_{j }denote the threshold value, i, used in the comparison of the j^{th }bits, this updating can be described by:
In a variation of that shown in
The method of
Whilst
In yet further variations, instead of using flags or updating the bits within the numbers, bits in a mask may be set in response to the comparison (e.g. in block 302) and then for subsequent iterations, the bits in the numbers may be combined (e.g. using AND gates) with the mask values. This has the same effect as the updating of the numbers (in the examples described above).
Synthesis experiments suggest that the use of two flags (as in the methods of
Furthermore, unlike the other methods described herein, the use of two flags (as in the methods of
If the inputs N_{k }to the method of
As shown in
And the hardware is arranged to find the i^{th }largest item in a list of size n of Um values (i.e. unsigned mbit numbers). In the graph shown in
Although the methods are described herein with a single bit being assessed in each iteration, in other examples, more than one bit (e.g. bit pairs) may be assessed in each iteration. This increases the size of the hardware that implements the method but increases the throughput of the hardware.
In the examples described above, there are n numbers in the input set and the number sorting hardware logic unit is arranged to identify the i^{th }largest or p^{th }smallest number from that input set. In some examples, however, there may be fewer than n numbers in the input set, e.g. n′ numbers in the input set. In such examples, where flags are used (e.g. in the methods of
In the examples described above, each of the input numbers N_{k }are mbit numbers, where m is fixed and is the same for all input numbers in the set. In other examples, whilst, the input numbers may each comprise mbits if fully generated, not all mbits (of some or all of the input numbers) may be available (i.e. generated) in a particular iteration. Any of the methods described above may be modified to operate on such input numbers which may be generated by any MSBfirst iterative process (such as CORDIC or Online Arithmetic) and in such examples, the index, j, represents the bit index assuming all mbits have been generated. As noted above, j=m−r in examples in which one bit position is considered per iteration.
In such examples, the additional logic (as described above) may, for example, be used to halt an MSBfirst iterative process for generating a particular input number once it is clear that the number the process is generating will not be the i^{th }largest (or p^{th }smallest, depending upon the implementation). It is therefore useful to determine this at any early stage and avoid unnecessary computation and hence save power.
In various examples, it may be that the numbers N_{k }are values with no finite binary representation in the standard fixed point format (such as ⅓ or the square root of 2) which are being generated 1bit at a time (and hence, whilst m is an integer, the value of m is not fixed but increases in value as more bits are generated). Using the additional logic, the i^{th }largest (or p^{th }smallest, depending upon the implementation) of these numbers may be able to be found by looking at the top r_{max}bits, and then the methods described herein would be able to indicate which of the inputs is the i^{th }largest (or p^{th }smallest, depending upon the implementation) and stop the calculations after r_{max }iterations (e.g. where r_{max}=100). Alternatively, whilst the output value may not definitely be the i^{th }largest (or p^{th }smallest, depending upon the implementation), the value of r_{max }may be set that the output number has a high probability of being the i^{th }largest (or p^{th }smallest, depending upon the implementation). In a variation on this, there may be various check points implemented (e.g. various values of r_{max}) and a decision may be made at each check point in turn until the output number can be identified, without performing this decision at each iteration.
In some of the examples described above and shown in the drawings, the use of specific logic gates (e.g. NOT, AND, OR gates) is described. It will be appreciated that in other examples, any arrangement of hardware logic that implements the same functionality (e.g. as a NOT, AND or OR gates) may be used instead of a single logic gate and these may be referred to as logic blocks (e.g. NOT, AND and OR logic blocks).
The methods described above may be implemented in hardware (e.g. within a number sorting hardware logic unit) or software.
The methods described herein may be embodied in hardware on an integrated circuit, e.g. within an number sorting hardware logic unit. Generally, any of the functions, methods, techniques or components described above can be implemented in software, firmware, hardware (e.g., fixed logic circuitry), or any combination thereof. The terms “module,” “functionality,” “component”, “element”, “unit”, “block” and “logic” may be used herein to generally represent software, firmware, hardware, or any combination thereof. In the case of a software implementation, the module, functionality, component, element, unit, block or logic represents program code that performs the specified tasks when executed on a processor. The algorithms and methods described herein could be performed by one or more processors executing code that causes the processor(s) to perform the algorithms/methods. Examples of a computerreadable storage medium include a randomaccess memory (RAM), readonly memory (ROM), an optical disc, flash memory, hard disk memory, and other memory devices that may use magnetic, optical, and other techniques to store instructions or other data and that can be accessed by a machine.
The terms computer program code and computer readable instructions as used herein refer to any kind of executable code for processors, including code expressed in a machine language, an interpreted language or a scripting language. Executable code includes binary code, machine code, bytecode, code defining an integrated circuit (such as a hardware description language or netlist), and code expressed in a programming language code such as C, Java or OpenCL. Executable code may be, for example, any kind of software, firmware, script, module or library which, when suitably executed, processed, interpreted, compiled, executed at a virtual machine or other software environment, cause a processor of the computer system at which the executable code is supported to perform the tasks specified by the code.
A processor, computer, or computer system may be any kind of device, machine or dedicated circuit, or collection or portion thereof, with processing capability such that it can execute instructions. A processor may be any kind of general purpose or dedicated processor, such as a CPU, GPU, Systemonchip, state machine, media processor, an applicationspecific integrated circuit (ASIC), a programmable logic array, a fieldprogrammable gate array (FPGA), physics processing units (PPUs), radio processing units (RPUs), digital signal processors (DSPs), general purpose processors (e.g. a general purpose GPU), microprocessors, any processing unit which is designed to accelerate tasks outside of a CPU, etc. A computer or computer system may comprise one or more processors. Those skilled in the art will realize that such processing capabilities are incorporated into many different devices and therefore the term ‘computer’ includes set top boxes, media players, digital radios, PCs, servers, mobile telephones, personal digital assistants and many other devices.
It is also intended to encompass software which defines a configuration of hardware as described herein, such as HDL (hardware description language) software, as is used for designing integrated circuits, or for configuring programmable chips, to carry out desired functions. That is, there may be provided a computer readable storage medium having encoded thereon computer readable program code in the form of an integrated circuit definition dataset that when processed (i.e. run) in an integrated circuit manufacturing system configures the system to manufacture hardware logic configured to perform any of the methods described herein, or to manufacture a processor comprising any apparatus described herein. An integrated circuit definition dataset may be, for example, an integrated circuit description.
Therefore, there may be provided a method of manufacturing, at an integrated circuit manufacturing system, a processor comprising hardware logic configured to perform one of the methods as described herein. Furthermore, there may be provided an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, causes the method of manufacturing processor comprising the hardware logic to be performed.
An integrated circuit definition dataset may be in the form of computer code, for example as a netlist, code for configuring a programmable chip, as a hardware description language defining an integrated circuit at any level, including as register transfer level (RTL) code, as highlevel circuit representations such as Verilog or VHDL, and as lowlevel circuit representations such as OASIS(RTM) and GDSII. Higher level representations which logically define an integrated circuit (such as RTL) may be processed at a computer system configured for generating a manufacturing definition of an integrated circuit in the context of a software environment comprising definitions of circuit elements and rules for combining those elements in order to generate the manufacturing definition of an integrated circuit so defined by the representation. As is typically the case with software executing at a computer system so as to define a machine, one or more intermediate user steps (e.g. providing commands, variables etc.) may be required in order for a computer system configured for generating a manufacturing definition of an integrated circuit to execute code defining an integrated circuit so as to generate the manufacturing definition of that integrated circuit.
An example of processing an integrated circuit definition dataset at an integrated circuit manufacturing system so as to configure the system to manufacture a processor comprising hardware logic configured to perform one of the methods as described herein will now be described with respect to
The layout processing system 1304 is configured to receive and process the IC definition dataset to determine a circuit layout. Methods of determining a circuit layout from an IC definition dataset are known in the art, and for example may involve synthesising RTL code to determine a gate level representation of a circuit to be generated, e.g. in terms of logical components (e.g. NAND, NOR, AND, OR, MUX and FLIPFLOP components). A circuit layout can be determined from the gate level representation of the circuit by determining positional information for the logical components. This may be done automatically or with user involvement in order to optimise the circuit layout. When the layout processing system 1304 has determined the circuit layout it may output a circuit layout definition to the IC generation system 1306. A circuit layout definition may be, for example, a circuit layout description.
The IC generation system 1306 generates an IC according to the circuit layout definition, as is known in the art. For example, the IC generation system 1306 may implement a semiconductor device fabrication process to generate the IC, which may involve a multiplestep sequence of photo lithographic and chemical processing steps during which electronic circuits are gradually created on a wafer made of semiconducting material. The circuit layout definition may be in the form of a mask which can be used in a lithographic process for generating an IC according to the circuit definition. Alternatively, the circuit layout definition provided to the IC generation system 1306 may be in the form of computerreadable code which the IC generation system 1306 can use to form a suitable mask for use in generating an IC.
The different processes performed by the IC manufacturing system 1302 may be implemented all in one location, e.g. by one party. Alternatively, the IC manufacturing system 1302 may be a distributed system such that some of the processes may be performed at different locations, and may be performed by different parties. For example, some of the stages of: (i) synthesising RTL code representing the IC definition dataset to form a gate level representation of a circuit to be generated, (ii) generating a circuit layout based on the gate level representation, (iii) forming a mask in accordance with the circuit layout, and (iv) fabricating an integrated circuit using the mask, may be performed in different locations and/or by different parties.
In other examples, processing of the integrated circuit definition dataset at an integrated circuit manufacturing system may configure the system to manufacture a processor comprising hardware logic configured to perform one of the methods as described herein without the IC definition dataset being processed so as to determine a circuit layout. For instance, an integrated circuit definition dataset may define the configuration of a reconfigurable processor, such as an FPGA, and the processing of that dataset may configure an IC manufacturing system to generate a reconfigurable processor having that defined configuration (e.g. by loading configuration data to the FPGA).
In some embodiments, an integrated circuit manufacturing definition dataset, when processed in an integrated circuit manufacturing system, may cause an integrated circuit manufacturing system to generate a device as described herein. For example, the configuration of an integrated circuit manufacturing system in the manner described above with respect to
In some examples, an integrated circuit definition dataset could include software which runs on hardware defined at the dataset or in combination with hardware defined at the dataset. In the example shown in
A first further example provides a method of selecting, in hardware logic, a number from a set of n mbit numbers, wherein the selected number is either an i^{th }largest or a p^{th }smallest number from the set of n mbit 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 mbit 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 mbit numbers, based on the outcome of the comparison and a value of the bit from the mbit number, selectively updating a bit in the mbit number occupying a next bit position, wherein in a first iteration, a most significant bit from each of the mbit 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.
Outputting data indicative of the selected number may comprise either: outputting the selected number; or outputting an indication of the position, within the n mbit numbers, of the selected number.
Setting, based on an outcome of the comparison, a bit of the selected number may comprise: 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.
In a r^{th }iteration, summing a bit from each of the mbit numbers to generate a summation result, may comprise summing a bit having a bit index mr from each of the mbit numbers to generate a summation result, wherein each bit is either an original bit from one of the mbit numbers or an updated bit from a previous iteration.
The selected number may be the i^{th }largest number from the set of n mbit numbers and the threshold value may be equal to i. In other examples, the selected number may be the p^{th }smallest number from the set of n mbit numbers and the threshold value is equal to (n−p) or (n−p+1).
Selectively updating a bit in the mbit number occupying a next bit position based on the outcome of the comparison and a value of the bit from the mbit number may comprise: selectively setting a flag associated with the mbit number based on the outcome of the comparison and a value of the bit from the mbit number; and selectively updating a bit in the mbit number occupying a next bit position based on values of one or more flags associated with the mbit number.
Selectively setting a flag associated with the mbit number based on the outcome of the comparison and a value of the bit from the mbit number may comprise: 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 mbit 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 mbit number, and wherein selectively updating a bit in the mbit number occupying a next bit position based on values of one or more flags associated with the mbit number comprises: in response to determining that the max flag associated with the mbit number is set, setting the bit in the mbit number occupying the next bit position to one; in response to determining that the min flag associated with the mbit number is set, setting the bit in the mbit 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 mbit number is set, leaving the bit in the mbit number occupying the next bit position unchanged.
Selectively setting a flag associated with the mbit number based on the outcome of the comparison and a value of the bit from the mbit number may comprise: 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 mbit 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 mbit number and updating the threshold value by an amount equal to the summation result, and wherein selectively updating a bit in the mbit number occupying a next bit position based on values of one or more flags associated with the mbit number comprises: in response to determining that the particular flag is set, setting the bit in the mbit number occupying the next bit position to a predefined value; and in response to determining that the particular flag associated with the mbit number is not set, leaving the bit in the mbit number occupying the next bit position unchanged. The predefined value may be zero.
Selectively setting a flag associated with the mbit number based on the outcome of the comparison and a value of the bit from the mbit number may comprise: 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 mbit number and updating the threshold value by an amount equal to n minus the summation result; 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 mbit number, and wherein selectively updating a bit in the mbit number occupying a next bit position based on values of one or more flags associated with the mbit number comprises: in response to determining that the particular flag is set, setting the bit in the mbit number occupying the next bit position to a predefined value; and in response to determining that the particular flag associated with the mbit number is not set, leaving the bit in the mbit number occupying the next bit position unchanged. The predefined value may be one.
The method may further comprise: determining how many of the mbit numbers have an associated flag that is set; and in response to determining that n−1 of the mbit numbers have an associated flag set, outputting data indicative of the mbit number without an associated flag set.
Selectively updating a bit in the mbit number occupying a next bit position based on the outcome of the comparison and a value of the bit from the mbit number may comprise: 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 mbit 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 mbit number to one.
Selectively updating a bit in the mbit number occupying a next bit position based on the outcome of the comparison and a value of the bit from the mbit number may comprise: 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 mbit 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 mbit number to zero and reducing the threshold value by an amount equal to the summation result.
The method may comprise m iterations and in the m^{th }iteration, a least significant bit from each of the mbit numbers is summed and a least significant bit of the selected number is set.
A second further example provides a hardware logic unit arranged to select an i^{th }largest or p^{th }smallest number from a set of n mbit 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 mbit 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 mbit 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 mbit numbers, selectively update a bit in the mbit number occupying a next bit position based on the outcome of the comparison in that iteration and a value of the bit from the mbit number; and an output arranged to output data indicative of the selected number.
The hardware logic unit may further comprise: flag control logic arranged to selectively set a flag associated with the mbit number based on the outcome of the comparison and a value of the bit from the mbit number; and wherein the updating logic is arranged to selectively update a bit in the mbit number occupying a next bit position based on values of one or more flags associated with the mbit number.
The flag control logic may comprise: 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 mbit 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 mbit number, and wherein the updating logic is arranged to: in response to determining that the max flag associated with the mbit number is set, set the bit in the mbit number occupying the next bit position to one; in response to determining that the min flag associated with the mbit number is set, set the bit in the mbit 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 mbit number is set, leave the bit in the mbit number occupying the next bit position unchanged.
The flag control logic may be 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 mbit 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 mbit 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 mbit 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 mbit number occupying the next bit position unchanged. The predefined value may be zero.
The flag control logic may be 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 mbit number and updating the threshold value by an amount equal to n minus the summation result; 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 mbit number, and wherein the updating logic is arranged to: in response to determining that the particular flag is set, set the bit in the mbit 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 mbit number occupying the next bit position unchanged. The predefined value may be one.
The hardware logic unit may further comprise: an early exit hardware logic block arranged to determine how many of the mbit numbers have an associated flag that is set; and in response to determining that n−1 of the mbit numbers have an associated flag set, to output the mbit number without an associated flag set as the selected number.
The updating logic may be 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 mbit 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 mbit number to one.
The updating logic may be 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 mbit 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 mbit number to zero and reduce the threshold value by an amount equal to the summation result.
A third further example provides a hardware logic unit configured to perform the method described above.
A fourth further example provides a method of manufacturing, using an integrated circuit manufacturing system, a hardware logic unit as detailed above.
A fifth further example provides an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture a hardware logic unit as detailed above.
A sixth further example provides a computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture a hardware logic unit as detailed above.
A seventh further example provides 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 as detailed above; 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.
An eighth further example provides a method, implemented in hardware logic, for generating and selecting a number, the method comprising: performing a MSBfirst (most significant bit first) iterative generating process for generating a set of n numbers; concurrently with performing the MSBfirst iterative generating process for generating the set of n numbers, performing a MSBfirst iterative selection process to select either an i^{th }largest or a p^{th }smallest number from the set of n numbers, where i, p and n are integers; and in response to the MSBfirst iterative selection process determining that a particular one of the numbers of said set of n numbers will not be the selected number, halting the generation of said particular number by said MSBfirst iterative generating process after at least one of the bits of said particular number has been generated and before all of the bits of said particular number have been generated, wherein the method comprises outputting data indicative of the selected number.
The MSBfirst iterative generating process may be a CORDIC (Coordinate Rotation Digital Computer) process or an Online Arithmetic process.
Performing the MSBfirst iterative selection process may comprise performing a plurality of iterations, wherein each of the iterations may comprise: summing a bit from each of the numbers of the set 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 numbers of the set, based on the outcome of the comparison and a value of the bit from the number, selectively updating a bit in the number occupying a next bit position. In a first iteration, a most significant bit from each of the numbers of the set may be summed and a most significant bit of the selected number may be set and each subsequent iteration sums bits occupying successive bit positions in their respective numbers and sets a next bit of the selected number.
The selected number may be the i^{th }largest number from the set of n numbers and the threshold value is equal to i. In other examples, the selected number may be the p^{th }smallest number from the set of n numbers and the threshold value is equal to (n−p) or (n−p+1).
Each of the n numbers of the set, if fully generated, may be mbit numbers.
Outputting data indicative of the selected number may comprise either: outputting the selected number; or outputting an indication of the position, within the set of n numbers, of the selected number.
A ninth further example provides a processing unit configured to generate and select a number, the processing unit comprising: a generation logic unit, implemented in hardware, configured to perform a MSBfirst iterative generating process for generating a set of n numbers; a selection logic unit, implemented in hardware, configured to operate concurrently with the generation logic unit, and configured to perform a MSBfirst iterative selection process to select either an i^{th }largest or a p^{th }smallest number from the set of n numbers, where i, p and n are integers; and an output arranged to output data indicative of the selected number, wherein the processing unit is configured to, in response to the selection logic unit determining that a particular one of the numbers of said set of n numbers will not be the selected number, cause the generation logic unit to halt the generation of said particular number by said MSBfirst iterative generating process after at least one of the bits of said particular number has been generated and before all of the bits of said particular number have been generated.
The selection logic may comprise: summation logic arranged to, in each iteration, sum a bit from each of the numbers to generate a summation result, wherein all the bits being summed occupy an identical bit position within their respective number; 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; and updating logic arranged to, in each iteration and for each of the numbers, selectively update a bit in the number occupying a next bit position based on the outcome of the comparison in that iteration and a value of the bit from the number. The summation logic may be arranged such that in a first iteration, a most significant bit from each of the numbers is summed and each subsequent iteration sums bits occupying successive bit positions in their respective numbers.
A tenth further example provides a processing unit configured to perform the method for generating and selecting a number, as detailed above.
An eleventh further example provides a method of manufacturing, using an integrated circuit manufacturing system, a processing unit as detailed above.
A twelfth further example provides an integrated circuit definition dataset that, when processed in an integrated circuit manufacturing system, configures the integrated circuit manufacturing system to manufacture a processing unit as detailed above.
A thirteenth further example provides a computer readable storage medium having stored thereon a computer readable description of an integrated circuit that, when processed in an integrated circuit manufacturing system, causes the integrated circuit manufacturing system to manufacture a processing unit as detailed above.
A fourteenth further example provides 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 processing unit as detailed above; 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 processing unit; and an integrated circuit generation system configured to manufacture the processing unit according to the circuit layout description.
Those skilled in the art will realize that storage devices utilized to store program instructions can be distributed across a network. For example, a remote computer may store an example of the process described as software. A local or terminal computer may access the remote computer and download a part or all of the software to run the program. Alternatively, the local computer may download pieces of the software as needed, or execute some software instructions at the local terminal and some at the remote computer (or computer network). Those skilled in the art will also realize that by utilizing conventional techniques known to those skilled in the art that all, or a portion of the software instructions may be carried out by a dedicated circuit, such as a DSP, programmable logic array, or the like.
The methods described herein may be performed by a computer configured with software in machine readable form stored on a tangible storage medium e.g. in the form of a computer program comprising computer readable program code for configuring a computer to perform the constituent portions of described methods or in the form of a computer program comprising computer program code means adapted to perform all the steps of any of the methods described herein when the program is run on a computer and where the computer program may be embodied on a computer readable storage medium. Examples of tangible (or nontransitory) storage media include disks, thumb drives, memory cards etc. and do not include propagated signals. The software can be suitable for execution on a parallel processor or a serial processor such that the method steps may be carried out in any suitable order, or simultaneously.
The hardware components described herein may be generated by a nontransitory computer readable storage medium having encoded thereon computer readable program code.
Memories storing machine executable data for use in implementing disclosed aspects can be nontransitory media. Nontransitory media can be volatile or nonvolatile. Examples of volatile nontransitory media include semiconductorbased memory, such as SRAM or DRAM. Examples of technologies that can be used to implement nonvolatile memory include optical and magnetic memory technologies, flash memory, phase change memory, resistive RAM.
A particular reference to “logic” refers to structure that performs a function or functions. An example of logic includes circuitry that is arranged to perform those function(s). For example, such circuitry may include transistors and/or other hardware elements available in a manufacturing process. Such transistors and/or other elements may be used to form circuitry or structures that implement and/or contain memory, such as registers, flip flops, or latches, logical operators, such as Boolean operations, mathematical operators, such as adders, multipliers, or shifters, and interconnect, by way of example. Such elements may be provided as custom circuits or standard cell libraries, macros, or at other levels of abstraction. Such elements may be interconnected in a specific arrangement. Logic may include circuitry that is fixed function and circuitry can be programmed to perform a function or functions; such programming may be provided from a firmware or software update or control mechanism. Logic identified to perform one function may also include logic that implements a constituent function or subprocess. In an example, hardware logic has circuitry that implements a fixed function operation, or operations, state machine or process.
The implementation of concepts set forth in this application in devices, apparatus, modules, and/or systems (as well as in methods implemented herein) may give rise to performance improvements when compared with known implementations. The performance improvements may include one or more of increased computational performance, reduced latency, increased throughput, and/or reduced power consumption. During manufacture of such devices, apparatus, modules, and systems (e.g. in integrated circuits) performance improvements can be tradedoff against the physical implementation, thereby improving the method of manufacture. For example, a performance improvement may be traded against layout area, thereby matching the performance of a known implementation but using less silicon. This may be done, for example, by reusing functional blocks in a serialised fashion or sharing functional blocks between elements of the devices, apparatus, modules and/or systems. Conversely, concepts set forth in this application that give rise to improvements in the physical implementation of the devices, apparatus, modules, and systems (such as reduced silicon area) may be traded for improved performance. This may be done, for example, by manufacturing multiple instances of a module within a predefined area budget.”
Any range or device value given herein may be extended or altered without losing the effect sought, as will be apparent to the skilled person.
It will be understood that the benefits and advantages described above may relate to one embodiment or may relate to several embodiments. The embodiments are not limited to those that solve any or all of the stated problems or those that have any or all of the stated benefits and advantages.
Any reference to ‘an’ item refers to one or more of those items. The term ‘comprising’ is used herein to mean including the method blocks or elements identified, but that such blocks or elements do not comprise an exclusive list and an apparatus may contain additional blocks or elements and a method may contain additional operations or elements. Furthermore, the blocks, elements and operations are themselves not impliedly closed.
The steps of the methods described herein may be carried out in any suitable order, or simultaneously where appropriate. The arrows between boxes in the figures show one example sequence of method steps but are not intended to exclude other sequences or the performance of multiple steps in parallel. Additionally, individual blocks may be deleted from any of the methods without departing from the spirit and scope of the subject matter described herein. Aspects of any of the examples described above may be combined with aspects of any of the other examples described to form further examples without losing the effect sought. Where elements of the figures are shown connected by arrows, it will be appreciated that these arrows show just one example flow of communications (including data and control messages) between elements. The flow between elements may be in either direction or in both directions.
The applicant hereby discloses in isolation each individual feature described herein and any combination of two or more such features, to the extent that such features or combinations are capable of being carried out based on the present specification as a whole in the light of the common general knowledge of a person skilled in the art, irrespective of whether such features or combinations of features solve any problems disclosed herein. In view of the foregoing description it will be evident to a person skilled in the art that various modifications may be made within the scope of the invention.