Multiplication of first and second operands using redundant representation

Patent metadata

Field	Value
Publication number	US-9703531-B2
Application number	US-201514939469-A
Country	US
Kind code	B2
Filing date	Nov 12, 2015
Priority date	Nov 12, 2015
Publication date	Jul 11, 2017
Grant date	Jul 11, 2017

Abstract

A method is provided for multiplying a first operand comprising at least two X-bit portions and a second operand comprising at least one Y-bit portion. At least two partial products are generated, each partial product comprising a product of a selected X-bit portion of the first operand and a selected Y-bit portion of the second operand. Each partial product is converted to a redundant representation in dependence on significance indicating information indicative of a significance of the partial product. In the redundant representation, the partial product is represented using a number of N-bit portions, and in a group of at least two adjacent N-bit portions, a number of overlap bits of a lower N-bit portion of the group have a same significance as some least significant bits of at least one upper N-bit portion of the group. The partial products are added while represented in the redundant representation.

First claim

We claim:

1. A data processing method for multiplying a first operand comprising a plurality of X-bit portions and a second operand comprising at least one Y-bit portion, comprising:
generating, by multiply circuitry, a plurality of partial products, each partial product comprising a product of a selected X-bit portion of the first operand and a selected Y-bit portion of the second operand;
for each partial product, converting the partial product to a redundant representation in dependence on significance indicating information indicative of a significance of the partial product, wherein in said redundant representation the partial product is represented using a plurality of N-bit portions, where in a group of at least two adjacent N-bit portions of the redundant representation, a plurality of overlap bits of a lower N-bit portion of the group have a same significance as a plurality of least significant bits of at least one upper N-bit portion of the group; and
adding the plurality of partial products represented in the redundant representation,
wherein the adding of the partial products is performed using a plurality of N-bit add circuit units for performing independent N-bit additions in parallel using respective N-bit portions of the partial products represented in the redundant representation.

2. The method of claim 1 , wherein the adding of the partial products comprises accumulating the partial products into an accumulator register storing an accumulator value having said redundant representation.

3. The method of claim 1 , wherein the multiplying comprises a plurality of partial product accumulating operations, each partial product accumulating operation corresponding to a different pair of portions selected as said selected X-bit portion and said selected Y-bit portion, and comprising:
multiplying the selected X-bit portion and the selected Y-bit portion to generate one of said plurality of partial products;
converting said one of said plurality of partial products to the redundant representation in dependence on the significance indicating information; and
adding said one of said plurality of partial products in said redundant representation to an accumulator value having said redundant representation to generate an updated accumulator value;
wherein the updated accumulator value for one partial product accumulating operation is used as the accumulator value for a next partial product accumulating operation.

4. The method of claim 3 , wherein the partial product accumulating operations are performed in ascending order of significance of the partial products generated in each partial product accumulating operation;
the method comprises performing a plurality of overlap propagation additions, each overlap propagation addition comprising adding the overlap bits of a given N-bit portion of the accumulator value to non-overlap bits of a following N-bit portion of the accumulator value; and
at least one of said plurality of overlap propagation additions is performed in parallel with the adding step of at least one of said partial product accumulating operations.

5. The method of claim 1 , comprising performing an overlap propagation operation on a result of adding the plurality of partial products in the redundant representation, the overlap propagation operation comprising propagating the overlap bits of one or more N-bit portions of the result to one or more subsequent N-bit portions of the result.

6. The method of claim 1 , wherein the significance indicating information is dependent on a relative position of said selected X-bit portion within said first operand and said selected Y-bit portion within said second operand.

7. The method of claim 1 , wherein the significance indicating information is dependent on a significance indicating parameter associated with at least one of said selected X-bit portion and said selected Y-bit portion.

8. The method of claim 1 , wherein the significance indicating information is dependent on a parameter specified by an instruction for controlling processing circuitry to generate at least one of said partial products.

9. The method of claim 8 , wherein the significance indicating information is dependent on a parameter of the instruction identifying which X-bit portion of the first operand is said selected X-bit portion.

10. The method of claim 1 , wherein the first operand and the second operand comprise integers.

11. The method of claim 1 , wherein X≦53 and Y≦53.

12. The method of claim 11 , wherein each partial product is generated using a floating-point multiplying circuitry for multiplying significands of two floating-point values.

13. The method of claim 1 , comprising a step of mapping the first operand to a corresponding vector of floating-point values, each floating-point value having a significand mapped from a respective X-bit portion of the first operand and an exponent dependent on a significance of that X-bit portion within the first operand;
wherein the significance indicating information for a given partial product is dependent on the exponent of the floating-point value corresponding to the selected X-bit portion used to generate said given partial product.

14. The method of claim 1 , wherein X=Y.

15. The method of claim 1 , wherein X is different to Y.

16. A data processing apparatus comprising processing circuitry configured to perform the method of claim 1 .

17. A data processing apparatus comprising:
multiply circuitry to multiply a selected X-bit portion of a first operand comprising a plurality of X-bit portions and a selected Y-bit portion of a second operand comprising at least one Y-bit portion to generate a partial product;
conversion circuitry to convert the partial product to a converted partial product having a redundant representation in dependence on significance indicating information indicative of a significance of the partial product, wherein in said redundant representation the partial product is represented using a plurality of N-bit portions, where in a group of at least two adjacent N-bit portions of the redundant representation, a plurality of overlap bits of a lower N-bit portion of the group have a same significance as a plurality of least significant bits of at least one upper N-bit portion of the group; and
adding circuitry to add the converted partial product to an accumulator value having said redundant representation,
wherein said adding circuitry comprises a plurality of N-bit add circuit units to perform independent N-bit additions in parallel using corresponding N-bit portions of the converted partial product and the accumulator value.

18. The data processing apparatus according to claim 17 , comprising control circuitry responsive to at least one multiply instruction to control the multiply circuitry and the conversion circuitry to generate a plurality of converted partial products in the redundant representation corresponding to different combinations of portions selected as said selected X-bit portion and said selected Y-bit portion, and the adding circuitry to add each of said plurality of partial products to the accumulator value.

Assignees

• Advanced Risc Mach Ltd

Inventors

• Lutz David Raymond
• Burgess Neil
• Hinds Christopher Neal

Classifications

• G06F7/5443 Primary

  Sum of products (for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00) · CPC title

• G06F7/5336

  overlapped, i.e. with successive bitgroups sharing one or more bits being recoded into signed digit representation, e.g. using the Modified Booth Algorithm · CPC title

• G06F7/50 Primary

  Adding; Subtracting (G06F7/483 - G06F7/491, G06F7/544 - G06F7/556 take precedence) · CPC title

• G06F7/5324

  partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers · CPC title