Content addressable memory (CAM)

Details Content addressable memory (CAM) Content addressable memory (CAM)

1999-02-17

2002-04-16

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C711S158000, C711S170000

Reexamination Certificate

active

06374325

ABSTRACT:

TECHNICAL FIELD OF THE INVENTION
The present invention relates generally to computer memories, and more particularly to a content addressable memory with reduced size, power, and access time and increased floor planning flexibility.
BACKGROUND OF THE INVENTION
Random access memory (RAM) is the memory most often used in current electronic systems. In a RAM, the address of data is provided on an address bus and the corresponding data is then retrieved. The width of the address bus determines how many memory locations can be addressed and thus determines the size of the memory.
Another type of memory is content addressable memory (CAM). In a CAM, the data itself is provided in a special register. The CAM is then searched for the data by comparing each bit of the data with each bit of the information stored in the CAM. If a match is found, a match flag is set to indicate that the data was found. A priority encoder then prioritizes the matching locations (if more than one match was found) and generates the corresponding address of the highest priority matching location. One application for the CAM is in a memory cache system in which the matching process is used to determine whether the cache includes data needed elsewhere, such as data requested by a processor.
Since the CAM is searched based on the contents of the memory location rather than based on the data location in the memory, and further, since the same data content may be found in more than one location in the CAM, the CAM is also useful in applications in which it is desirable to retrieve multiple items from memory simultaneously. The highly parallel nature of content addressing is also an advantageous feature useful, for example, in processing high level algorithmic functions. Use of the CAM in these types of applications, however, also generally requires much larger CAMs than typically used in a cache. For smaller CAMs such as those used in cache applications, a primary concern is fast, efficient access and thus, the focus is on optimizing the access method to minimize latency. In larger CAMs, however, where the objective is to support a large number of entries, attention must be focused on maintaining an efficient layout shape and a reasonable bandwidth.
FIG. 1
shows an architectural diagram of a prior art CAM array
100
. The prior art CAM array
100
consists of 1024 words, each word having 56 bits. Each row in the CAM array
100
represents one of the 1024 words. Each of the 56 columns in the CAM array
100
represents one bit in each of the 1024 words. Thus, as shown in the prior art CAM array
100
, a long, narrow memory structure is typically used. In systems which include a CAM array such as that shown in
FIG. 1
, the CAM array may be extended to increase memory capacity by adding more rows. This long, narrow structure, however, not only becomes increasingly cumbersome as more capacity is added but also severely impacts the layout of the floor plan of any device in which it is used.
Other prior art CAM systems do little to alleviate these types of problems. Most, such as the systems described in U.S. Pat. Nos. 4,888,731, 4,928,260, and 5,388,066, simply provide more efficient methods of storing data and/or accessing data stored in the CAM array while still utilizing the conventional long, narrow architecture. Another such prior art CAM system such as described in the article entitled “Extending The CacheCAM™ Comparand Width” by Ray Parry, published by Music Semiconductor, AB-N6, concatenates adjacent entries of the typical long, narrow CAM array structure using validity bits to identify successive entries.
What is needed is a simple, easy to implement method and system for managing a CAM having a large number of entries while still maintaining an efficient layout shape and a reasonable bandwidth.
SUMMARY OF THE INVENTION
The present invention is a content addressable memory (CAM) system, having a CAM array operable to store a number of data words, each of the data words having a number of bits. The CAM is made up of rows and columns of CAM cells, each CAM cell operable to store one of the bits of one of the data words. Each row of the CAM system of the present invention stores the bits of at least two of the data words. The bits of the at least two data words on a single row are interleaved. Using a time multiplexing technique, the CAM system of the present invention accesses each of the data words on the row in turn during one of a number of cycles.
In another aspect of the present invention, a portion of the content of the data words is used to determine where on the row the data word is stored and, thus, reduces the number of cycles required to search for a particular data word.


REFERENCES:
patent: 4888731 (1989-12-01), Chuang et al.
patent: 4928260 (1990-05-01), Chuang et al.
patent: 5126968 (1992-06-01), Hamamoto et al.
patent: 5319589 (1994-06-01), Yamagata et al.
patent: 5339268 (1994-08-01), Machida
patent: 5383146 (1995-01-01), Threewitt
patent: 5388066 (1995-02-01), Hamamoto et al.
patent: 5642322 (1997-06-01), Yoneda
patent: 5818786 (1998-10-01), Yoneda
patent: 5943252 (1999-08-01), Schultz et al.
patent: 6098147 (2000-08-01), Mizhuhara
patent: 6101116 (2000-08-01), Lien et al.
patent: 6108747 (2000-08-01), Kaganoi
“Extending the CacheCAM™ Camparand Width”, Ray Parry, Music Semiconductors, May 28, 1997, Rev. 0.5 Web, 2 pages.
“What Is A CAM (Content-addressable Memory)?”, Ray Parry, Music Semiconductors, May 28, 1997, Rev. 1.5 Web, 2 pages.

Affiliated with

Also associated with

Rating

Content addressable memory (CAM) does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2919995