Sequentially comparing content addressable memory

Details Sequentially comparing content addressable memory Sequentially comparing content addressable memory

1998-11-30

2001-04-10

Nguyen, Tan T. (Department: 2818)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C711S108000

Reexamination Certificate

active

06215685

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The present invention relates generally to computer memories, and more particularly to a memory cache configuration and a method of searching the cache for matches.
BACKGROUND OF THE INVENTION
“Content-addressable memories” (CAMS) are used in memory cache systems. They perform a matching process that determines whether the cache contains data needed elsewhere in the system, such as data requested a processor.
With a general purpose computer that uses a CAM, as with all cache systems, when a processor identifies the data it needs, the CAM must check its memory to determine if the identified data is located in the CAM. In other words, it determines whether the data is a cache entry or whether it is stored only in main (non-cache) memory. With the CAM approach, this checking process is performed. by storing “tags”, each of which may be part of the address of each cache entry, in the CAM. The CAM compares each tag to a “target tag” issued by the processor. If there is a match, the data is located in the CAM. If not, the data is fetched from main memory.
Conventional CAMs simultaneously compare the target tag to every bit of all tags. They accomplish this comparison by using special tag memory cells (“tag cells”). Each tag cell is like a conventional RAM cell, with an associated bitline and wordline and data storage components, but also has a comparator. The comparator compares a signal on a bitline to the cell's contents and places the result on a readline. The comparators of all cells in the CAM are turned on at once so that each cell may perform its comparison at the same time as all other cells.
FIG. 1
illustrates a prior art CAM
100
that has a comparator (switches
107
and
108
) for each tag cell
102
. Bitlines
101
carry consecutive bits of the target tag (and the complementary bits) simultaneously to the cells
102
. Each bit of the target tag is compared to the contents of the cells
102
as indicated by the state of a pair of inverters
104
. Each row of cells
102
has an associated matchline
103
, which is precharged to Vcc. Switches
105
are activated by wordlines
106
. A pair of series-connected switching transistors
107
and
108
are controlled by the output of each inverter
104
. Switching transistors
107
and
108
connect matchline
103
to ground and must both be activated to discharge matchline
103
. This discharge will occur only when the cell contents do not match the target tag bit on the bitline. Thus, for each row, the matchline
103
goes low when there is a mismatch. If the matchline of any row remains at Vcc, a match on that row is indicated. An OR gate (not shown) may be used to provide a global hit signal from the CAM
100
.
This conventional method of configuring and simultaneously comparing contents of tag cells of a CAM is costly in terms of die area and the resulting current spike in the power supply. For CAMs that store a large number of entries, such as those used in packet communication systems, the current spikes can cause problems.
SUMMARY OF THE INVENTION
One aspect of the invention is a content addressable memory (CAM) that stores tags and data associated with each tag and sequentially compares the tags to a target tag. The CAM comprises an array of tag cells and an array of data cells. Each tag cell has appropriate memory storage components for storing a bit of data and also has a multiplexing switch whose output is a signal representing the state of the bit stored in the cell. A bit-select line connects each column of tag cells and a readline connects each row of tag cells. A tag compare circuit is external to the tag cells. Any bit-select line can be activated to turn on the multiplexing switches in a column of the array. Then, the tag compare circuit compares the bits in the cells of that column to a bit of the target tag. As each bit of the target tag is compared to successive columns of tag cell outputs, the tag compare circuit maintains readline outputs that each indicate whether the comparisons for cells on a row so far indicate a match or a mismatch. These readline outputs can be tied to each other to provide a “hit” signal. Advantages of the invention are that the area of each tag cell, and hence the size of the CAM, are reduced. This is due to the fact that each tag cell has only a multiplexing switch (one or two transistors) at its output rather than a comparator. When an array of such cells is considered, the area savings is significant.
The CAM also reduces current spikes. At any one time, only one bit of the target address is compared to bits from a column of tag cells.
A further advantage is that the CAM may be easily programmed to accommodate target tags having varying lengths. Thus, for shorter target tags, the CAM may be programmed in a manner that requires less time to determine if there is a match.
The above features are especially attractive for CAMs used for packet switching, such as asynchronous transfer mode (ATM) switches. These switches perform address substitutions, using CAMs that have a large number of addresses, typically 1 K or more. In such CAMs, the array size and current spikes associated with conventional CAMs are an even greater problem than with smaller CAMs.
The programmability aspect of the invention may be extended to partitioning the CAM into sections that may be disabled or enabled during tag matching. This permits users to further reduce power and increase speed as dictated by the sections of the CAM that are actually being used.


REFERENCES:
patent: 4622653 (1986-11-01), McElroy
patent: 5359564 (1994-10-01), Liu et al.
patent: 5467349 (1995-11-01), Huey et al.
patent: 5513134 (1996-04-01), Cooperman et al.
patent: 5517441 (1996-05-01), Dietz et al.
patent: 6055234 (2000-04-01), Aramaki
Betty Prince, et al.,Semiconductor Memories, A Handbook of Design, Manufacture and Applications, Second Edition, Basic Memory Architecture and Cell Structure, 5.3 Data Storage Elements, pp. 152-154.

Affiliated with

Also associated with

Rating

Sequentially comparing content addressable memory does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Sequentially comparing content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sequentially comparing content addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2491150