Concurrent multi-bit adder

Patent metadata

Field	Value
Publication number	US-10402165-B2
Application number	US-201715690301-A
Country	US
Kind code	B2
Filing date	Aug 30, 2017
Priority date	Aug 30, 2017
Publication date	Sep 3, 2019
Grant date	Sep 3, 2019

Abstract

A system includes a non-destructive associative memory array and a predictor, a selector and a summer. The memory array includes a plurality of sections, each section includes cells arranged in rows and columns, to store bit j from a first multi-bit number and bit j from a second multi-bit number in a same column in section j. The predictor generally concurrently predicts a plurality of carry out values in each of the sections and the selector selects one of the predicted carry out values for all bits. The summer generally concurrently, for all bits, calculates a sum of the multi-bit numbers using the selected carry-out values.

First claim

What is claimed is:

1. A method for an associative memory device, the method comprising:
storing a plurality of pairs of multi-bit numbers A and B in columns of a memory array of said associative memory device, each pair of bits A j and B j in a separate section of each column;
dividing bits stored in each of said columns to groups;
in parallel in each column, first concurrently performing a ripple carry inside each group with a prediction that a value of a carry-in of all said groups is a first value, to provide first-predicted carry-out values of each bit in said groups said performing utilizing per-column Boolean operations on each said pair of bits;
in parallel in each column, second concurrently performing a ripple carry inside each group with a prediction that a value of a carry-in of all said groups is a second value to provide second-predicted carry-out values of each bit in said groups, said performing utilizing per-column Boolean operations on each said pair of bits; and
in parallel in each column, selecting one of: said first-predicted carry-out and said second-predicted carry-out, according to the actual carry-out of a previous group, to provide a final carry-out.

2. The method of claim 1 wherein a first group for said selecting is a group of least significant bits and a last group for said selecting is a group of most significant bits.

3. The method of claim 2 wherein a carry-in of a first group is one of: zero and an input.

4. The method of claim 1 also comprising:
concurrently adding together each bit j of a first number of each of said pairs, each bit j of a second number of each of said pairs and each bit j−1 of said final carry-out, used as a carry-in to bits j, thereby to produce a sum of said two multi-bit numbers.

5. The method of claim 1 wherein said first and said second performing a ripple carry comprise:
concurrently calculating and storing results of a Boolean OR operation between each bit j of a first number of each of said pairs and each bit j of a second number of each of said pairs;
concurrently calculating and storing results of a Boolean AND operation between each bit j of a first number of each of said pairs and each bit j of a second number of each of said pairs; and
concurrently using said results for said ripple caries.

6. A system comprising:
a non-destructive associative memory array comprising a plurality of sections, each section comprising cells arranged in rows and columns, to store bit j from a first multi-bit number and bit j from a second multi-bit number in a same column in section j;
a predictor, operative in parallel on said columns in said memory array, to generally concurrently predict a plurality of carry out values in each of said sections, said predictor performing per-column Boolean operations on each said pair of bits;
a selector, operative on said columns in said memory array, to select one of said predicted carry out values for all bits; and
a summer, operative on said columns in said memory array, to generally concurrently, for all bits, calculate a sum of said multi-bit numbers using said selected carry-out values.

7. The system according to claim 6 and wherein said bits of said multi-bit numbers are divided into a plurality of groups of bits.

8. The system according to claim 7 said predictor to store in a C 0 row of said memory array carry-out values produced from a prediction that a value of a carry-in to each said group is a first value and to store in a C 1 row of said memory array carry-out values produced from a prediction that a value of a carry-in to each said group is a second value.

9. The system according to claim 8 wherein said selector to store in a Cout row of said memory array, for each group a carry-out value taken from one of: row C 0 and row C 1 according to the actual carry out of a previous group.

10. The system according to claim 9 wherein said summer to store in a sum row of said memory array a sum of bit j of said two multi-bit numbers and bit j−1 of said Cout value.

Assignees

• Gsi Technology Inc

Inventors

• Lazer Moshe

Classifications

• G11C15/04

  using semiconductor elements · CPC title

• G11C7/1006

  Data managing, e.g. manipulating data before writing or reading out, data bus switches or control circuits therefor · CPC title

• G06F12/0207

  with multidimensional access, e.g. row/column, matrix · CPC title

• G06F2207/4804

  Associative memory or processor · 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