# US 10,873,332 B2 · Adder circuitry for very large integers

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,873,332 B2
- Document ID: US10873332B2
- Status: Granted
- Kind: B2
- Application number: 16/206,748
- Filed: 2018-11-30
- Published: 2019-04-18
- Granted: 2020-12-22
- Earliest claimed: 2018-07-12
- Assignees: Intel Corporation
- Applicants: Intel Corporation
- Inventors: Martin Langhammer
- Web page: https://patentgrep.com/patent/US10873332B2

## CPC

- G06F 7/506: with simultaneous carry generation for, or propagation over, two or more stages
- G06F 7/503: 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
- G06F 7/505: in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination
- G06F 17/16: Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)}
- H03K 19/1737: {using multiplexers (H03K19/1738 takes precedence)}
- H03K 19/17724: Structural details of logic blocks
- H03K 19/17744: {for input/output signals}
- G06F 2207/4812: Multiplexers
- G06F 2207/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
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H03K: PULSE TECHNIQUE (measuring pulse characteristics G01R; modulating sinusoidal oscillations with pulses H03C; transmission of digital information H04L; discriminator circuits detecting phase difference between two signals by counting or integrating cycles of oscillation H03D3/04; automatic control, starting, synchronisation or stabilisation of generators of electronic oscillations or pulses where the type of generator is irrelevant or unspecified H03L; coding, decoding or code conversion, in general H03M)

## Abstract

An integrated circuit that includes very large adder circuitry is provided. The very large adder circuitry receives more than two inputs each of which has hundreds or thousands of bits. The very large adder circuitry includes multiple adder nodes arranged in a tree-like network. The adder nodes divide the input operands into segments, computes the sum for each segment, and computes the carry for each segment independently from the segment sums. The carries at each level in the tree are accumulated using population counters. After the last node in the tree, the segment sums can then be combined with the carries to determine the final sum output. An adder tree network implemented in this way asymptotically approaches the area and performance latency as an adder network that uses infinite speed ripple carry adders.

## Claims

### Claim 1

Adder circuitry, comprising:
a plurality of adder circuits coupled together in a tree-like arrangement having a first level with a first number of the adder circuits and a second level with a second number of the adder circuits that is less than the first number, wherein the adder circuits are configured to:
receive input signals;
separate the input signals into different segments;
compute sums for the different segments; and
compute carries for at least some of the segments, wherein the sums output from the second level are computed independently from the carries output from the first level.

### Claim 2 (depends on 1)

The adder circuitry of claim 1, wherein each of the input signals includes at least 100 bits.

### Claim 3 (depends on 1)

The adder circuitry of claim 1, wherein each of the input signals includes at least 1000 bits.

### Claim 4 (depends on 1)

The adder circuitry of claim 1, wherein each of the adder circuits is configured to separate the input signals into N different segments and is further configured to output (N−1) carries.

### Claim 5 (depends on 1)

The adder circuitry of claim 1, wherein each of the adder circuits comprises:
decoder circuits configured to output generate and propagate signals; and
a prefix network configured to receive the generate and the propagate signals from the decoder circuits and to compute the corresponding carries.

### Claim 6 (depends on 1)

The adder circuitry of claim 1, wherein the carries are computed after the sums have been computed.

### Claim 7 (depends on 1)

The adder circuitry of claim 1, further comprising counter circuits configured to tally the number of carries received from different adder circuits in the plurality of adder circuits.

### Claim 8 (depends on 1)

The adder circuitry of claim 1, wherein the plurality of adder circuits is configured to output a sum vector and a carry vector.

### Claim 9 (depends on 8)

The adder circuitry of claim 8, further comprising:
a final adder stage configured to combine the sum vector and the carry vector.

### Claim 10 (depends on 9)

The adder circuitry of claim 9, wherein the final adder stage comprises:
decoder circuits configured to output generate and propagate signals and sum signals; and
a prefix network configured to receive the generate and the propagate signals from the decoder circuits and to compute additional carry signals.

### Claim 11 (depends on 10)

The adder circuitry of claim 10, wherein the final adder stage further comprises:
adders configured to receive the additional carry signals from the prefix network and the sum signals from the decoder circuits to generate a final sum output.

### Claim 12 (depends on 10)

The adder circuitry of claim 10, wherein each of the decoder circuits includes two sub-adders and a logic gate configured to output the generate and propagate signals.

### Claim 13 (depends on 10)

The adder circuitry of claim 10, wherein each of the decoder circuits includes a single sub-adder configured to concurrently output the generate and propagate signals.

### Claim 14 (depends on 10)

The adder circuitry of claim 10, wherein at least one of the decoder circuits is configured to receive a carry element from the carry vector and a sum element from the sum vector, wherein the at least one of the decoder circuits comprises a sub-adder that receives the carry element and a first subset of the sum element, and wherein the at least one of the decoder circuits further comprises a logic gate configured to receive a carry out from the sub-adder and a second subset of the sum element that is non-overlapping with the first subset.

### Claim 15

Adder circuitry, comprising:
a tree of adder nodes, wherein a first level in the tree comprises first adder nodes configured to receive input operands, to separate the input operands into segments, and to compute sums for each of the segments in parallel, wherein the first adder nodes are further configured to output carry bits for a subset of the segments; and
counters configured to tally the total number of high carry bits output from the first adder nodes.

### Claim 16 (depends on 15)

The adder circuitry of claim 15, wherein a second level in the tree comprises:
second adder nodes configured to receive the sums from the first level, wherein the second adder nodes are further configured to output additional carry bits.

### Claim 17 (depends on 16)

The adder circuitry of claim 16, further comprising:
additional counters configured to tally the total number of high carry bits output from the second adder nodes; and
adders configured to sum together values output from the counters and the additional counters.

### Claim 18

Adder circuitry, comprising:
a first carry pipeline configured to output a first carry signal;
a second carry pipeline configured to output a second carry signal;
a first segment pipeline configured to output a first segment sum independently from the computation of the first carry signal;
a second segment pipeline configured to output a second segment sum independently from the computation of the second carry signal; and
summing circuits configured to combine the first segment sum, the second segment sum, the first carry signal, and the second carry signal to generate a final sum output.

### Claim 19 (depends on 18)

The adder circuitry of claim 18, wherein the summing circuits comprises:
decoder circuits configured to receive the first segment sum, the second segment sum, the first carry signal, and the second carry signal and to output corresponding generate and propagate signals; and
a prefix network configured to receive the generate and propagate signals from the decoder circuits, wherein the prefix network comprises a Kogge-Stone topology, a Brent-Kung topology, a Sklansky topology, or a combination thereof.

### Claim 20 (depends on 18)

The adder circuitry of claim 18, wherein the first and second pipelines comprise a tree of adder circuits having a first number of adder circuits in a first level of the tree and a second number of adder circuits in a second level of the tree, and wherein the first number of adder circuits in the first level of the tree is different than the second number of adder circuits in the second level of the tree.
