Implementing large multipliers in a programmable integrated circuit device

• US 8,959,137 B1
• Filed: 11/15/2012
• Issued: 02/17/2015
• Est. Priority Date: 02/20/2008
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Ngo, Chuong D
• Assistant Examiner(s): SANDIFER, MATTHEW D
• Application Number:
  US13/677,924
• Time in Patent Office: 824 Days
• Field of Search: 708/501, 708/503, 708/523, 708/620, 708625-632
• US Class Current: 708/620
• 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 specialized processing block is configurable as one ternary linear decomposition or two binary linear decompositions to perform large multiplications using smaller multipliers, and includes a first number of multiplier circuits of a first size, a second number of pre-adders, and a third number of block inputs. The block inputs are connected to a first subset of the multiplier circuits, and to the pre-adders which are connected to a second subset of the multiplier circuits. There is also a fourth number of additional inputs. A plurality of shifters shift partial product outputs of each of the multipliers by various shift amounts. A joint adder structure combines the shifted partial products. Controllable elements controllably select between different configurations of inputs to the multipliers and pre-adders, controllably connect and disconnect certain ones of the shifted partial products, and selectively split the joint adder structure into two smaller adder structures.

Claims

1. A specialized processing block for performing multiplication operations in a programmable integrated circuit device, said specialized processing block comprising:

a first number of multiplier circuits of a first size;

a second number of pre-adders;

a third number of block inputs, respective pairs of said block inputs being connected to respective ones of a first subset of said multiplier circuits, said respective pairs of said block inputs also being combined in said pre-adders and then input to a second subset of said multiplier circuits;

a fourth number of additional inputs;

a first set of controllable elements that controllably select between said additional inputs, and outputs of some of said pre-adders, for input to one of said multipliers, and that controllably select between said additional inputs, and some of said block inputs, for input to some of said pre-adders;

a plurality of shifters so that partial product outputs of each of said multipliers are shifted by one or more shift amounts to provide one or more shifted partial product outputs from each of said multipliers;

a joint adder structure for combining said shifted partial product outputs of said multipliers;

a second set of controllable elements that controllably connect and disconnect certain ones of said shifted partial products to or from said joint adder structure; and

a third controllable element for selectively splitting said joint adder structure into two smaller adder structures;

wherein;

when said third controllable element is controlled to maintain said joint adder structure as one adder structure, said second set of controllable elements connects and disconnects said certain ones of said shifted partial products to support one ternary Karatsuba decomposition of one multiplication operation; and

when said third controllable element is controlled to split said joint adder structure into said two smaller adder structures, said second set of controllable elements connects and disconnects said certain ones of said shifted partial products to support two separate binary Karatsuba decompositions of two multiplication operations using respective third and fourth subsets of said multipliers.

2. The specialized processing block of claim 1 wherein said joint adder structure comprises compressors that perform addition operations without carries and adders that perform addition operations with carries.

3. The specialized processing block of claim 1 wherein:

said first number is six;

each of said third and fourth subsets of said multipliers includes three of said multipliers;

said ternary Karatsuba decomposition performs a multiplication operation that requires nine of said multipliers in the absence of ternary Karatsuba decomposition; and

each respective one of said first and second binary Karatsuba decompositions performs a respective multiplication operation that requires four of said multipliers in the absence of binary Karatsuba decomposition.

4. The specialized processing block of claim 3 wherein when said third controllable element is controlled to split said joint adder structure into said two smaller adder structures:

said first set of controllable elements connects said third subset of said multipliers to one of said two smaller adder structures and connects said fourth subset of said multipliers to another of said two smaller adder structures;

said third subset of said multipliers includes a first group of multipliers from said first and second subsets of said multipliers, and said fourth subset of said multipliers includes a second group of multipliers from said first and second subsets of said multipliers;

said second set of controllable elements connects and disconnects said certain ones of said shifted partial products to support two separate binary Karatsuba decompositions of two multiplication operations;

said third subset of said multipliers and said one of said two smaller adder structures performs a first one of said binary Karatsuba decompositions for a first multiplication operation; and

said fourth subset of said multipliers and said another of said two smaller adder structures performs a second one of said binary Karatsuba decompositions for a second multiplication operation.

5. The specialized processing block of claim 1 wherein, when said third controllable element is controlled to split said joint adder structure into said two smaller adder structures, said first set of controllable elements selects said additional inputs for input to said one of said multipliers and for input to said some of said pre-adders.

6. The specialized processing block of claim 1 wherein said joint adder structure provides two identical but offset patterns for aligning and combining said shifted partial product outputs of said multipliers.

7. The specialized processing block of claim 6 wherein:

when said third controllable element is controlled to maintain said joint adder structure as one adder structure;

said first set of controllable elements controllably select said outputs of said some of said pre-adders for input to said one of said multipliers, and controllably select said some of said block inputs for input to said some of said pre-adders;

said joint adder structure comprises a compressor that compresses combined shifted partial product outputs of said multipliers to provide compressed vectors;

said joint adder structure further comprises first and second carry-propagate adders;

a first less significant group of bits of each of said compressed vectors is input to one of said first and second carry-propagate adders;

a second more significant group of bits of each of said compressed vectors is input to another of said first and second carry-propagate adders; and

said third controllable element connects, as a carry input to said another of said first and second carry-propagate adders, a bit from said one of said first and second carry-propagate adders corresponding to a most significant bit of said first less significant group of bits.

8. The specialized processing block of claim 1 wherein:

at least one of said multipliers is extended by 1 bit in each dimension beyond said first size.

9. A method of configuring a programmable integrated circuit device to performing multiplication operations, said programmable integrated circuit device including a specialized processing block, said specialized processing block comprising:

a first number of multiplier circuits of a first size,

a second number of pre-adders,

a third number of block inputs, respective pairs of said block inputs being connected to respective ones of a first subset of said multiplier circuits, said respective pairs of said block inputs also being combined in said pre-adders and then input to a second subset of said multiplier circuits,

a fourth number of additional inputs,

a first set of controllable elements that controllably select between said additional inputs, and outputs of some of said pre-adders, for input to one of said multipliers, and that controllably select between said additional inputs, and some of said block inputs, for input to some of said pre-adders,

a plurality of shifters so that partial product outputs of each of said multipliers are shifted by one or more shift amounts to provide one or more shifted partial product outputs from each of said multipliers,

a joint adder structure for combining said shifted partial product outputs of said multipliers,

a second set of controllable elements that controllably connect and disconnect certain ones of said shifted partial products to or from said joint adder structure, and

a third controllable element for selectively splitting said joint adder structure into two smaller adder structures, said method comprising;

configuring said first and second sets of controllable elements and said third controllable element to select between operation of said specialized processing block as a single block with said first number of multipliers to support one ternary Karatsuba decomposition of one multiplication operation, and operation of said specialized processing block as two sub-blocks each having a respective third or fourth subset of said multipliers including half said first number of multipliers, to support two separate binary Karatsuba decompositions of two multiplication operations.

10. The method of claim 9 wherein:

said first number is six;

each of said third and fourth subsets of said multipliers includes three of said multipliers;

said ternary Karatsuba decomposition performs a multiplication operation that requires nine of said multipliers in the absence of ternary Karatsuba decomposition; and

each respective one of said first and second binary Karatsuba decompositions performs a respective multiplication operation that requires four of said multipliers in the absence of binary Karatsuba decomposition.

11. The method of claim 10 further comprising, when said third controllable element is configured to split said joint adder structure into said two smaller adder structures:

configuring said first set of controllable elements to connect said third subset of said multipliers to one of said two smaller adder structures and to connect said fourth subset of said multipliers to another of said two smaller adder structures, wherein said third subset of said multipliers includes a first group of multipliers from said first and second subsets of said multipliers, and said fourth subset of said multipliers includes a second group of multipliers from said first and second subsets of said multipliers; and

configuring said second set of controllable elements to connect and disconnect said certain ones of said shifted partial products to support two separate binary Karatsuba decompositions of two multiplication operations;

wherein;

said third subset of said multipliers and said one of said two smaller adder structures performs a first one of said binary Karatsuba decompositions for a first multiplication operation; and

said fourth subset of said multipliers and said another of said two smaller adder structures performs a second one of said binary Karatsuba decompositions for a second multiplication operation.

12. The method of claim 9 further comprising, when said third controllable element is configured to split said joint adder structure into said two smaller adder structures, configuring said first set of controllable elements to select said additional inputs for input to said one of said multipliers and for input to said some of said pre-adders.

13. The method of claim 9 further comprising providing in said joint adder structure two identical but offset patterns for aligning and combining said shifted partial product outputs of said multipliers.

14. The method of claim 13 further comprising, when said third controllable element is configured to maintain said joint adder structure as one adder structure, wherein said joint adder structure comprises a compressor that compresses combined shifted partial product outputs of said multipliers to provide compressed vectors, and said joint adder structure further comprises first and second carry-propagate adders:

configuring said first set of controllable elements to select said outputs of said some of said pre-adders for input to said one of said multipliers, and to select said some of said block inputs for input to said some of said pre-adders;

configuring a first less significant group of bits of each of said compressed vectors as inputs to one of said first and second carry-propagate adders;

configuring a second more significant group of bits of each of said compressed vectors as inputs to another of said first and second carry-propagate adders; and

configuring said third controllable element to connect, as a carry input to said another of said first and second carry-propagate adders, a bit from said one of said first and second carry-propagate adders corresponding to a most significant bit of said first less significant group of bits.

15. The method of claim 9 further comprising:

extending at least one of said multipliers by 1 bit in each dimension beyond said first size.

16. A non-transitory machine-readable storage medium encoded with instructions for performing a method of configuring a programmable integrated circuit device to performing multiplication operations, said programmable integrated circuit device including a specialized processing block, said specialized processing block comprising:

a first number of multiplier circuits of a first size,

a second number of pre-adders,

a third number of block inputs, respective pairs of said block inputs being connected to respective ones of a first subset of said multiplier circuits, said respective pairs of said block inputs also being combined in said pre-adders and then input to a second subset of said multiplier circuits,

a fourth number of additional inputs,

a first set of controllable elements that controllably select between said additional inputs, and outputs of some of said pre-adders, for input to one of said multipliers, and that controllably select between said additional inputs, and some of said block inputs, for input to some of said pre-adders,

a plurality of shifters so that partial product outputs of each of said multipliers are shifted by one or more shift amounts to provide one or more shifted partial product outputs from each of said multipliers,

a joint adder structure for combining said shifted partial product outputs of said multipliers,

a second set of controllable elements that controllably connect and disconnect certain ones of said shifted partial products to or from said joint adder structure, and

a third controllable element for selectively splitting said joint adder structure into two smaller compressor and adder structures, said instructions comprising;

instructions to configure said first and second sets of controllable elements and said third controllable element to select between operation of said specialized processing block as a single block with said first number of multipliers to support one ternary Karatsuba decomposition of one multiplication operation, and operation of said specialized processing block as two sub-blocks each having a respective third or fourth subset of said multipliers including half said first number of multipliers, to support two separate binary Karatsuba decompositions of two multiplication operations.

17. The non-transitory machine-readable storage medium of claim 16 wherein:

said first number is six;

each of said third and fourth subsets of said multipliers includes three of said multipliers;

said ternary Karatsuba decomposition performs a multiplication operation that requires nine of said multipliers in the absence of ternary Karatsuba decomposition; and

each respective one of said first and second binary Karatsuba decompositions performs a respective multiplication operation that requires four of said multipliers in the absence of binary Karatsuba decomposition.

18. The non-transitory machine-readable storage medium of claim 17 wherein, when said instructions comprise instructions to configure said third controllable element to split said joint adder structure into said two smaller adder structures, said instructions further comprise:

instructions to configure said first set of controllable elements to connect said third subset of said multipliers to one of said two smaller adder structures and to connect said fourth subset of said multipliers to another of said two smaller adder structures, wherein said third subset of said multipliers includes a first group of multipliers from said first and second subsets of said multipliers, and said fourth subset of said multipliers includes a second group of multipliers from said first and second subsets of said multipliers; and

instructions to configure said second set of controllable elements to connect and disconnect said certain ones of said shifted partial products to support two separate binary Karatsuba decompositions of two multiplication operations;

wherein;

said third subset of said multipliers and said one of said two smaller adder structures performs a first one of said binary Karatsuba decompositions for a first multiplication operation; and

said fourth subset of said multipliers and said another of said two smaller adder structures performs a second one of said binary Karatsuba decompositions for a second multiplication operation.

19. The non-transitory machine-readable storage medium of claim 16 wherein:

when said instructions comprise instructions to configure said third controllable element to split said joint adder structure into said two smaller adder structures, said instructions further comprise instructions to configure said first set of controllable elements to select said additional inputs for input to said one of said multipliers and for input to said some of said pre-adders.

20. The non-transitory machine-readable storage medium of claim 16 wherein, when said instructions comprise instructions to configure said third controllable element to maintain said joint adder structure as one adder structure, wherein said joint adder structure comprises a compressor that compresses combined shifted partial product outputs of said multipliers to provide compressed vectors, and said joint adder structure further comprises first and second carry-propagate adders and provides two identical but offset patterns for aligning and combining said shifted partial product outputs of said multipliers, said instructions further comprise:

instructions to configure said first set of controllable elements to select said outputs of said some of said pre-adders for input to said one of said multipliers, and to select said some of said block inputs for input to said some of said pre-adders;

instructions to configure a first less significant group of bits of each of said compressed vectors as inputs to one of said first and second carry-propagate adders;

instructions to configure a second more significant group of bits of each of said compressed vectors as inputs to another of said first and second carry-propagate adders; and

instructions to configure said third controllable element to connect, as a carry input to said another of said first and second carry-propagate adders, a bit from said one of said first and second carry-propagate adders corresponding to a most significant bit of said first less significant group of bits.

21. The non-transitory machine-readable storage medium of claim 16 wherein said instructions further comprise instructions to extend at least one of said multipliers by 1 bit in each dimension beyond said first size.