Structures for LUT-based arithmetic in PLDs

• US 8,788,550 B1
• Filed: 06/12/2009
• Issued: 07/22/2014
• Est. Priority Date: 11/26/2003
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Padalia, Ketan, Cashman, David, Lewis, David, Lee, Andy L., Kim, Henry, Schleicher, Jay, Yuan, Jinyong
• Primary Examiner(s): Ngo, Chuong D
• Application Number:
  US12/484,010
• Time in Patent Office: 1,866 Days
• Field of Search: 708/230, 708/232, 708/235, 326/41, 326/48
• US Class Current: 708/235
• CPC Class Codes: G06F 7/575 Basic arithmetic logic units, i.e. devices selectable to perform either addition, subtraction or one of several logical operations, using, at least partially, the same circuitry
• CPC Class Codes: H03K 19/177 arranged in matrix form
• CPC Class Codes: H03K 19/17728 Reconfigurable logic blocks, e.g. lookup tables

Abstract

A programmable logic device (PLD) includes a plurality of logic array blocks (LAB'"'"'s) connected by a PLD routing architecture. At least one LAB includes a logic element (LE) configurable to arithmetically combine a plurality of binary input signals in a plurality of stages. The LE comprises look-up table (LUT) logic having K inputs (a “K-LUT”). The K-LUT is configured to input the binary input signals at respective inputs of the K-LUT logic cell and to provide, at a plurality of outputs of the K-LUT logic cell, respective binary result signals indicative of at least two of the plurality of stages of the arithmetic combination of binary input signals. An input line network includes a network of input lines, the input lines configurable to receive input signals from the PLD routing architecture that represent the binary input signals and to provide the input signals to the K-LUT. An output line network includes a network of output lines, the output lines configured to receive, from the K-LUT, output signals that represent the binary result signals and to provide the output signals to the PLD routing architecture. The described LUT'"'"'s can perform arithmetic efficiently, as well as non-arithmetic functions.

Claims

1. A programmable logic device (PLD) including a plurality of logic array blocks (LAB'"'"'s) connected by a PLD routing architecture, wherein at least one LAB includes a logic element (LE) configurable to arithmetically combine a plurality of binary input signals in a plurality of stages, the LE comprising:

a K-input look-up table (LUT) (“

K-LUT”

), the K-LUT arranged to receive the plurality of binary input signals at respective inputs of the K-LUT and to provide, at a plurality of outputs of the K-LUT, respective binary result signals indicative of at least two stages of the plurality of stages of the arithmetic combination of the plurality of binary input signals;

an input line network including a network of input lines, the network of input lines arranged to receive a plurality of representative input signals from the PLD routing architecture that represent the plurality of binary input signals and to provide the plurality of binary input signals to the K-LUT, the input line network being configured to provide at least a first one of the plurality of binary input signals to both a first K-LUT portion and a second K-LUT portion in a first state, and provide a first carry-in signal to the first K-LUT portion and a second carry-in signal, which differs from the first carry-in signal, to the second K-LUT portion in a second state; and

an output line network including a network of output lines, the network of output lines arranged to receive, from the K-LUT, output signals that represent the binary result signals and to provide the network of output signals to the PLD routing architecture.

2. The PLD of claim 1, wherein:

the K-LUT includes a plurality of portions, each portion connected to the routing architecture via the input line network to receive at least some of the representative input signals; and

each portion of the plurality of portions of the K-LUT includes circuitry to generate the binary result signals indicative of a one of the plurality of stages of the arithmetic combination of the plurality of binary input signals.

3. The PLD of claim 2, wherein:

the plurality of binary input signals are provided to each portion of the plurality of portions of the K-LUT.

4. The PLD of claim 2, wherein:

the input line network includes selector circuitry operable such that,

in the first state, wherein each collection of inputs to the K-LUT that includes an input to each portion of the plurality of portions of the K-LUT receives a same particular binary input signal, and

in the second state, at least one collection of inputs to the K-LUT does not receive the particular binary input signal.

5. The PLD of claim 4, wherein:

the selector circuitry of the input line network includes a plurality of input multiplexers, wherein outputs of said plurality of input multiplexers are connected to the collection of inputs to the K-LUT, and

the plurality of input multiplexers is operable such that, in the first state, each input multiplexer of the plurality of input multiplexers provides the particular binary input signal to the output of that multiplexer and, in the second state, each of at least some of the plurality of input multiplexers provides other than the particular binary input signal to the output of such input multiplexer.

6. A programmable logic device (PLD) including a plurality of logic array blocks (LAB'"'"'s) connected by a PLD routing architecture, wherein at least one LAB includes a logic element (LE) configurable to arithmetically combine a plurality of binary input signals in a plurality of stages, the LE comprising:

a K-input look-up table (LUT) (“

K-LUT”

), the K-LUT arranged to receive the plurality of binary input signals at respective inputs of the K-LUT and to provide, at a plurality of outputs of the K-LUT, respective binary result signals indicative of the arithmetic combination of the plurality of binary input signals;

an input line network including a network of input lines, the network of input lines arranged to receive a plurality of representative input signals from the PLD routing architecture that represent the plurality of binary input signals and to provide the plurality of binary input signals to the K-LUT, the input line network being arranged to provide at least a first one of the plurality of binary input signals to both a first K-LUT portion and a second K-LUT portion in a first state, and provide a first carry-in signal to the first K-LUT portion and a second carry-in signal, which differs from the first carry-in signal, to the second K-LUT portion in a second state;

an output line network including a network of output lines, the network of output lines arranged to receive, from the K-LUT, a plurality of representative output signals that represent the binary result signals and to provide the plurality of representative output signals to the PLD routing architecture; and

at least one output multiplexer, each of the at least one output multiplexers coupled to select among the respective binary result signals directly at the outputs of the K-LUT under the control of a carry-in signal to the LE, to provide an arithmetic output signal from the LE to an output line of the output line network.

7. The PLD of claim 6, wherein:

the K-LUT includes a plurality of portions, each portion connected to the PLD routing architecture via the input line network to receive at least some of the representative input signals; and

each portion of the plurality of portions of the K-LUT includes circuitry to generate the binary result signals, which are indicative of a plurality of stages of the arithmetic combination of the plurality of binary input signals.

8. The PLD of claim 7, wherein:

the plurality of binary input signals are provided to each portion of the plurality of portions of the K-LUT.

9. The PLD of claim 7, wherein:

the input line network includes selector circuitry operable such that,

in the first state, wherein each collection of inputs to the K-LUT that includes an input to each portion of the plurality of portions of the K-LUT receives a same particular binary input signal, and

in the second state, at least one collection of inputs to the K-LUT does not receive the particular binary input signal.

10. The PLD of claim 7, wherein:

the K-LUT portions include at least a first K-LUT portion and a second K-LUT portion;

the first K-LUT portion is comprised of a first sub-portion and a second sub-portion; and

the second K-LUT portion is comprised of a third sub-portion and a fourth sub-portion,

wherein each of the-at least one output multiplexer is operable to selectively provide an output from one of the third sub-portion and the fourth sub-portion, based on signal indicative of a signal output from the second sub-portion.

11. The PLD of claim 7, wherein:

the input line network includes at least a first input multiplexer between the routing architecture and a first one of the K-LUT portions and at least a second input multiplexer between the routing architecture and a second one of the K-LUT portions.

12. A programmable logic device (PLD) including a plurality of logic array blocks (LAB'"'"'s) connected by a PLD routing architecture, wherein at least one LAB includes a logic element (LE) configurable to arithmetically combine a plurality of binary input signals in a plurality of stages, the LE comprising:

a K input look-up table (“

K-LUT”

), the K-LUT arranged to receive the plurality of binary input signals at respective inputs of the K-LUT and to provide, at a plurality of outputs of the K-LUT, respective binary result signals indicative of at least two stages of the plurality of stages of the arithmetic combination of plurality of binary input signals;

an input line network including a network of input lines and an input multiplexer, the network of input lines arranged to receive a plurality of representative input signals from the PLD routing architecture that represent the plurality of binary input signals and to provide the plurality of binary input signals to the K-LUT, wherein the input multiplexer is configured to receive input signals from at least one of the network of input lines and provide output signals to the K-LUT, the input line network being configured to provide at least a first one of the plurality of binary input signals to both a first K-LUT portion and a second K-LUT portion in a first state, and provide a first carry-in signal to the first K-LUT portion and a second carry-in signal, which differs from the first carry-in signal, to the second K-LUT portion in a second state; and

an output line network including a network of output lines and an output multiplexer, the network of output lines arranged to receive, from the K-LUT, output signals that represent the binary result signals and to provide the network of output signals to the PLD routing architecture, wherein the output multiplexer selects an output signal at outputs of the K-LUT.

13. The PLD of claim 12, wherein:

the K-LUT includes a plurality of portions, each portion connected to the routing architecture via the input line network to receive at least some of the representative input signals; and

each portion of the plurality of portions of the K-LUT includes circuitry to generate the binary result signals indicative of at least two stages of the plurality of stages of the arithmetic combination of the plurality of binary input signals.

14. The PLD of claim 13 wherein:

the plurality of binary input signals are provided to each portion of the plurality of portions of the K-LUT.

15. The PLD of claim 13, wherein:

the input line network includes selector circuitry operable such that,

in the first state, wherein each collection of inputs to the K-LUT that includes an input to each portion of the plurality of portions of the K-LUT receives a same particular binary input signal, and

in the second state, at least one collection of inputs to the K-LUT does not receive the particular binary input signal.

16. The PLD of claim 15, wherein:

the selector circuitry of the input line network includes a plurality of input multiplexers, wherein outputs of said plurality of input multiplexers are connected to the collection of inputs to the K-LUT, and

the plurality of input multiplexers is operable such that, in the first state, each input multiplexer of the plurality of input multiplexers provides the particular binary input signal to the output of that multiplexer and, in the second state, each of at least some of the plurality of input multiplexers provides other than the particular binary input signal to the output of such input multiplexer.

17. The PLD of claim 16, wherein:

the input line network includes at least a first input multiplexer between the routing architecture and the first K-LUT portion and at least a second input multiplexer between the routing architecture and the second K-LUT portion;

the input line network is operable to

in the first state, provide at least the first one of the input signals to both the first K-LUT portion and the second K-LUT portion, via the first input multiplexer and the second input multiplexer, respectively, and

in the second state, instead provide the first carry-in signal to the first K-LUT portion and the second carry-in signal to the second K-LUT portion, via the first input multiplexer and the second input multiplexer, respectively.

18. The PLD of claim 17, wherein:

the K-LUT portions include at least a first K-LUT portion and a second K-LUT portion;

the output line network includes at least a first output multiplexer, controlled by a second one of the plurality of binary input signals, and at least a second output multiplexer, controlled by the second binary input signal,

the first K-LUT portion is comprised of a first sub-portion and a second sub-portion;

the second K-LUT portion is comprised of a third sub-portion and a fourth sub-portion;

the first output multiplexer selects between the output of the first sub-portion and the second sub-portion; and

the second output multiplexer selects between the output of the third sub-portion and the fourth sub-portion.

19. The PLD of claim 18, wherein:

each of the first K-LUT portion and the second K-LUT portion is a K-1 LUT.

20. The PLD of claim 19, wherein:

each of the first sub-portion, the second sub-portion, the third sub-portion and the fourth sub-portion is a K-2 LUT.