Multiplier-accumulator circuitry and methods

• US 8,645,450 B1
• Filed: 03/02/2007
• Issued: 02/04/2014
• Est. Priority Date: 03/02/2007
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Choe, Kok Heng, Lui, Henry Y., Ngai, Tony K
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US11/713,434
• Time in Patent Office: 2,531 Days
• Field of Search: 708/523, 708/603
• US Class Current: 708/523
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00

Abstract

Multiplier-accumulator circuitry includes circuitry for forming a plurality of partial products of multiplier and multiplicand inputs, carry-save adder circuitry for adding together the partial products and another input to produce intermediate sum and carry outputs, final adder circuitry for adding together the intermediate sum and carry outputs to produce a final output, and feedback circuitry for applying the final output (typically after some delay, e.g., due to registration of the final output) to the carry-save adder circuitry as said another input. The above circuitry may be implemented in so-called “hard IP” (intellectual property) of a field-programmable gate array (“FPGA”) integrated circuit device. If desired, any overflow from the accumulation performed by the above circuitry may be accumulated in “soft” accumulator-overflow circuitry that is implemented in the general-purpose programmable logic of the FPGA.

Claims

1. Multiplier-accumulator circuitry implemented in an integrated circuit device that includes a plurality of instances of general-purpose programmable logic elements and at least one instance of special-purpose circuitry, the multiplier-accumulator circuitry comprising:

circuitry for forming a plurality of partial products of multiplier and multiplicand inputs;

carry-save adder circuitry for adding together the partial products and another input to produce intermediate sum and carry outputs;

final adder circuitry for adding together the intermediate sum and carry outputs to produce a final output having no more bits than the maximum number of bits required for one multiplier-multiplicand product; and

feedback circuitry for applying the final output to the carry-save adder circuitry as said another input for accumulating the final output; and

accumulator-overflow circuitry for accumulating overflow from the final adder circuitry beyond the maximum number of bits from the adding of the intermediate sum and carry outputs;

wherein;

said multiplier-accumulator circuitry, other than said accumulator-overflow circuitry, is implemented in the special-purpose circuitry; and

said accumulator-overflow circuitry is implemented in the general-purpose logic elements.

2. The circuitry defined in claim 1 wherein the circuitry for forming comprises Booth decoder circuitry.

3. The circuitry defined in claim 1 wherein the final adder circuitry comprises carry-propagate adder circuitry.

4. The circuitry defined in claim 1 further comprising:

first input register circuitry for storing the multiplier input; and

second input register circuitry for storing the multiplicand input.

5. The circuitry defined in claim 1 further comprising:

output register circuitry for storing the final output prior to use of that final output as said another input.

6. The circuitry defined in claim 1 wherein the feedback circuitry is selectively operable to apply the final output to the carry-save adder circuitry as said another input.

7. The circuitry defined in claim 1 wherein said integrated circuit device is a field-programmable logic array.

8. The circuitry defined in claim 1 wherein each of the multiplier and multiplicand inputs consists of nine bits.

9. The circuitry defined in claim 8 wherein the circuitry for forming comprises Booth decoder circuitry for forming five partial products.

10. The circuitry defined in claim 9 wherein the carry-save adder circuitry comprises:

first and second banks of carry-save adders, the first bank adding three of the five partial products and a first portion of said another input, and the second bank adding two remaining ones of the five partial products and a second portion of said another input.

11. The circuitry defined in claim 10 wherein the carry-save adder circuitry further comprises:

compressor circuitry for compressing two outputs of a carry-save adder in the first bank and two outputs of a carry-save adder in the second bank to produce two outputs of the carry-save adder circuitry.

12. A method of performing multiplier-accumulator operations comprising:

forming a plurality of partial products of multiplier and multiplicand inputs using multiplication circuitry, said multiplication circuitry having a maximum number of bits;

adding the partial products and another input using carry-save addition circuitry to produce intermediate sum and carry outputs;

adding the intermediate sum and carry outputs using further addition circuitry, to produce a final output having no more bits than the maximum number of bits required for one multiplier-multiplicand product;

registering the final output;

feeding what has been registered back as said another input; and

accumulating overflow beyond the maximum number of bits from the adding of the intermediate sum and carry outputs;

wherein;

said method, other than said accumulating, is implemented in special-purpose circuitry of a field-programmable logic array integrated circuit device; and

said accumulating is implemented in general-purpose logic elements of the field-programmable logic array integrated circuit device.

13. The method defined in claim 12 wherein the forming comprises:

inputting the multiplier and multiplicand inputs to Booth decoder circuitry.

14. The method defined in claim 12 wherein the adding of the intermediate sum and carry outputs is performed using carry-propagate addition circuitry.

15. A field-programmable gate array integrated circuit device comprising:

a plurality of instances of general-purpose programmable logic elements; and

special-purpose circuitry adapted to perform multiplier-accumulator operations and including;

(a) circuitry for forming a plurality of partial products of multiplier and multiplicand inputs;

(b) carry-save adder circuitry for adding together the partial products and another input to produce intermediate sum and carry outputs;

(c) final adder circuitry for adding together the intermediate sum and carry outputs to produce a final output having no more bits than the maximum number required for one multiplier-multiplicand product;

(d) output register circuitry for registering the final output; and

(e) feedback circuitry for selectively applying an output of the output register circuitry to the carry-save adder circuitry as said another input;

the device further comprising accumulator-overflow circuitry, implemented in the logic elements, for accumulating overflow from the final adder circuitry.

16. The device defined in claim 15 wherein the special-purpose circuitry further includes:

(f) input registers for the multiplier and multiplicand inputs.