Large multiplier for programmable logic device

• US 9,063,870 B1
• Filed: 01/17/2013
• Issued: 06/23/2015
• Est. Priority Date: 12/05/2006
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin, Tharmalingam, Kumara
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US13/743,819
• Time in Patent Office: 887 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544
• CPC Class Codes: G06F 7/5324 partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers

Abstract

A plurality of specialized processing blocks in a programmable logic device, including multipliers and circuitry for adding results of those multipliers, can be configured as a larger multiplier by adding to the specialized processing blocks selectable circuitry for shifting multiplier results before adding. In one embodiment, this allows all but the final addition to take place in specialized processing blocks, with the final addition occurring in programmable logic. In another embodiment, additional compression and adding circuitry allows even the final addition to occur in the specialized processing blocks. Circuitry that controls when an input is signed or unsigned facilitates complex arithmetic.

Claims

1. For use in a programmable logic device having a plurality of specialized processing blocks, each of said specialized processing blocks having at least four n-by-n multipliers arranged in four-multiplier units, a method of performing a signed 3n-by-3n multiplication operation, said method comprising:

performing a 2n-by-2n multiplication using four of said n-by-n multipliers in a first of said four-multiplier units;

performing an n-by-n multiplication using one of said n-by-n multipliers in a second of said four-multiplier units; and

performing first and second 2n-by-n multiplications in a third of said four-multiplier units, using two of said n-by-n multipliers for each of said 2n-by-n multiplications;

wherein;

in each of said multiplications, multiplicands representing n most significant bits are treated as signed operands and multiplicands representing n least significant bits are forced to be unsigned;

said method further comprising;

shifting a second partial product of each of said 2n-by-n multiplications to align it with a first partial product of each of said 2n-by-n multiplications for addition within said third four-multiplier unit; and

adding results of said multiplications from said first, second and third four-multiplier units.

2. The method of claim 1 wherein said adding comprises adding said results in general-purpose programmable logic of said programmable logic device.

3. The method of claim 2 wherein:

said performing first and second 2n-by-n multiplications comprises, for each respective one of said first and second 2n-by-n multiplications;

performing a respective most significant bit multiplication using one said multiplier in said third four-multiplier unit to form a respective most significant bit partial product, and

performing a respective least significant bit multiplication using another said multiplier in said third four-multiplier unit to form a respective least significant bit partial product;

said shifting comprises shifting each respective most significant bit partial product to the left without shifting either respective least significant bit partial product; and

said addition within said third four-multiplier unit excludes further shifting of partial products.

4. The method of claim 3 further comprising selecting control signals to perform said shifting and said addition without further shifting.

5. The method of claim 1 wherein each said specialized processing block comprises two said four-multiplier units.

6. A programmable logic device having a plurality of specialized processing blocks, each of said specialized processing blocks having at least four n-by-n multipliers arranged in four-multiplier units, said programmable logic device being configured to perform a signed 3n-by-3n multiplication operation and comprising:

four of said n-by-n multipliers in a first of said four-multiplier units configured to perform a 2n-by-2n multiplication;

one of said n-by-n multipliers in a second of said four-multiplier units configured to perform an n-by-n multiplication;

a third of said four-multiplier units configured to perform first and second 2n-by-n multiplications, using two of said n-by-n multipliers for each of said 2n-by-n multiplications;

circuitry at multiplicand inputs of at least one of said multipliers for selectably forcing at least one of said inputs to be unsigned;

a shifter configured to shift a second partial product of each of said 2n-by-n multiplications to align it with a first partial product of each of said 2n-by-n multiplications for addition within said third four-multiplier unit; and

circuitry configured to add results of said multiplications from said first, second and third four-multiplier units.

7. The configured programmable logic device of claim 6 wherein said adding comprises adding said results in general-purpose programmable logic of said programmable logic device.

8. The configured programmable logic device of claim 7 wherein:

said programmable logic device is configured to perform said first and second 2n-by-n multiplications by, for each respective one of said first and second 2n-by-n multiplications;

performing a respective most significant bit multiplication using one said multiplier in said third four-multiplier unit to form a respective most significant bit partial product, and

performing a respective least significant bit multiplication using another said multiplier in said third four-multiplier unit to form a respective least significant bit partial product;

said programmable logic device is configured to shift each respective most significant bit partial product to the left without shifting either respective least significant bit partial product; and

said circuitry configured to add excludes further shifting of partial products.

9. The configured programmable logic device of claim 8 further comprising selectors responsive to selection control signals to perform said shifting and said addition without further shifting.

10. The configured programmable logic device of claim 6 wherein each said specialized processing block comprises two said four-multiplier units.

11. The configured programmable logic device of claim 10 wherein said circuitry configured to add is located substantially within one said specialized processing block.

12. The configured programmable logic device of claim 6 wherein said circuitry for selectably forcing at least one of said inputs to be unsigned comprises a multiplexer at said multiplicand input, said multiplexer controllably selecting, for input to a sign control input associated with said multiplicand input, between a first signal forcing said multiplicand input to be unsigned, and a second signal representing sign information for said multiplicand input.

13. The configured programmable logic device of claim 6 wherein said circuitry for selectably forcing at least one of said inputs to be unsigned comprises one said multiplexer at at least one multiplicand input of each said multiplier.

14. The configured programmable logic device of claim 13 wherein said circuitry for selectably forcing at least one of said inputs to be unsigned comprises one said multiplexer at each multiplicand input of each said multiplier.

15. A data storage medium encoded with machine-executable instructions for performing a method of programmably configuring a programmable logic device to perform a signed 3n-by-3n multiplication operation, wherein said programmable logic device has a plurality of specialized processing blocks, each of said specialized processing blocks having at least four n-by-n multipliers arranged in four-multiplier units, said instructions comprising:

instructions for configuring four of said n-by-n multipliers in a first of said four-multiplier units to perform a 2n-by-2n multiplication;

instructions for configuring one of said n-by-n multipliers in a second of said four-multiplier units to perform an n-by-n multiplication;

instructions for configuring a third of said four-multiplier units to perform first and second 2n-by-n multiplications, using two of said n-by-n multipliers for each of said 2n-by-n multiplications;

instructions for configuring multiplicand inputs in any of said multiplications to be selectably treatable as signed operands or unsigned operands;

instructions for configuring a shifter to shift a second partial product of each of said 2n-by-n multiplications to align it with a first partial product of each of said 2n-by-n multiplications for addition within said third four-multiplier unit; and

instructions for configuring circuitry to add results of said multiplications from said first, second and third four-multiplier units.

16. The data storage medium of claim 15 wherein said instructions for configuring circuitry to add comprise instructions for configuring general-purpose programmable logic of said programmable logic device to add said results.

17. The data storage medium of claim 16 comprising:

instructions to configure said programmable logic device to perform said first and second 2n-by-n multiplications including, for each respective one of said first and second 2n-by-n multiplications;

instructions to configure said programmable logic device to perform a respective most significant bit multiplication using one said multiplier in said third four-multiplier unit to form a respective most significant bit partial product, and

instructions to configure said programmable logic device to perform a respective least significant bit multiplication using another said multiplier in said third four-multiplier unit to form a respective least significant bit partial product; and

instructions to configure said programmable logic device to perform to shift each respective most significant bit partial product to the left without shifting either respective least significant bit partial product;

wherein;

said instructions to configure said circuitry to add excludes further shifting of partial products.

18. The data storage medium of claim 17 wherein said instructions further comprise instructions to configure selectors responsive to selection control signals to perform said shifting and said addition without further shifting.

19. The data storage medium of claim 15 wherein said instructions are for configuring a programmable logic device wherein each said specialized processing block comprises two said four-multiplier units.

20. The data storage medium of claim 19 wherein said instructions configure said circuitry to add substantially within one said specialized processing block.

21. The data storage medium of claim 15 wherein said instructions for configuring multiplicand inputs in any of said multiplications to be selectably treatable as signed operands or unsigned operands include instructions for configuring a respective multiplexer at each respective said multiplicand input, each said respective multiplexer being configured to controllably select, for input to a sign control input associated with said respective multiplicand input, between a first signal forcing said multiplicand input to be unsigned, and a second signal representing sign information for said multiplicand input.