Concurrent multi-bit adder
AssigneeGSI Technology, Inc.
InventorMoshe Lazer
Life of this patent
Estimating the term…
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.
Claims10
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 Aj and Bj 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.
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.
Dependencies are inferred from the claim text.