Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2002-03-29
2004-06-29
Malzahn, David H. (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S670000
Reexamination Certificate
active
06757703
ABSTRACT:
FIELD AND BACKGROUND OF THE INVENTION
The present invention relates to associative processors and, more particularly, to a method of adding and subtracting numbers stored in the associative array of an associative processor.
An associative processor is a device for parallel processing of a large volume of data.
FIG. 1
is a schematic illustration of an associative processor
10
. The heart of associative processor
10
is an array
12
of content addressable memory (CAM) cells
14
arranged in rows
16
and columns
18
. Associative processor
10
also includes four registers for controlling CAM cells
14
: two tags registers
20
a
and
20
b
that include many tag register cells
22
, a mask register
24
that includes many mask register cells
26
, and a pattern register
28
that includes many pattern register cells
30
. Each cell
14
,
22
,
26
or
30
is capable of storing one bit (0 or 1). Each tags register
20
is a part of a tags logic block
36
that communicates with each row
16
via a dedicated word enable line
32
and a dedicated match result line
34
, with each tag register cell
22
being associated with a respective row
16
via word enable line
32
, match result line
34
and a dedicated logic unit
38
. Each mask register cell
26
and each pattern register cell
30
is associated with a respective column
18
. For illustrational simplicity, only three rows
16
, only one word enable line
32
, only one match result line
34
and only two logic units
38
are shown in FIG.
1
. Note that the two tag register cells
22
that are associated with the same row
16
share the same word enable line
32
and the same match result line
34
. Typical arrays
12
include 8192 (2
13
) rows
16
. The array
12
illustrated in
FIG. 1
includes 32 columns
18
. More typically, array
12
includes 96 or more columns
18
.
Each machine cycle of associative processor
10
is either a compare cycle or a write cycle. Correspondingly, in a single machine cycle of associative processor
10
, each CAM cell
14
performs one and only one of two kinds of elementary operations, as directed by the contents of the corresponding cells
22
,
26
or
30
of registers
20
a
,
20
b
,
24
and
28
: either a compare operation or a write operation. For both kinds of elementary operations, columns
18
that are to be active are designated by the presence of “1” bits in the associated mask register cells
26
. The contents of tag register cells
22
of one of tags logic blocks
36
are broadcast to the associated rows
16
as “write enable” signals by that tags logic block
36
via word enable lines
32
, with rows
16
that receive a “1” bit being activated. In a compare cycle, each activated row
16
generates a “1” bit match signal on match result line
34
of that row
16
. Each activated CAM cell
14
of that row
16
compares its contents with the contents of the cell
30
of pattern register
28
that is associated with the column
18
of that CAM cell
14
. If the two contents are identical (both “0” bits or both “1” bits), that CAM cell
14
allows the match signal to pass. Otherwise, that CAM cell
14
blocks the match signal. As a result, if the contents of all the activated CAM cells
14
of a row
16
match the contents of corresponding cells
30
of pattern register
28
, the match signal reaches tags logic blocks
36
. In a write cycle, the contents of pattern register cells
30
associated with activated columns
18
are written to the activated CAM cells
14
of those columns
18
.
In the example illustrated in
FIG. 1
, the fifth through eighth columns
18
from the right are activated by the presence of “1” s in the corresponding mask register cells
26
. A binary “4” (0100) is stored in the corresponding pattern register cells
30
. A compare cycle performed by associative processor
10
in this configuration tests activated rows
16
to see if a binary “4” is stored in their fifth through eighth CAM cells
14
from the right. A write cycle performed by associative processor
10
in this configuration writes binary “4” to the fifth through eighth CAM cells
14
from the right of activated rows
16
.
Each logic unit
38
can be configured to perform, in a single machine cycle, one or more of several logical operations (AND, OR, NOT, XOR, identity) whose inputs are one or more of: the bit stored in the associated tag register cell
22
, the bit stored in the corresponding tag register cell
22
in the other tags logic block
36
, and, if the cycle is a compare cycle, the presence or absence of a match signal on match result line
34
. The AND, OR and XOR operations are binary operations (two inputs). The NOT and identity operations are unary operations (one input). The presence of a match signal on match result line
34
is treated as a binary “1”. The absence of a match signal on match result line
34
is treated as a binary “0”. The result of the logical operation is a single bit that is stored in the associated tag register cell
22
. In the simplest set of logical operations, in a compare cycle, the only input is the presence or absence of a match signal on match result line
34
and the sole logical operation is an identity operation. The result of this operation is the writing to the associated tag register cell
22
of the bit corresponding to the presence or absence of a match signal on match result line
34
.
In summary, in both kinds of elementary operations, tags register
20
a
or
20
b
and mask register
24
provide activation signals and pattern register
28
provides reference bits. Then, in a compare cycle, array
12
provides input to compare with the reference bits and tags registers
20
a
and
20
b
receive output; and in a write cycle, array
12
receives output that is identical to one or more reference bits.
Tags logic blocks
36
a
and
36
b
also can broadcast “1” s to all rows
16
, to activate all rows
16
regardless of the contents of tags registers
20
.
An additional function of tags registers
20
is to provide communication between rows
16
. For example, suppose that the results of a compare operation executed on rows
16
have been stored in tags register
20
a
, wherein every bit corresponds to a particular row
16
. By shifting tags register
20
a
, the results of this compare operation are communicated from their source rows
16
to other, target rows
16
. In a single tags shift operation the compare result of every source row
16
is communicated to a corresponding target row
16
, the distance between any source row
16
and the corresponding target row
16
being the distance of the shift.
More information about associative processors may be found in U.S. Pat. No. 5,974,521, to Akerib, which is incorporated by reference for all purposes as if fully set forth herein.
A prior art method of adding a first set of N binary numbers {a
n
, n=1 . . . N}, stored in a first set of columns
18
, to another set of N binary numbers {b
n
, n=1 . . . N}, stored in a second set of columns
18
, and storing the resulting N binary numbers {s
n
, n=1 . . . N} in a third set of columns
18
, is taught by Daniel P. Sieworek et al. in Computer Structures: Principles and Examples, Chapter 21: “A productive implementation of an associative array processor: STARAN 319”, McGraw-Hill, New York (1982), also available at the URL
http://www.ulib.org/webRoot/Books/Saving_Bell_Books/SBN%20Computer%20Strucutres/csp0336.htm.
Without loss of generality, all the input numbers {a
n
} and {b
n
} can be assumed to have the same number of bits, because any number that is shorter than the longest input number can be left-padded with “0” bits. For any particular index n, a
n
and b
n
are initially stored in the same row
16
, in different sets of respective columns, and s
n
is to be stored in the same row
16
, typically in its own set of columns, although either a
n
or b
n
can be partly or completely overwritten with s
n
because once a bit of s
n
is computed, the bits of a
n
and b
n
th
Friedman Mark M.
Malzahn David H.
Neomagic Israel Ltd.
LandOfFree
Associative processor addition and subtraction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Associative processor addition and subtraction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Associative processor addition and subtraction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3328526