Multi-element comparison and multi-element addition

1. Apparatus comprising:

one or more non-final reduction stages, each non-final reduction stage comprising:

a non-final intermediate operand forming stage to form non-final intermediate operands from one of an input vector and intermediate sum values output from a preceding non-final reduction stage;

a carry propagate adders stage to add respective pairs of said non-final intermediate operands to form intermediate sum values; and

a final reduction stage comprising:

a final intermediate operand forming stage to form final intermediate operands from intermediate sum values output from a last one of said one or more non-final reduction stages; and

an output adder stage to generate an output operand by adding said final intermediate operands;

wherein said apparatus is arranged to perform a selectable one of multi-element comparison and multi-element addition,

wherein said input vector operand comprises N X-bit elements, where X is a selectable positive integer value and N is an integer value of four or more and each of said non-final intermediate operands contains N/4 X-bit elements,

wherein one or more of the non-final reduction stages further comprises a non-final limit value selecting stage arranged, when performing multi-element comparison, to select N/2 limit values that are one of a larger value or a smaller value from a respective pair of X-bit elements that are added together by said carry propagate adders stage, and

wherein, when performing multi-element comparison, said final intermediate operand forming stage forms each of said final intermediate operands to comprise said N/2 limit values selected by said non-final limit value selecting stage.

2. Apparatus as claimed in claim 1 wherein said non-final limit value selecting stage, active when performing a multi-element comparison, is arranged to select, in dependence upon at least carry values generated by said carry propagate adders stage, said N/2 limit values.

3. Apparatus as claimed in claim 1 , wherein said final reduction stage comprises a final limit value selecting stage, active when performing a multi-element comparison, to select, in dependence upon at least carry values generated by said output adder stage, limit values that are one or a larger value or a smaller value form a pair of elements.

4. Apparatus as claimed in claim 1 , wherein said carry propagate adders stage comprises M Z-bit carry propagate adder circuits, where Z is less than or equal to a minimum value of X that can be selected and M*Z is equal to N*X.

5. Apparatus as claimed in claim 4 , wherein when Z is less than X, then said non-final limit value selecting stage selects said limit values in dependence upon both carry values and propagate values generated by said carry propagate adder circuits.

6. Apparatus as claimed in claim 1 , wherein, if said final intermediate operand values comprise two or more limit values, then said final intermediate operand forming stage separates said limit values within said final intermediate operands by at least one zero bit disposed between said limit values.

7. Apparatus as claimed in claim 1 , wherein, when performing multi-element comparison, said output adder stage selects as said output operand one or more limit values using one or more carry bits generated when adding said final intermediate operands.

8. Apparatus as claimed in claim 1 , wherein, when performing multi-element addition, said final intermediate operand forming stage forms each of said final intermediate operands to represent a sum of element values output from said carry propagate adders stage.

9. Apparatus as claimed in claim 8 , wherein, when performing multi-element addition, said final intermediate operand forming stage extends outputs from half of said carry propagate adders to represent carry bits generated by all of said carry propagate adders.

10. Apparatus as claimed in claim 9 , wherein, when performing multi-element addition, said output adder stage generates as said output operand a sum of said two final intermediate operands.

11. Apparatus as claimed in claim 1 , wherein said input vector operand comprises 2 P X-bit elements, where P is an integer of two or more.

12. Apparatus comprising:

one or more non-final reduction stages, each non-final reduction stage comprising:

non-final intermediate operand forming means for forming non-final intermediate operands from one of an input vector and intermediate sum values output from a preceding non-final reduction stage;

means for adding respective pairs of said non-final intermediate operands to form intermediate sum values; and

a final reduction stage comprising:

final intermediate operand forming means for forming final intermediate operands from intermediate sum values output from a last one of said one or more non-final reduction stages; and

output adder means for generating an output operand by adding said final intermediate operands; wherein

said apparatus is arranged to perform a selectable one of multi-element comparison

and multi-element addition,

wherein said input vector operand comprises N X-bit elements, where X is a selectable positive integer value and N is an integer value of four or more and each of said non-final intermediate operands contains N/4 X-bit elements,

wherein one or more of the non-final reduction stages further comprises a non-final limit value selecting means for selecting, when performing multi-element comparison, N/2 limit values that are one of a larger value or a smaller value from a respective pair of X-bit elements that are added together by said means for adding respective pairs of said non-final intermediate operands, and

wherein, when performing multi-element comparison, said final intermediate operand forming means forms each of said final intermediate operands to comprise said N/2 limit values selected by said non-final limit value selecting means.

13. A method of operating an apparatus comprising one or more non-final reduction circuits and a final reduction circuit, said method comprising the steps of:

within each of said one or more non-final reduction stages:

forming, with a non-final intermediate operand forming circuit, non-final intermediate operands from one of an input vector and intermediate sum values output from a preceding non-final reduction stage;

adding, with a carry propagate adder circuit, respective pairs of said non-final intermediate operands to form intermediate sum values; and within said final reduction circuit:

forming, with a final intermediate operand forming circuit, final intermediate operands from intermediate sum values output from a last one of said one or more non-final reduction circuits; and

generating, with an output adder circuit, an output operand by adding said final intermediate operands;

wherein said method performs a selectable one of multi-element comparison and multi-element addition,

wherein said input vector operand comprises N X-bit elements, where X is a selectable positive integer value and N is an integer value of four or more and each of said non-final intermediate operands contains N/4 X-bit elements, and

wherein one or more of the non-final reduction circuits further comprises a non-final limit value selecting circuit, and when performing multi-element comparison,

said method further comprising:

selecting, with said non-final limit value selecting circuit, N/2 limit values that are one of a larger value or a smaller value from a respective pair of X-bit elements that are added together by said adding, and

forming, with said final intermediate operand forming circuit, each of said final intermediate operands to comprise said N/2 limit values selected by said non-final limit value selecting circuit.