Combined associate processor and memory architecture

Details Combined associate processor and memory architecture Combined associate processor and memory architecture

2000-05-17

2002-10-15

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S165000

Reexamination Certificate

active

06467020

ABSTRACT:

FIELD AND BACKGROUND OF THE INVENTION
The present invention relates to associative processors and, more particularly, to an associative processor configured to perform two or more different arithmetical operations simultaneously and methods for loading the associative processor with data to be processed and for downloading the data after processing.
An associative processor is a device for parallel processing of a large volume of data.
FIG. 1
is a schematic illustration of a prior art 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 three registers for controlling CAM cells
14
: a tags register
20
that includes 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). 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 one row
16
via word enable line
32
, match result line
34
and a dedicated logic circuit
38
. Each mask register cell
26
and each pattern register cell
30
is associated with one column
18
. For illustrational simplicity, only three rows
16
, only one word enable line
32
, only one match result line
34
and only one logic circuit
38
are shown in FIG.
1
. 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 CAM cell
14
can perform two kinds of elementary operations, as directed by the contents of the corresponding cells
22
,
26
or
30
of registers
20
,
24
and
28
: compare operations and write operations. 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
are broadcast to the associated rows
16
as “write enable” signals by tags logic block
36
via word enable lines
32
, with rows
16
that receive a “1” bit being activated. In a single cycle of compare operations, 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 block
36
and the associated logic circuit
38
writes a “1” bit to the associated tag register cell
22
; otherwise, the associated logic block
38
writes a “0” bit to the associated tag register cell
22
. In a single cycle of write operations, 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 operation cycle 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 operation cycle 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
.
In summary, in both kinds of elementary operations, tags register
20
and mask register
24
provide activation signals and pattern register
28
provides reference bits.
Then, in a compare operation cycle, array
12
provides input to compare with the reference bits and tags register
20
receives output; and in a write operation cycle, array
12
receives output that is identical to one or more reference bits.
Tags logic block
36
also can broadcast “1”s to all rows
16
, to activate all rows
16
regardless of the contents of tags register
20
.
An additional function of tags register
20
is to provide communication between rows
16
. The results of a compare operation executed on rows
16
are stored in tags register
20
, wherein every bit corresponds to a particular row
16
. By shifting tags register
20
, 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.
Any arithmetical operation can be implemented as successive write and compare cycles. For example, to add an integer N to all the m-bit integers in an array, after the integers have been stored in m adjacent columns
18
of array
12
, with one integer per row
16
, the following operations are performed:
For each integer M that can be represented by m bits (i.e., the integers 0 through 2
m−1
):
(a) write M to the cells
30
of pattern register
28
that correspond to the m adjacent columns
18
;
(b) activate all rows
16
by broadcasting “1” to all rows
16
;
(c) execute a cycle of simultaneous compare operations with the activated CAM cells
14
to set to “1” the contents of tag register cells
22
associated with rows
16
that store M and to set to “0” the contents of all other tag register cells
22
;
(d) write M+N to the cells
30
of pattern register
28
that correspond to the m adjacent columns
18
; and
(e) execute a cycle of simultaneous write operations with the activated CAM cells
14
to write M+N to the activated rows
16
.
Associative processor
10
is well-suited to the parallel processing of data, such as digital image data, that consist of relatively short integers. For example, each pixel of an image with 256 gray levels is represented by an 8-bit integer. To add a number N to 8192 such integers in a serial processor requires 8192 add cycles. To add N to 8192 such integers in associative processor
10
requires 256 compare cycles and 256 write cycles.
More information about prior art 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.
Nevertheless, prior art associative processors such as associative processor
10
suffer from certain inefficiencies. First, rows
18
must be wide enough to accommodate all the operands of every arithmetical operation that is to be performed using the associative processor. Most arithmetical operations do not require the full width of array
12
, so most of the time, many CAM cells
14
are idle. Second, although the arithmetical operations themselves are performed in parallel, the input to array
12
and the output from array
12
must be effected serially. For example, one way to store the input m-bit integers of the above example in the m adjacent columns
18
of array
12
is as follows:
(a) Select m adjacent columns
18
of array
12
to store the input integers.
Set the contents of the corresponding mask register cells
26
to “1” and the contents of all the other mask register cells
26
to “0”.
(b) For each input integer, write the integer to the cells
30
of pattern register
28
that correspond to the selected columns
18
, activate one row
16
of array
12
by setting the contents of

Affiliated with

Also associated with

Rating

Combined associate processor and memory architecture does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Combined associate processor and memory architecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combined associate processor and memory architecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2960177