Adder circuit using lookup tables

Patent metadata

Field	Value
Publication number	US-12248764-B2
Application number	US-202418588604-A
Country	US
Kind code	B2
Filing date	Feb 27, 2024
Priority date	Dec 28, 2020
Publication date	Mar 11, 2025
Grant date	Mar 11, 2025

Abstract

A four-input lookup table (“LUT4”) is modified to operate in a first mode as an ordinary LUT4 and in a second mode as a 1-bit adder providing a sum output and a carry output. A six-input lookup table (“LUT6”) is modified to operate in a first mode as an ordinary LUT6 with a single output and in a second mode as a 2-bit adder providing a sum output and a carry output. Both possible results for the two different possible carry inputs can be determined and selected between when the carry input is available, implementing a 2-bit carry-select adder when in the second mode and retaining the ability to operate as an ordinary LUT6 in the first mode. Using the novel LUT6 design in a circuit chip fabric allows a 2-bit adder slice to be built that efficiently makes use of the LUT6 without requiring additional logic blocks.

First claim

What is claimed is:

1. A first arithmetic logic unit (ALU) slice comprising:
a plurality of lookup tables (LUTs);
input connections configured to receive as input a portion of a first operand, a portion of a second operand, a first carry-in bit from a second ALU slice, and a second carry-in bit from a third ALU slice;
a multiplexer controlled by the second carry-in bit; and
output connections configured to provide, as output, a set of sum bits and a carry-out bit, the sum bits containing a sum of the portion of the first operand, the portion of the second operand, and the first carry-in bit.

2. The first ALU slice of claim 1 , wherein the plurality of LUTs is four LUTs.

3. The first ALU slice of claim 2 , wherein the four LUTs are implemented as components of a single larger LUT.

4. The first ALU slice of claim 1 , wherein a high order bit of the sum bits is an XOR of the output of an output of a first LUT of the plurality of LUTs with the output of the multiplexer.

5. The first ALU slice of claim 1 , wherein a first LUT of the plurality of LUTs is configured to generate an output that is an XOR of a high bit of the first operand with a high bit of the second operand.

6. The first ALU slice of claim 5 , wherein a second LUT of the plurality of LUTs is configured to generate an output that is an AND of a low bit of the first operand with a low bit of the second operand.

7. The first ALU slice of claim 6 , wherein a fourth LUT of the plurality of LUTs is configured to generate an output that is an OR of:
an AND of the high bit of the first operand with the high bit of the second operand; and
an AND of:
the XOR of the high bit of the first operand with the high bit of the second operand; and
the AND of the low bit of the first operand with the low bit of the second operand.

8. The first ALU slice of claim 1 , wherein a first LUT of the plurality of LUTs is configured to generate an output that is an AND of:
a binary XOR of a low bit of the first operand with a low bit of the second operand; and
an XOR of a high bit of the first operand with a high bit of the second operand.

9. The first ALU slice of claim 8 , wherein a second LUT of the plurality of LUTs is configured to generate an output that is an exclusive or (XOR) of:
an AND of the low bit of the first operand with the low bit of the second operand; and
the XOR of the high bit of the first operand with the high bit of the second operand.

10. The first ALU slice of claim 9 , wherein a third LUT of the plurality of LUTs is configured to generate an output that is an OR of:
an AND of the high bit of the first operand with the high bit of the second operand; and
an AND of:
the XOR of the high bit of the first operand with the high bit of the second operand; and
the AND of the low bit of the first operand with the low bit of the second operand.

11. The first ALU slice of claim 1 , wherein a low order bit of the sum bits is an XOR of the output of a first LUT of the plurality of LUTs with the first carry-in bit.

12. The first ALU slice of claim 1 , wherein the input connections of the first ALU slice are further configured to receive:
a first input bit from the second ALU slice, the first input bit representing the carry-out bit of the second ALU slice if a carry input to the second ALU slice is zero; and
a second input bit from the second ALU slice, the second input bit representing the carry-out bit of the second ALU slice if the carry input to the second ALU slice is one.

13. The first ALU slice of claim 12 , wherein the first input bit and the second input bit are received by the first ALU slice before the second ALU slice receives the carry input to the second ALU slice.

14. The first ALU slice of claim 1 , wherein:
the first ALU slice is configured to provide, as the output, the set of sum bits and the carry-out bit, in a first mode of operations; and
in a second mode of operation, the first ALU slice is configured to:
provide, as output, a first output bit based on the portion of the first operand, the portion of the second operand, and an assumed value of zero for the first carry-in bit, the first output bit being provided before the first carry-in bit is received as input;
provide, as output, a second output bit based on the portion of the first operand, the portion of the second operand, and an assumed value of one for the first carry-in bit, the second output bit being provided before the first carry-in bit is received as input.

15. A computer-readable medium containing instructions that when executed by a machine, cause the machine to program a field programmable gate array (FPGA) to generate a circuit comprising:
a first arithmetic logic unit (ALU) slice comprising:
a plurality of lookup tables (LUTs);
input connections configured to receive as input a portion of a first operand, a portion of a second operand, a first carry-in bit from a second ALU slice, and a second carry-in bit from a third ALU slice;
a multiplexer controlled by the second carry-in bit; and
output connections configured to provide, as output, a set of sum bits and a carry-out bit, the sum bits containing a sum of the portion of the first operand, the portion of the second operand, and the first carry-in bit.

16. The computer-readable medium of claim 15 , wherein the plurality of LUTs is four LUTs.

17. The computer-readable medium of claim 15 , wherein:
the first ALU slice is configured to provide, as the output, the sum bits and the carry-out bit, in a first mode of operations; and
in a second mode of operation, the first ALU slice is configured to:
provide, as output, a first output bit based on the portion of the first operand, the portion of the second operand, and an assumed value of zero for the first carry-in bit, the first output bit being provided before the first carry-in bit is received as input;
provide, as output, a second output bit based on the portion of the first operand, the portion of the second operand, and an assumed value of one for the first carry-in bit, the second output bit being provided before the first carry-in bit is received as input.

18. The computer-readable medium of claim 17 , wherein the circuit further comprises one or more additional ALU slices including a highest-order ALU slice, such that the circuit generates, as an output of the highest-order ALU slice in the second mode of operation, one of the following values:
a one-bit value that is active if and only if any pair of corresponding bits in the first operand the second operand are active;
a one-bit value that is active if and only if any bit in the first operand or the second operand is active;
a one-bit value that is active if and only if no pairs of corresponding bits in the first operand and the second operand are both active;
a one-bit value that is active if and only if every bit in the first operand and the second operand is not active;
a one-bit value that is active if and only if any pair of corresponding bits in the first operand and the second operand are different; or
a one-bit value that is active if and only if the first operand and the second operand are identical.

19. A system comprising:
a memory that stores instructions; and
one or more processors configured by the instructions to perform operations comprising:
programming a field programmable gate array (FPGA) to generate a circuit comprising:
a first arithmetic logic unit (ALU) slice comprising:
a plurality of lookup tables (LUTs);
input connections configured to receive as input a

Assignees

• Achronix Semiconductor Corp

Inventors

• Lafrieda Christopher C
• Ekanayake Virantha N

Classifications

• G06F1/03

  working, at least partly, by table look-up (G06F1/025 takes precedence) · CPC title

• H03K19/21

  EXCLUSIVE-OR circuits, i.e. giving output if input signal exists at only one input; COINCIDENCE circuits, i.e. giving output only if all input signals are identical · CPC title

• H03K19/20

  characterised by logic function, e.g. AND, OR, NOR, NOT circuits (H03K19/003 - H03K19/01 take precedence) · CPC title

• G06F7/5045

  for multiple operands · CPC title

• G06F7/5057

  using table look-up; using programmable logic arrays (G06F7/509 takes precedence) · CPC title