Use of hybrid interconnect/logic circuits for multiplication

• US 7,765,249 B1
• Filed: 11/07/2005
• Issued: 07/27/2010
• Est. Priority Date: 11/07/2005
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Pugh, Daniel J., Redgrave, Jason, Schmit, Herman, Caldwell, Andrew
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US11/269,518
• Time in Patent Office: 1,723 Days
• Field of Search: 708/230, 708/232, 708/625, 326/38, 326/39
• US Class Current: 708/230
• CPC Class Codes: G06F 7/5324 partitioned, i.e. using repetitively a smaller parallel parallel multiplier or using an array of such smaller multipliers
• CPC Class Codes: H03K 19/17728 Reconfigurable logic blocks, e.g. lookup tables
• CPC Class Codes: H03K 19/17736 Structural details of routing resources

Abstract

Some embodiments of the invention provide a configurable integrated circuit (“IC”). The configurable IC includes a set of configurable logic circuits for configurably performing a set of functions on a set of inputs. The IC also includes several input select interconnect circuits for selecting the input set supplied to each configurable logic circuit. Each input select interconnect circuit is associated with a particular configurable logic circuit. When a configurable logic circuit is used to perform a multiplication operation, at least one of its associated input select interconnect circuits performs a logic operation that implements part of the multiplication operation.

Claims

1. An integrated circuit (“

IC”

) comprising;

a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs; and

a plurality of input select interconnect circuits for selecting the set of inputs supplied to each configurable logic circuit,

wherein each input select interconnect circuit is associated with a particular configurable logic circuit,

wherein for at least one particular configurable logic circuit that is used to perform a multiplication operation, at least one associated input select interconnect circuit of the particular configurable logic circuit performs a logic operation that implements part of the multiplication operation, wherein the logic operation performed by the input select interconnect circuit when it is implementing part of the multiplication operation is an AND operation.

2. The IC of claim 1 further comprising a plurality of adders and multipliers arranged in an asymmetrical tree.

3. The IC of claim 2, wherein the asymmetrical tree has multiple levels wherein no two adders appear in a same level in the asymmetrical tree.

4. The IC of claim 1 further comprising a plurality of adders and multipliers arranged in a binary tree.

5. The IC of claim 4, wherein the binary tree has multiple levels, wherein each adder in a first level receives inputs from two multipliers and each adder in subsequent levels receives inputs from up to two adders in a previous level.

6. The IC of claim 1, wherein the input select interconnect circuit that performs the logic operation is a hybrid interconnect/logic circuit.

7. The IC of claim 6, wherein the hybrid interconnect/logic circuit has a set of select lines, wherein the hybrid interconnect/logic circuit operates as an interconnect circuit when it receives only configuration data at the hybrid interconnect/logic circuit'"'"'s select lines and operates as a logic circuit when it receives at least one user design signal at one of the hybrid interconnect/logic circuit'"'"'s select lines.

8. An integrated circuit (“

IC”

) comprising;

a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs; and

a plurality of input select interconnect circuits for selecting the set of inputs supplied to each configurable logic circuit,

wherein each input select interconnect circuit is associated with a particular configurable logic circuit,

wherein for at least one particular configurable logic circuit that is used to perform a multiplication operation, at least one associated input select interconnect circuit of the particular configurable logic circuit performs a logic operation that implements part of the multiplication operation, wherein the multiplication operation is broken into a set of AND operations and a set of add operations, wherein the set of configurable logic circuits are utilized to perform the add operations and a set of input select interconnect circuits are utilized to perform the AND operations to generate a result of the multiplication operation.

9. An integrated circuit (“

IC”

) comprising;

a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs; and

a plurality of input select interconnect circuits for selecting the set of inputs supplied to each configurable logic circuit,

wherein each input select interconnect circuit is associated with a particular configurable logic circuit,

wherein for at least one particular configurable logic circuit that is used to perform a multiplication operation, at least one associated input select interconnect circuit of the particular configurable logic circuit performs a logic operation that implements part of the multiplication operation, wherein the multiplication operation is a multiplication between a first operand and a second operand, wherein the implements a first-type multiplier to perform the multiplication operation, wherein the first-type multiplier comprises a set of adders comprising a set of logic circuits and their associated input select interconnect circuits, wherein at least one input-select interconnect circuit performs an AND operation between a bit of the first operand and a bit of the second operand.

10. The IC of claim 9,

wherein one of said configurable logic circuits is a first configurable logic circuit,

wherein the first configurable logic circuit and the associated input select interconnect circuit of the first configurable logic circuit generate a least significant bit of the multiplication operation,

wherein either the associated input select interconnect circuit of the first configurable logic circuit or the first configurable logic circuit implements an AND operation.

11. The IC of claim 9, wherein each adder has a carry-in and a carry-out, wherein the adders are connected together in a chain, wherein for several of the adders in the chain the carry-out of each adder is connected to the carry-in of a next adder in the chain.

12. The IC of claim 11, wherein the carry-in of a first adder in the chain has a value of zero.

13. The IC of claim 11, wherein the carry-out of a last adder in the chain is not connected to carry-in of any adders and is used as a most significant bit of the multiplication operation.

14. The IC of claim 9, further implementing a second-type multiplier, wherein the second-type multiplier comprises:

a) a plurality of said first-type multipliers; and

b) a plurality of sets of multi-bit adders, wherein all multi-bit adders in a set have a same number of bits,

wherein each multi-bit adder in a first set shiftably adds a result of one first-type multiplier to a result of another first-type multiplier,

wherein each multi-bit adder in sets other than the first set shiftably adds a result of a multi-bit adder of a previous set to a result of another multi-bit adder in said previous set.

15. The IC of claim 9, further implementing a second-type multiplier, wherein the second-type multiplier comprises:

a) a plurality of said first-type multipliers; and

b) a plurality of multi-bit adders, wherein all multi-bit adders have a same number of bits,

wherein a first multi-bit adder shiftably adds a result of one first-type multiplier to a result of a second first-type multiplier,

wherein all other multi-bit adders shiftably add a result of one first-type multiplier to a result of a previous multi-bit adder.

16. An electronic system comprising:

an integrated circuit (“

IC”

) comprising;

i) a set of configurable logic circuits, each configurable logic circuit for configurably performing a set of functions on a set of inputs; and

ii) a plurality of input select interconnect circuits for selecting the set of inputs supplied to each configurable logic circuit,

iii) wherein each input select interconnect circuit is associated with a particular configurable logic circuit,

iv) wherein for at least one configurable logic circuit that is used to perform a multiplication operation, at least one associated input select interconnect circuit of the configurable logic circuit performs a logic operation that implements part of the multiplication operation, wherein the multiplication operation is broken into a set of AND operations and a set of add operations, wherein the set of configurable logic circuits are utilized to perform the add operations and a set of input select interconnect circuits are utilized to perform the AND operations to generate a result of the multiplication operation.

17. The electronic system of claim 16, wherein the input select interconnect circuit that performs the logic operation is a hybrid interconnect/logic circuit.

18. The electronic system of claim 17, wherein the hybrid interconnect/logic circuit has a set of select lines, wherein the hybrid interconnect/logic circuit operates as an interconnect circuit when it receives only configuration data at the hybrid interconnect/logic circuit'"'"'s select lines and operates as a logic circuit when it receives at least one user design signal at one of the hybrid interconnect/logic circuit'"'"'s select lines.

19. The electronic system of claim 16 further comprising a non-volatile memory for storing configuration data and for supplying configuration data to the IC when the IC powers up.

20. The electronic system of claim 19, wherein the non-volatile memory and the IC are on different IC dies.

21. The electronic system of claim 19, wherein the non-volatile memory and the IC are on a same IC die.