Variable width content addressable memory device for...

Details Variable width content addressable memory device for... Variable width content addressable memory device for...

2000-09-01

2003-04-22

Gossage, Glenn (Department: 2187)

Electrical computers and digital processing systems: memory

Storage accessing and control

Specific memory composition

C365S049130

Reexamination Certificate

active

06553453

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to memory devices, and more particularly to content addressable memory devices that can be searched in variable data width.
2. Description of the Related Art
Memory devices are indispensable components of modern computer systems and networks. As storage devices, they are used to provide fast access to data and instructions stored therein. Content addressable memory (CAM) is a special type of memory that is often used for performing address searches. For example, Internet routers often include a CAM for searching the address of specified data. The use of CAMs allows the routers to perform fast searches to allow computer systems to communicate data with one another over networks. In addition, CAMs are also utilized in numerous other areas such as database searches, image processing, and voice recognition applications, where fast search performance is desired.
As is well known, CAMs typically include a two-dimensional row and column content addressable memory array of core cells, such that each row contains an address, pointer, or bit pattern entry. Within such an array of cells, a CAM may perform “read” and “write” operations at specific addresses like a conventional random access memory (RAM). In addition, the CAM is also used to perform fast search operations that simultaneously compare a bit pattern of data against an entire list (e.g., column) of pre-stored entries (e.g., rows) of bit patterns in the CAM array. Based on these comparisons, the CAM typically outputs a result in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data. By thus performing comparisons simultaneously of all CAM entries, the CAM provides significant savings in search time over RAMs such as dynamic RAMs (DRAMs), static RAMs (SRAMs), and the like.
In modern computer systems and networks, CAMs are often used in various applications having different data size requirements. In Internet routers and switches, for example, a CAM may be used in medium access control (MAC) level switching, asynchronous transfer mode (ATM), and various network layer protocols such as Internet protocol (IP) versions 4 (Ipv4), 6 (Ipv6), and the like. As is well known in the art, the ATM often uses 32-bit data fields while the MAC level 2 addressing typically uses 48 to 64-bit data sizes. The data sizes may vary further depending on specific applications. For example, the 64-bit data size for the MAC level addressing may be increased to 128 bits when both the source and destination addresses are used in switching.
To address such varying data size requirements, one conventional approach has employed a CAM chip with a multitude of macros, each of which is configurable to a specific data size requirement.
FIG. 1A
shows a block diagram of a conventional CAM chip
100
having four macros
102
,
104
,
106
, and
108
. Each of the macros
102
,
104
,
106
, and
108
is configurable by a user to specified widths for various applications. For example, the macro
102
is configured as a 4K×64 block (i.e., 4K entries of 64 bit data width); the macros
104
and
108
are configured as an 8K×32 block (i.e., 8K entries of 32 bit data width); and the macro
106
is configured as a 2K×128 block (i.e., 2K entries of 128 bit data width). Thus, in this arrangement, all entries in a single macro have the same width.
FIG. 1B
illustrates a block diagram of a macro
120
depicting various widths into which it can be configured. As shown, the macro
120
includes a plurality of blocks
122
,
124
,
126
,
128
, and
130
, which can be configured into 32-bit width, 64-bit width, 128-bit width, or 256-bit width. For example, each of the blocks
122
,
124
,
126
, and
128
may be used to provide 32-bit width. Alternatively, blocks
122
and
124
may be used to provide data width size of 64 bits.
Unfortunately, however, the width of conventional macros
102
,
104
,
106
,
108
, and
120
is typically configurable on the block level only using associated registers that specify data size for each of the macros. This means that each of the macros
102
,
104
,
106
,
108
, and
120
cannot accommodate more than one data size at the same time. The configuration of macros at the block level often results in wasting of valuable memory space. For example, if the macro
120
can accommodate 128 bit data width but is actually configured into 64 bit data width, half of the memory space will not be used, thus resulting effectively in the waste of 50% of memory space. Likewise, if the macro
120
can support up to 64-bit data width but is configured into 32-bit data size, half of the memory space will be lost. In addition, the use of macros generally requires the users or customers to be intimately knowledgeable about the macros and their data sizes to avoid overflow of the macros. Furthermore, if the macros are reprogrammed to different data sizes, valuable data (e.g., search statistics) could be lost in the process.
Thus, what is needed is a CAM device that can store variable data size widths for searching variable width data without wasting valuable memory space, thereby maximizing the usage of CAM space with attendant savings in cost.
SUMMARY OF THE INVENTION
The present invention fills these needs by providing variable width CAM devices for searching data of variable widths. It should be appreciated that the present invention can be implemented in numerous ways, including as a process, an apparatus, a system, a device, or a method. Several embodiments of the present invention are described below.
In one embodiment, the present invention provides a variable width CAM device for searching data of variable widths. The CAM device includes a plurality of CAM blocks and a plurality of dual-mode first encoders. The plurality of CAM blocks is configured to store a plurality of data of variable widths with each data having one or more data portions of one or more predetermined widths. Each CAM block is configured to store a predetermined width portion of the data such that each data is stored in one or more CAM blocks. The CAM blocks receive a search data having a specified number of search data portions with each search data portion having one or more predetermined widths. Each CAM block receives a search data portion of the search data for searching the search data in the CAM blocks. The plurality of dual mode first encoders is configured for concatenating the specified number of the CAM blocks to generate one or more search results. A set of the dual mode first encoders concatenates the specified number of CAM blocks to match the width of the search data. The remaining dual mode first encoders generate one or more search results when the concatenated CAM blocks contain data that matches the search data.
In another embodiment, the present invention provides a variable width CAM device including a plurality of CAM blocks and a plurality of first encoders. The plurality of CAM blocks is configured for storing a plurality of data having a plurality of widths. Each CAM block has a plurality of entries with each entry being configured to store a predetermined width data portion of one of the plurality of data. Each of the plurality of data is stored in one or more entries that are located in different CAM blocks. The CAM blocks are arranged to receive a search data having a specified number of search data portions such that each CAM block receives one search data portion having the predetermined width. Each entry in the CAM blocks is capable of generating a match result when the predetermined width data portion in each entry matches the search data portion of the predetermined width. The plurality of first encoders is configured to sequentially couple the plurality of CAM blocks in the specified number to match the width of the search data. Each first encoder is associated with one CAM block for receiving the match results from the entries in the associated CAM block. A set of the first encoders transmits

Affiliated with

Also associated with

Rating

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

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3013796