Method and apparatus for decomposing functions in a configurable IC

• US 20070257700A1
• Filed: 11/07/2005
• Published: 11/08/2007
• Est. Priority Date: 03/15/2005
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Teig, Steven, Caldwell, Andrew, Schmit, Herman
• Granted Patent: US 7,530,033 B2
• Time in Patent Office: Days
• US Class Current: 326/38
• CPC Class Codes: G06F 30/327 Logic synthesis; Behaviour synthesis, e.g. mapping logic, HDL to netlist, high-level language to RTL or netlist
• CPC Class Codes: G06F 30/331 with hardware acceleration, e.g. by using field programmable gate array [FPGA] or emulation
• CPC Class Codes: G06F 30/34 for reconfigurable circuits, e.g. field programmable gate arrays [FPGA] or programmable logic devices [PLD]
• CPC Class Codes: G06F 30/347 Physical level, e.g. placement or routing
• CPC Class Codes: H03K 19/1737 using multiplexers H03K19/1738 takes precedence
• CPC Class Codes: H03K 19/177 arranged in matrix form

Abstract

Some embodiments of the invention provide a configurable integrated circuit (“IC”). The configurable IC includes a set of multiplexers that each has a set of input terminals, a set of output terminals, and a set of select terminals. The set of multiplexers includes a group of multiplexers, where at least one input terminal of each multiplexer in the group is a permanently inverting input terminal. During at least a set of cycles during the operation of the configurable IC, several multiplexers in the group of multiplexers are used to implement a particular function.

Claims

1. A method of implementing a function in a configurable integrated circuit (IC) with a plurality of multiplexers, the method comprising:

a) decomposing the function into a plurality of smaller sub-functions;

b) using a multiplexer with a permanently inverting input terminal to perform at least one particular smaller function.

2. The method of claim 1, wherein each multiplexer has a set of input terminals, a set of output terminals, and a set of select terminals, wherein the multiplexer receives input data along the input and select terminals and performs the particular smaller function on the received input data.

3. The method of claim 2, wherein the multiplexer further receives at least one constant value along at least one input terminal, while also receiving an input data along at least one input terminal.

4. The method of claim 1, wherein during one period of operation of the configurable IC receives only configuration data along its set of select terminals, while during another period of operation of the configurable IC receives non-configuration input data on which the multiplexer performs the particular smaller function.

5. The method of claim 1, wherein the decomposing comprises using Davio decomposition to decompose the function.

6. The method of claim 5, wherein using Davio decomposition comprises defining the particular smaller function as an XOR function.

7. The method of claim 5, wherein using Davio decomposition comprises defining the particular smaller function as a function that is equivalent to an XOR function that has at least a negated input, permuted inputs, or a negated output.

8. The method of claim 5, wherein the decomposing further comprises using Shannon decomposition to decompose the function.

9. The method of claim 1, wherein the decomposing comprises using Shannon decomposition to decompose the function.

10. The method of claim 1, wherein the configurable IC includes a plurality of logic circuits, wherein the multiplexer is an input select multiplexer that selects an input to a particular logic circuit.

11. The method of claim 10, wherein the logic circuit performs one of the smaller functions.

12. A configurable integrated circuit (“

IC”

) comprising;

a) a set of multiplexers, each with a set of input terminals, a set of output terminals, and a set of select terminals;

b) said set of multiplexers comprising a group of multiplexers, wherein at least one input terminal of each multiplexer in the group is a permanently inverting input terminal; and

c) wherein, during at least a set of cycles during the operation of the configurable IC, a plurality of multiplexers in the group of multiplexers are used to implement a particular function.

13. The configurable IC of claim 12, wherein to implement the particular function, one of the multiplexers in the group of multiplexers performs an XOR function.

14. The configurable IC of claim 12, wherein to implement the particular function, one of the multiplexers in the group of multiplexers performs a first function that is an equivalent of an XOR function.

15. The configurable IC of claim 14, wherein the first function is NPN equivalent of the XOR second function, wherein NPN stands for negate input, permute input, negate output.

16. The configurable IC of claim 12,

wherein the group of multiplexers is a first group of multiplexers;

wherein the set of multiplexers further comprises a second group of multiplexers for use during the set of cycles to implement the particular function,

wherein the multiplexers in the second group either (i) do not have any permanently inverting input terminals or (ii) have permanently inverting input terminals but do not use the permanently inverting input terminals when implementing the particular function during the set of cycles.

17. The configurable IC of claim 12, wherein the first group of multiplexers are used to perform at least one Davio decomposition that decomposes the particular function into smaller sub-functions.

18. The configurable IC of claim 17, while the second group of multiplexers are used to perform at least one Shannon decomposition that decomposes the particular function or the smaller sub-functions into other sub-functions.

19. The configurable IC of claim 12, wherein the first group of multiplexers are used to perform at least one Davio decomposition that decomposes the particular function into smaller sub-functions.

20. A configurable integrated circuit (“

IC”

) comprising;

a configurable logic circuit for configurably performing a set of functions on a set of n inputs, wherein n is a number greater than 1; and

a set of input select interconnect circuits for selecting the inputs to the configurable logic circuit;

wherein during certain operation cycles of the configurable IC, the configurable logic circuit and a group of the input select interconnect circuits from the set of input select interconnect circuits perform a particular m-input function, wherein m is a number greater than n.

21. The configurable IC of claim 20, wherein each input select interconnect circuit has a set of input terminals, a set of output terminals, and a set of select terminals, wherein the group of input select interconnect circuits receive (m-n) inputs along (m-n) select terminals.

22. The configurable IC of claim 20, wherein the group of input select interconnect circuits that perform the m-input function are hybrid interconnect/logic circuits.

23. The configurable IC of claim 22, wherein a hybrid interconnect/logic circuit operates as an interconnect circuit when it receives only configuration data at its select lines and operates as a logic circuit when it receives at least one user design signal at one of its select lines.

24. The configurable IC of claim 20, wherein at least one input select interconnect circuit in the group has a permanently inverting input.

25. The configurable IC of claim 20, wherein the configurable logic circuit and the group of input select interconnect circuits are used to decompose the m-input function into a set of function each with less than m inputs.

26. The configurable IC of claim 20 further comprising:

a plurality of configurable logic circuit for configurably performing a set of functions on a set of n inputs, wherein n is a number greater than 1; and

a particular set of input select interconnect circuits for selecting the inputs to each particular configurable logic circuit;

wherein during certain operation cycles of the configurable IC, each particular configurable logic circuit and a group of the input select interconnect circuits from the set of input select interconnect circuits for the particular configurable logic circuit perform a particular m-input function.

27. The configurable IC of claim 26 further comprising:

a plurality of configurable logic circuit for configurably performing a set of functions on a set of n inputs, wherein n is a number greater than 1; and

a particular set of input select interconnect circuits for selecting the inputs to each particular configurable logic circuit;

wherein during certain operation cycles of the configurable IC, each particular configurable logic circuits and a group of the input select interconnect circuits from the set of input select interconnect circuits for the particular configurable logic circuit perform a particular x-input function, wherein x is a number greater than n.