System and method for long addition and long multiplication in associative memory

Patent metadata

Field	Value
Publication number	US-10635397-B2
Application number	US-201815915113-A
Country	US
Kind code	B2
Filing date	Mar 8, 2018
Priority date	Mar 8, 2018
Publication date	Apr 28, 2020
Grant date	Apr 28, 2020

Abstract

A method for an associative memory device includes replacing a set of three multi-bit binary numbers P, Q and R, stored in the associative memory device, with two multi-bit binary numbers X and Y, also stored in the associative memory device, wherein a sum of the binary numbers P, Q and R is equal to a sum of the binary numbers X and Y. A system includes an associative memory array having rows and columns and a multi-bit multiplier. Each column of the array stores two multi-bit binary numbers to be multiplied. The multi-bit multiplier multiplies, in parallel, the two multi-bit binary numbers per column by concurrently processing all bits of partial products generated by the multiplier. The multiplier performs the processing without any carry propagation delay when adding all but the last two partial products.

First claim

What is claimed is:

1. A method for an associative memory device, the method comprising:
replacing a set of three multi-bit binary numbers P, Q and R, stored in said associative memory device, with two multi-bit binary numbers X and Y, also stored in said associative memory device, wherein a sum of said binary numbers P, Q and R is equal to a sum of said binary numbers X and Y.

2. The method of claim 1 and also comprising having a plurality of sets i of three multi-bit binary numbers P i , Q i and R i and concurrently performing said replacing on said plurality of sets i.

3. The method of claim 1 wherein said replacing comprises:
concurrently, for each location j of binary numbers P, Q and R, placing a first bit in a location j of said binary number X and a second bit in a location k of said binary number Y, said first bit being a sum bit and said second bit being a carry bit according to a full adder truth table, and said location k representing a value greater by a power of two than the value in location j.

4. The method of claim 1 and also comprising:
having n multi-bit binary addends;
repeatedly performing said replacing on sets of three of said multi-bit binary addends until there are only two final multi bit binary addends left; and
performing a standard multi bit add operation on said final two multi bit binary addends providing a sum of said n multi-bit binary addends.

5. The method of claim 1 and also comprising:
having two multi-bit binary numbers to be multiplied;
initially putting bits of a first partial product of said two multi-bit binary numbers into said binary number P and bits of a second partial product into said binary number Q;
placing bits of a next partial product in said binary number R;
performing said replacing;
putting bits of said multi-bit binary number X into said multi-bit binary number P and bits of said multi-bit binary number Y into said multi-bit binary number Q;
repeating said placing, performing and putting until said next partial product is a last partial product; and
performing a standard multi bit add operation on said multi-bit binary numbers P and Q thereby providing a result of a multiplication operation between said two multi-bit binary numbers.

6. The method of claim 5 wherein said first performing comprises:
placing a most significant bit (MSB) of said multi-bit binary number R in a temporary location in said associative memory device;
storing a least significant bit (LSB) of said multi-bit binary number P in a first free location of said result, starting from the LSB of said result; and
placing a bit from said temporary location as an MSB of said multi-bit binary number P, thereby keeping a constant number of bits in each of said multi-bit binary numbers P, Q and R.

7. A system comprising:
an associative memory array arranged in rows and columns storing three original multi-bit binary numbers P, Q and R in each column of said associative memory array; and
a 3to2 replacer to concurrently replace, in parallel in all columns said original multi-bit binary numbers P, Q and R with two replacement multi-bit binary numbers X and Y wherein a sum of said original multi-bit binary numbers P, Q and R is equal to a sum of said replacement multi-bit binary numbers X and Y.

8. The system of claim 7 wherein concurrently for each bit j of multi-bit binary numbers P, Q and R stored in each column, said 3to2 replacer to place a first bit in a location j of said multi-bit binary number X and a second bit in a location k of said multi-bit binary number Y, wherein said first bit is a sum bit and said second bit is a carry bit according to a full adder truth table, and said location k to store a value greater by a power of two than the value stored in location j.

9. The system of claim 7 said associative memory array to store a plurality of multi-bit binary addends and said system also comprising:
a variable reducer to repeatedly activate said 3to2 replacer on groups of three multi-bit binary numbers, wherein each group comprises a first, a second and a third multi-bit binary addend from said plurality of multi-bit binary addends, until there are only two final multi bit binary addends left; and
a multi-bit adder to calculate a sum of said final two multi bit binary addends thereby to provide a sum of said plurality of multi-bit binary addends.

10. The system of claim 9 said associative memory array to store a pair of multi-bit binary numbers to be multiplied and also comprising
a multi-bit multiplier to generate partial products of said pair, to activate said variable reducer on said partial products and to activate said multi bit adder to provide a multiplication result between said pair.

11. A system comprising:
An associative memory array having rows and columns, each column of said array to store two multi-bit binary numbers to be multiplied; and
a multi-bit multiplier to multiply, in parallel, said two multi-bit binary numbers per column by concurrently processing all bits of partial products generated by said multiplier, said multiplier performing said processing without any carry propagation delay when adding all but the last two partial products.

12. A method comprising:
multiplying, in parallel, a pair of multi-bit binary numbers stored in a column of an associative memory array, said multiplying comprising:
generating partial products of said pair; and
repeatedly performing a 3to2 replacement of said partial products.

Assignees

• Gsi Technology Inc

Inventors

• Lazer Moshe

Classifications

• G06F7/533 Primary

  Reduction of the number of iteration steps or stages, e.g. using the Booth algorithm, log-sum, odd-even · CPC title

• G06F7/501

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

• G06F7/523

  Multiplying only · CPC title

• G06F7/5318

  with column wise addition of partial products, e.g. using Wallace tree, Dadda counters (G06F7/5324 takes precedence) · CPC title

• G06F7/5312 Primary

  using carry save adders · CPC title