High performance FPGA addition

Patent metadata

Field	Value
Publication number	US-10340920-B1
Application number	US-201816147098-A
Country	US
Kind code	B1
Filing date	Sep 28, 2018
Priority date	Jul 12, 2018
Publication date	Jul 2, 2019
Grant date	Jul 2, 2019

Abstract

The present disclosure relates generally to techniques for enhancing adders implemented on an integrated circuit. In particular, arithmetic performed by an adder implemented to receive operands having a first precision may be restructured so that a set of sub-adders may perform the arithmetic on a respective segment of the operands. More specifically, the adder may be restructured so that a sub-adder of the set of sub-adders may concurrently output a generate signal and a propagate signal, which may both be routed to a prefix network. The prefix network may determine respective carry bit(s), which may carry into and/or select a sum at a subsequent sub-adder of the restructured adder. As a result, the integrated circuit may benefit from increased efficiencies, reduced latency, and reduced resource consumption (e.g., area and/or power) involved with implementing addition, which may improve operations such as encryption or machine learning on the integrated circuit.

First claim

What is claimed is:

1. Adder circuitry on an integrated device, the adder circuitry comprising:
input circuitry configured to receive a first input and a second input;
first arithmetic logic circuitry communicatively coupled to the input circuitry, wherein the first arithmetic logic circuitry is configured to:
determine a first sum of a first bit of the first input and a first bit of the second input; and
determine a propagate signal and a generate signal based at least in part on the first sum; and

output circuitry communicatively coupled to the first arithmetic logic circuitry, wherein the output circuitry is configured to concurrently output the generate signal, the propagate signal, and the first sum.

2. The adder circuitry of claim 1 , comprising second arithmetic logic circuitry communicatively coupled to the input circuitry, wherein the second arithmetic logic circuitry comprises propagate logic path circuitry and generate logic path circuitry, and wherein the second arithmetic logic circuitry is configured to:
determine a second sum of a second bit of the first input and a second bit of the second input;
determine an additional propagate signal and an additional generate signal based at least in part on the second sum;
route the additional propagate signal to the propagate logic path circuitry; and
route the additional generate signal to the generate logic path circuitry.

3. The adder circuitry of claim 2 , wherein the first arithmetic logic circuitry is communicatively coupled to the propagate logic path circuitry and the generate logic path circuitry, and wherein the first arithmetic logic circuitry is configured to:
receive the additional propagate signal via the propagate logic path circuitry;
receive the additional generate signal via the generate logic path circuitry;
determine the propagate signal based at least in part on the additional propagate signal; and
determine the generate signal based at least in part on the additional generate signal.

4. The adder circuitry of claim 3 , wherein the first arithmetic logic circuitry is communicatively coupled to the generate logic path circuitry via instance-based connectivity.

5. The adder circuitry of claim 1 , comprising output path circuitry communicatively coupled to the output circuitry, wherein the output path circuitry comprises a multiplexer configured to receive the first sum and one of the generate signal or the propagate signal.

6. The adder circuitry of claim 1 , comprising:
second arithmetic logic circuitry communicatively coupled to the input circuitry, wherein the second arithmetic logic circuitry is configured to:
determine a second sum of a second bit of the first input and a second bit of the second input; and
determine an additional propagate signal based at least in part on the second sum; and

additional output circuitry communicatively coupled to the second arithmetic logic circuitry, wherein the output circuitry is configured to concurrently output the additional propagate signal and the second sum.

7. The adder circuitry of claim 1 , wherein the propagate signal comprises a first portion of an additional propagate signal, wherein the first arithmetic logic circuitry is configured to receive a second portion of the additional propagate signal, and wherein the first arithmetic logic circuitry is configured to calculate the additional propagate signal based at least in part on a logical AND of the first and second portion of the additional propagate signal.

8. The adder circuitry of claim 1 , wherein the generate signal comprises a carry-out signal resulting from the first sum.

9. The adder circuitry of claim 1 , wherein the first arithmetic logic circuitry is configured to determine the propagate signal independently from the generate signal.

10. The adder circuitry of claim 1 , wherein the output circuitry comprises first output circuitry and second output circuitry, wherein the first output circuitry is configured to concurrently output a first portion of the generate signal and a first portion of the propagate signal, and wherein the second output circuitry is configured to concurrently output a second portion of the propagate signal and a second portion of the generate signal.

11. The adder circuitry of claim 1 , comprising a carry skip structure, wherein the carry skip structure comprises propagate logic path circuitry and generate logic path circuitry.

12. The adder circuitry of claim 11 , wherein the generate logic path circuitry comprises carry-chain circuitry.

13. The adder circuitry of claim 11 , wherein the propagate logic path circuitry comprises selection circuitry.

14. The adder circuitry of claim 1 , wherein the integrated device comprises a field-programmable gate array.

15. Adder circuitry on an integrated circuit device, the adder circuitry comprising:
first input circuitry configured to receive a first input having a first set of bits;
second input circuitry configured to receive a second input having a second set of bits;
first sub-adder circuitry coupled to the first input circuitry and to the second input circuitry, wherein the first sub-adder circuitry is configured to receive a first subset of the first set of bits and a first subset of the second set of bits and to concurrently determine a generate signal, a propagate signal, and a first sum of the first subset of the first set of bits and the first subset of the second set of bits based at least in part on the first subset of the first set of bits and the first subset of the second set of bits;
a prefix network coupled to the first sub-adder circuitry, wherein the prefix network is configured to determine a carry out signal based at least in part on the generate signal and the propagate signal, wherein the prefix network comprises first combinatorial circuitry; and
second combinatorial circuitry coupled to the prefix network, wherein the second combinatorial circuitry is configured to determine a portion of a second sum of the first set of bits and the second set of bits based at least in part on the carry out signal.

16. The adder circuitry of claim 15 , wherein the second combinatorial circuitry comprises second sub-adder circuitry coupled to the first sub-adder circuitry and the prefix network and configured to add the first sum and the carry out signal to determine the portion of the second sum of the first set of bits and the second set of bits.

17. The adder circuitry of claim 15 , wherein a topology of the prefix network comprises a Kogge-Stone topology, a Brent-Kung topology, a Sklansky topology, or a combination thereof.

18. The adder circuitry of claim 15 , wherein the first sub-adder circuitry is configured to determine a first portion of the propagate signal and a second portion of the propagate signal based at least in part on the first subset of the first set of bits and the first subset of the second set of bits, and wherein the first sub-adder circuitry is configured to determine the propagate signal based at least in part on the first portion of the propagate signal and the second portion of the propagate signal.

19. A tangible, non-transitory, machine-readable medium, comprising machine-readable instructions to construct adder circuitry that, when executed by one or more processors, cause the one or more processors to:
configure input circuitry to receive a first input and a second input;
configure arithmetic logic circuitry communicatively coupled to the input circuitry, wherein configuring the arithmetic logic circuitry comprises configuri

Assignees

• Intel Corp

Inventors

• Langhammer Martin
• Vanderhoek Tim Michael
• Chromczak Jeffery Christopher
• Chandler Trevis

Classifications

• H03K19/1737

  using multiplexers (H03K19/1738 takes precedence) · CPC title

• H03K19/17724

  Structural details of logic blocks · CPC title

• G06F7/503 Primary

  using carry switching, i.e. the incoming carry being connected directly, or only via an inverter, to the carry output under control of a carry propagate signal · CPC title

• G06F2207/5063

  2-input gates, i.e. only using 2-input logical gates, e.g. binary carry look-ahead, e.g. Kogge-Stone or Ladner-Fischer adder · CPC title

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title