Large multiplier for programmable logic device

• US 7,930,336 B2
• Filed: 12/05/2006
• Issued: 04/19/2011
• 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:
  US11/566,982
• Publication Number:
  US 20080133627A1
• Time in Patent Office: 1,596 Days
• Field of Search: 708/620, 708/625
• US Class Current: 708/620
• CPC Class Codes: G06F 7/52 Multiplying; Dividing G06F7/483 - G06F7/491, G06F7/544 take precedence
• 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.

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 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;

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;

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. The method of claim 5 wherein said adding comprises performing said adding substantially in one said specialized processing block.

7. The method of claim 6 wherein:

both said 2n-by-2n multiplication and said first and second 2n-by-n multiplications are performed in said one specialized processing block comprising said first and third four-multiplier units;

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

performing a most significant bit multiplication for said 2n-by-2n multiplication using one said multiplier in said first four-multiplier unit to form a most significant bit partial product for said 2n-by-2n multiplication, and performing a respective most significant bit multiplication for each respective one of said 2n-by-n multiplications using a respective one of said multipliers in said third four-multiplier unit to form a respective most significant bit partial product for each respective one of said 2n-by-n multiplications, and

performing a least significant bit multiplication for said 2n-by-2n multiplication using another said multiplier in said first four-multiplier unit to form a least significant bit partial product for said 2n-by-2n multiplication, and performing a respective least significant bit multiplication for each respective one of said 2n-by-n multiplications using respective others of said multipliers in said third four-multiplier unit to form a respective least significant bit partial product for each respective one of said 2n-by-n multiplications; and

said shifting comprises shifting each respective one of said most significant bit partial products of said 2n-by-n multiplications to the left without shifting either respective one of said least significant bit partial products of said 2n-by-n multiplications;

said method further comprising;

shifting said most significant bit partial product of said 2n-by-2n multiplication to the left without shifting said least significant bit partial product of said 2n-by-2n multiplication;

summing said most significant and least significant bit partial products of said 2n-by-2n multiplication to produce a most significant bit sum and a least significant bit sum of said 2n-by-2n partial products of said 2n-by-2n multiplication;

summing each pair of respective most significant and least significant bit partial products of said 2n-by-n multiplications to produce a respective most significant bit sum and least significant bit sum for each of said 2n-by-n multiplications;

left-shifting said most significant bit sum of said 2n-by-2n partial products of said 2n-by-2n multiplication;

right-shifting each of said most significant bit sum of said 2n-by-n partial products and said least significant bit sum of said 2n-by-n partial products;

right-shifting output of said n-by-n multiplication and inputting said right-shifted output to said one of said specialized processor blocks comprising said first and third four-multiplier units; and

adding said left-shifted most significant bit sum of said 2n-by-2n partial products, said right-shifted most and least significant bit sums of said 2n-by-n partial products, said right-shifted output of said n-by-n multiplication, and said least significant bit sum of said 2n-by-2n partial products.

8. The method of claim 7 wherein adding said left-shifted most significant bit sum of said 2n-by-2n partial products, said right-shifted most and least significant bit sums of said 2n-by-n partial products, said right-shifted output of said n-by-n multiplication, and said least significant bit sum of said 2n-by-2n partial products comprises:

compressing said least significant bit sum of said 2n-by-2n partial products;

compressing said left-shifted most significant bit sum of said 2n-by-2n partial products with a first one of said right-shifted most and least significant bit sums of said 2n-by-n partial products;

compressing said right-shifted output of said n-by-n multiplication with a second one of said right-shifted most and least significant bit sums of said 2n-by-n partial products; and

adding results of said compressings.

9. 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 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;

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.

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

11. The configured programmable logic device of claim 10 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.

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

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

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

15. The configured programmable logic device of claim 14 wherein:

said one specialized processing block comprises both said first four-multiplier unit configured to perform said 2n-by-2n multiplication and said third four-multiplier unit configured to perform said first and second 2n-by-n multiplications;

in each of said first and third four-multiplier units, said performing said 2n-by-2n multiplication and first and second 2n-by-n multiplications comprises, for each respective one of said 2n-by-2n multiplication and first and second 2n-by-n multiplications;

performing a most significant bit multiplication for said 2n-by-2n multiplication using one said multiplier in said first four-multiplier unit to form a most significant bit partial product for said 2n-by-2n multiplication, and performing a respective most significant bit multiplication for each respective one of said 2n-by-n multiplications using a respective one of said multipliers in said third four-multiplier unit to form a respective most significant bit partial product for each respective one of said 2n-by-n multiplications, and

performing a least significant bit multiplication for said 2n-by-2n multiplication using another said multiplier in said first four-multiplier unit to form a least significant bit partial product for said 2n-by-2n multiplication, and performing a respective least significant bit multiplication for each respective one of said 2n-by-n multiplications using respective others of said multipliers in said third four-multiplier unit to form a respective least significant bit partial product for each respective one of said 2n-by-n multiplications; and

said shifter is configured to shift each respective one of said most significant bit partial products of said 2n-by-n multiplications to the left without shifting either respective one of said least significant bit partial products of said 2n-by-n multiplications;

said configured programmable logic device further comprising;

a shifter to shift said most significant bit partial product of said 2n-by-2n multiplication to the left without shifting said least significant bit partial product of said 2n-by-2n multiplication;

circuitry configured to sum said most significant and least significant bit partial products of said 2n-by-2n multiplication to produce a most significant bit sum and a least significant bit sum of said 2n-by-2n partial products of said 2n-by-2n multiplication;

circuitry configured to sum each pair of respective most significant and least significant bit partial products of said 2n-by-n multiplications to produce a respective most significant bit sum and least significant bit sum for each of said 2n-by-n multiplications;

first left-shifting circuitry to left-shift said most significant bit sum of said 2n-by-2n partial products of said 2n-by-2n multiplication;

right-shifting circuitry to right-shift said most significant bit sum of said 2n-by-n partial products and said least significant bit sum of said 2n-by-n partial products;

second right-shifting circuitry to right-shift output of said n-by-n multiplication and input said right-shifted output of said n-by-n multiplication to said one of said specialized processor blocks comprising said first and third four-multiplier units; and

circuitry configured to add said left-shifted most significant bit sum of said 2n-by-2n partial products, said right-shifted most and least significant bit sums of said 2n-by-n partial products, said right-shifted output of said n-by-n multiplication, and said least significant bit sum of said 2n-by-2n partial products.

16. The configured programmable logic device of claim 15 wherein circuitry configured to add said left-shifted most significant bit sum of said 2n-by-2n partial products, said right-shifted most and least significant bit sums of said 2n-by-n partial products, said left-shifted output of said n-by-n multiplication, and said least significant bit sum of said 2n-by-2n partial products comprises:

first 3;

2 compression circuitry to compress said least significant bit sum of said 2n-by-2n partial products;

4;

2 compression circuitry to compress said left-shifted most significant bit sum of said 2n-by-2n partial products with a first one of said right-shifted most and least significant bit sums of said 2n-by-n partial products;

second 3;

2 compression circuitry to compress said right-shifted output of said n-by-n multiplication with a second one of said right-shifted most and least significant bit sums of said 2n-by-n partial products; and

adding circuitry to add outputs of said first and second 3;

2 compression circuitry and said 4;

2 compression circuitry.

17. A data storage medium encoded with machine-executable instructions for performing a method of programmably configuring a programmable logic device to perform a 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 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.

18. The data storage medium of claim 17 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.

19. The data storage medium of claim 18 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.

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

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

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

23. The data storage medium of claim 22 wherein:

said instructions configure both said first and third four-multiplier units configured to perform said 2n-by-2n multiplication and said first and second 2n-by-n multiplications;

said instructions configure each of said first and third four-multiplier units to perform said 2n-by-2n multiplication and first and second 2n-by-n multiplications comprises, wherein, for each respective one of said 2n-by-2n multiplication and first and second 2n-by-n multiplications;

said instructions configure one said multiplier in said four-multiplier unit to perform a most significant bit multiplication for said 2n-by-2n multiplication to form a respective most significant bit partial product for said 2n-by-2n multiplication, and configure a respective one of said multipliers in said third four-multiplier unit to perform a respective most significant bit multiplication for each respective one of said 2n-by-n multiplications to form a respective most significant bit partial product for each respective one of said 2n-by-n multiplications, and

said instructions configure another said multiplier in said four-multiplier unit to perform a least significant bit multiplication for said 2n-by-2n multiplication to form a respective least significant bit partial product for said 2n-by-2n multiplication, and configure respective others of said multipliers in said third four-multiplier unit to perform a respective least significant bit multiplication for each respective one of said 2n-by-n multiplications to form a respective least significant bit partial product for each respective one of said 2n-by-n multiplications; and

said instructions configure said shifter to shift each respective one of said most significant bit partial products of said 2n-by-n multiplications to the left without shifting either respective one of said least significant bit partial products of said 2n-by-n multiplications;

said instructions configure a shifter to shift said most significant bit partial product of said 2n-by-2n multiplication to the left without shifting said least significant bit partial product of said 2n-by-2n multiplication;

said instructions configure circuitry to sum said most significant and least significant bit partial products of said 2n-by-2n multiplication to produce a most significant bit sum and a least significant bit sum of said 2n-by-2n partial products of said 2n-by-2n multiplication;

said instructions configure circuitry to sum each pair of respective most significant and least significant bit partial products of said 2n-by-n multiplications to produce a respective most significant bit sum and least significant bit sum of said 2n-by-n multiplications;

said instructions configure first left-shifting circuitry to left-shift said most significant bit sum of said 2n-by-2n partial products of said 2n-by-2n multiplication;

said instructions configure right-shifting circuitry to right-shift said most significant bit sum of said 2n-by-n partial products and said least significant bit sum of said 2n-by-n partial products;

said instructions configure second right-shifting circuitry to right-shift output of said n-by-n multiplication and input said right-shifted output of said n-by-n multiplication to said one of said specialized processor blocks comprising said first and third four-multiplier units; and

said instructions configure circuitry to add said left-shifted most significant bit sum of said 2n-by-2n partial products, said right-shifted most and said least significant bit sums of said 2n-by-n partial products, said right-shifted output of said n-by-n multiplication, and said least significant bit sum of said 2n-by-2n partial products.

24. The data storage medium of claim 23 wherein said instructions to configure circuitry configured to add said left-shifted most significant bit sum of said 2n-by-2n partial products, said right-shifted most and said least significant bit sums of said 2n-by-n partial products, said right-shifted output of said n-by-n multiplication, and said least significant bit sum of said 2n-by-2n partial products comprises:

instructions to configure first 3;

2 compression circuitry to compress said least significant bit sum of said 2n-by-2n partial products;

instructions to configure 4;

2 compression circuitry to compress said left-shifted most significant bit sum of said 2n-by-2n partial products with a first one of said right-shifted most and said least significant bit sums of said 2n-by-n partial products;

instructions to configure second 3;

2compression circuitry to compress said right-shifted output of said n-by-n multiplication with a second one of said right-shifted most and said least significant bit sums of said 2n-by-n partial products; and

instructions to configure adding circuitry to add outputs of said first and second 3;

2 compression circuitry and said 4;

2 compression circuitry.