BACKGROUND

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 inFIG.1.FIG.1shows a schematic diagram of an example hardware arrangement100for sorting 4 inputs, x1, x2, x3, x4into size order, i.e. such that output1≥output2≥output3≥output4. It can be seen that this sorter100comprises 5 identical logic blocks102each of which outputs the largest and smallest (i.e. max and min) values of two inputs (which may be denoted a and b).

Each of the logic blocks102receives two n-bit 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 n-bit wide multiplexers that each choose between n-bits from a or n-bits from b. If the logic block102outputs both the maximum and minimum values (from a and b, as shown in the examples inFIG.1), the select signal is used to control the multiplexing of 2n-bits (e.g. in the form of 2n 1-bit wide multiplexers or two n-bit wide multiplexers). Alternatively, if the logic block has only one output (which is either the maximum or minimum of a and b), the select signal is used to control the multiplexing of n-bits (e.g. in the form of n 1-bit wide multiplexers or one n-bit wide multiplexer).

In the arrangement described above, the select signal is used to power a plurality of logic elements (e.g. logic gates) within a logic block102and 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 blocks102are concatenated (e.g. as in the sorter100shown inFIG.1or larger sorters for more than 4 inputs) the resulting delay of the sorting circuit increases which may seriously impact performance (e.g. it may result in the sorting process taking more than a single clock cycle).

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.

SUMMARY

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 ithlargest or a pthsmallest number from a set of n m-bit numbers is described. The method is performed iteratively and in the rthiteration, where r is between 1 and m, the method comprises: summing the (m−r)thbit, where the (m−1)thbit is the most significant 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 (m−r)thbit of the selected number is determined and output and additionally the (m−r−1)thbit of each of the m-bit numbers is selectively updated based on the outcome of the comparison and the value of the (m−r)thbit in the m-bit number. In a first iteration, r=1 and the most significant bit from each of the m-bit 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 ithlargest or a pthsmallest number.

A first aspect provides a method of selecting, in hardware logic, a number from a set of n m-bit numbers, wherein the selected number is either an ithlargest or a pthsmallest 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.

A second aspect provides a hardware logic unit arranged to select an ithlargest or pthsmallest 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.

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 MSB-first (most significant bit first) iterative generating process for generating a set of n numbers; concurrently with performing the MSB-first iterative generating process for generating the set of n numbers, performing a MSB-first iterative selection process to select either an ithlargest or a pthsmallest number from the set of n numbers, where i, p and n are integers; and in response to the MSB-first 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 MSB-first 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 MSB-first 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 MSB-first iterative selection process to select either an ithlargest or a pthsmallest 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 MSB-first 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 non-transitory 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 non-transitory 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 non-transitory 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.

