Method and apparatus for decomposing functions in a configurable IC

• US 7,530,033 B2
• Filed: 11/07/2005
• Issued: 05/05/2009
• Est. Priority Date: 03/15/2005
• Status: Expired due to Fees

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Tabula Incorporated
• Inventors: Caldwell, Andrew, Teig, Steven, Schmit, Herman
• Primary Examiner(s): DO, THUAN V
• Application Number:
  US11/269,141
• Publication Number:
  US 20070257700A1
• Time in Patent Office: 1,275 Days
• Field of Search: 716/1, 716/11, 716/12, 716/19
• US Class Current: 716/119
• 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 computer-implemented synthesis method for implementing a logic function in an integrated circuit (“

IC”

) comprising a plurality of multiplexers, the method comprising;

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

assigning a particular multiplexer that comprises a permanently inverting input terminal to perform at least one smaller logic sub-function in the IC.

2. The computer-implemented synthesis method of claim 1, wherein the particular multiplexer comprises a set of input terminals, a set of output terminals, and a set of select terminals, wherein the particular multiplexer receives input data along the input and select terminals and performs the smaller sub-function on the received input data.

3. The computer-implemented synthesis method of claim 2, wherein the particular 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 computer-implemented synthesis method of claim 1, wherein during one period of operation of the IC, the particular multiplexer receives only configuration data along a set of select terminals, while during another period of operation of the IC, the particular multiplexer receives non-configuration input, along at least one of the select terminals, on which the particular multiplexer performs the smaller logic sub-function.

5. The computer-implemented synthesis method of claim 1, wherein the decomposing comprises using Shannon decomposition to decompose the logic function.

6. The computer-implemented synthesis method of claim 1, wherein the IC comprises a plurality of logic circuits, wherein the particular multiplexer is an input select multiplexer that selects an input to a particular logic circuit.

7. The computer-implemented synthesis method of claim 6, wherein the particular logic circuit performs one of the smaller logic sub-functions.

8. A computer-implemented synthesis method for implementing a logic function in an integrated circuit (“

IC”

) comprising a plurality of multiplexers, the method comprising;

decomposing the logic function into a plurality of smaller logic sub-functions, wherein the decomposing comprises using Davio decomposition to decompose the logic function; and

assigning a particular multiplexer that comprises a permanently inverting input terminal to perform at least one smaller logic sub-function in the IC.

9. The computer-implemented synthesis method of claim 8, wherein using Davio decomposition comprises defining an XOR function, wherein using said particular multiplexer with the permanently inverting input terminal comprises using the multiplexer to perform the XOR function.

10. The computer-implemented synthesis method of claim 8, wherein using Davio decomposition comprises defining the smaller logic sub-function as a function that is equivalent to an XOR function that has at least one of a negated input, permuted input, and a negated output.

11. The computer-implemented synthesis method of claim 8, wherein the decomposing further comprises using Shannon decomposition to decompose the logic function.

12. An integrated circuit (“

IC”

) comprising;

a plurality of logic circuits;

a set of multiplexers, each multiplexer comprising a set of input terminals, a set of output terminals, and a set of select terminals;

wherein at least one input terminal of a particular multiplexer is a permanently inverting input terminal;

wherein, during a particular set of cycles during the operation of the IC, the particular multiplexer performs a particular logic sub-function on an input signal that the particular multiplexer receives along at least one of the particular multiplexer'"'"'s input terminals, said particular logic sub-function resulting from a decomposition of a particular larger logic function into a plurality of logic sub-functions; and

wherein, during the particular set of cycles, at least one of the logic circuits performs at least one of the other logic sub-functions resulting from the decomposition of the larger logic function.

13. The IC of claim 12, wherein the particular logic sub-function is an XOR function.

14. The IC of claim 12, wherein the particular logic sub-function is an equivalent of an XOR function.

15. The IC of claim 14, wherein the particular logic sub-function is an NPN equivalent of the XOR function, wherein NPN stands for negate input, permute input, negate output.

16. The IC of claim 12, wherein the particular multiplexer is a first multiplexer, the IC further comprising a second multiplexer for implementing the particular logic sub-function during the set of cycles,

wherein the second multiplexer does not use permanently inverting input terminals when implementing the particular logic sub-function.

17. An electronic device comprising:

an integrated circuit (“

IC”

) comprising;

a plurality of logic circuits; and

a set of multiplexers, each multiplexer comprising a set of input terminals, a set of output terminals, and a set of select terminals;

wherein at least one input terminal of a particular multiplexer is a permanently inverting input terminal;

wherein, during a particular set of cycles during the operation of the IC, the particular multiplexer performs a particular logic sub-function on an input signal that the particular multiplexer receives along at least one of the particular multiplexer'"'"'s input terminals, said particular logic sub-function resulting from a decomposition of a particular larger logic function into a plurality of logic sub-functions; and

wherein during the particular set of cycles, at least one of the logic circuits performs at least one of the other logic sub-functions resulting from the decomposition of the larger logic function.