Concurrent multi-bit adder

Patent metadata

Field	Value
Publication number	US-10824394-B2
Application number	US-201916554730-A
Country	US
Kind code	B2
Filing date	Aug 29, 2019
Priority date	Aug 30, 2017
Publication date	Nov 3, 2020
Grant date	Nov 3, 2020

Abstract

A system includes an associative memory array and a concurrent adder. The memory array includes a plurality of sections, where each section includes cells arranged in rows and columns. The memory array stores 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 concurrent adder performs, in parallel, multi-bit add operations of P pairs of multi-bit operands stored in columns of a memory array. Each pair of the P pairs is stored in a different column of the array and each add operation occurs in its associated different column.

First claim

What is claimed is:

1. A method for an associative memory device, the method comprising:
in parallel, performing multi-bit add operations of P pairs of multi-bit operands stored in columns of a memory array,
wherein each pair of said P pairs is stored in a different column of said array and each add operation occurs in its associated different column.

2. The method of claim 1 wherein said performing comprises:
for each pair of multi-bit operands A and B, storing each pair of bits A 3 and B 3 in a separate section of each column;
dividing bits stored in each of said columns into groups;
in parallel in each column, utilizing per-column Boolean operations on each said pair of bits to provide first-predicted carry-out values and second-predicted carry-out values of each bit in said groups, given a prediction that a value of a carry-in of all said groups is a first value and a second value, respectively; 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.

3. The method of claim 2 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.

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

5. The method of claim 2 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.

6. The method of claim 2 wherein said utilizing comprises:
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.

7. 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; and
a concurrent adder to, in parallel, perform multi-bit add operations of P pairs of multi-bit operands stored in columns of a memory array,
wherein each pair of said P pairs is stored in a different column of said array and each add operation occurs in its associated different column.

8. The system according to claim 7 and wherein said concurrent adder comprises:
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.

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

10. The system according to claim 8 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.

11. The system according to claim 10 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.

12. The system according to claim 11 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

• G06F7/501

  Half or full adders, i.e. basic adder cells for one denomination · CPC title

• G06F7/507 Primary

  using selection between two conditionally calculated carry or sum values · CPC title

• G06F7/505 Primary

  in bit-parallel fashion, i.e. having a different digit-handling circuit for each denomination · CPC title

• G11C15/04

  using semiconductor elements · CPC title

• G06F2207/4804

  Associative memory or processor · CPC title