Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2000-09-01
2002-03-26
Ho, Hoai V. (Department: 2818)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S230050, C711S108000
Reexamination Certificate
active
06362990
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to memory devices, and more particularly to a content addressable memory device for providing uninterrupted search operations synchronized with read/write operations and independent search and maintenance interfaces.
2. Description of the Related Art
Memory devices are indispensable components of modem computer systems. 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 address searches to allow computer systems to communicate data with one another over networks. Besides routers, CAMs are also utilized in other areas such as database searches, image processing, and voice recognition applications.
CAMs generally include a two-dimensional row and column content address memory array of core cells, such that each row contains an address, pointer, or bit pattern entry. Based on such array of cells, a CAM may perform “read” and “write” operations at specific addresses like a conventional random access memory (RAM). In addition, it also performs “search” operations that simultaneously compare a bit pattern of data known as “comparand” against an entire list (i.e., column) of pre-stored entries (i.e., rows) of bit patterns in the CAM array.
Conventional CAMs are typically two port devices.
FIG. 1A
shows a block diagram of a conventional two-port CAM
100
. The CAM
100
includes an input port
107
and an output port
109
. The input port
107
communicates data and control signals over a data bus
102
for communicating data and an instruction bus
104
for transmitting instructions associated with an operation to be performed. The data bus
102
is used to receive a comparand or write data as inputs and is thus shared for performing either a search operation or a write operation.
The output port
109
is shared for a search operation or a read operation. Specifically, the output port
109
outputs either search results or read results from the CAM
100
via an output bus
106
. In a search operation, for example, the CAM
100
may output a search result, via output bus
106
, in the form of an address, pointer, or bit pattern corresponding to an entry that matches the input data. Alternatively, the read results may be output through the data bus
102
.
The conventional CAM
100
typically performs operations such as search, read, and/or write operations in sequence.
FIG. 1B
shows an exemplary sequence of operations that are serially performed in successive memory clock cycles by the CAM
100
. As shown in
FIG. 1B
, the CAM performs a series of operations beginning with three “search” operations, a “write” operation, two “search” operations, a “write” operation, two “read” operations, and ending with two “search” operations. These operations are performed one after another, in sequence, with each operation being performed in at least one clock cycle.
Unfortunately, however, the sequential nature of the CAM operations degrade the performance of a CAM by delaying search operations. This is because the “read” and “write” operations interrupt “search” operations. As can be appreciated, the interruption in such search operations presents a significant impediment to high speed “real time” successive address searching and thereby complicates system design. For example, Internet routers are often called upon to perform many searches of routing tables stored in their CAMs. In such situations, interruptions in searches delay the processing of search operations and thus slow down the response times of computer systems in general.
Additionally, the sharing of the input port
107
by comparand and write data typically requires multiplexing of comparand and write data for input to the CAM
100
Similarly, the sharing of the output port
109
for outputting search results and read results also entails de-multiplexing these results.
FIG. 1C
shows a more detailed block diagram of the conventional two-port CAM
100
with a multiplexer
111
and a de-multiplexer
113
. The CAM
100
includes a control block
108
and a CAM array
110
. The multiplexer
111
receives a comparand and/or write data as inputs and selects either the comparand or the write data for output in response to a control signal. The selected output from the multiplexer
111
is then provided to the data bus
102
for input to the CAM array
110
.
To control the operation of the CAM
100
, control signals are provided to the instruction bus
104
for input to the control block
108
. In response to the control signals, the control block
108
generates another set of control signals for controlling the operations of the CAM array
110
. In a search operation, the CAM array
110
outputs, on the result bus
106
an address, pointer, or bit pattern (collectively referred herein as “address”) corresponding to an entry or word in the CAM array
110
that matches the input data on the data bus
102
. For a read operation, on the other hand, the CAM outputs on the result bus
106
data corresponding to the address provided on data bus
102
.
The demultiplexer
113
is coupled to receive an output result from the output bus
106
as an input. When the CAM operation is a search operation, the demultiplexer
113
routes the output result onto a search data bus
115
. On the other hand, when the CAM operation is a read operation, the demultiplexer
113
routes the output result onto a read data bus
117
.
FIG. 1D
shows another block diagram of the conventional CAM
100
in more detail. The CAM
100
includes data bus
102
, instruction bus
104
, result bus
106
, control block
108
, CAM array
110
, multiplexer (MUX)
112
, comparand register
114
, global mask registers
116
, status register
118
, and address counter
120
. The control block
108
receives instructions for a desired operation through instruction bus
104
, and generates the control signals for the “search,” “read,” and “write” operations of the CAM array
110
. The CAM
100
illustrated in
FIG. 1D
is commercially available, for example, as model NL85721 Ternary Content Addressable Memory IPCAM from Netlogic Micosystems, Inc.
Unfortunately, using a multiplexing scheme in performing read/write and search operations adds complexity in implementing conventional two-port CAMs with attendant increase in cost. Furthermore, the multiplexing scheme slows down overall CAM performance since read/write data cannot be input or output simultaneously in a same clock cycle with a search data or result. Indeed, a read or write operation must “steal” cycles from the search operations because the buses
102
and
106
are shared.
In view of the foregoing, there is a need for a CAM device and method that can perform read/write operations and search operations simultaneously without multiplexing input data and output results so as to improve CAM performance.
SUMMARY OF THE INVENTION
The present invention fills this need by providing three-port content addressable memory (CAM) devices and methods for implementing the same. 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 three-port CAM device including a CAM, a search control block, and a maintenance control block. The CAM is configured to store data. The search control block is arranged to receive search data and search control signals via a first port for searching the search data in the CAM. The search control block is further configured to perform search operations by accessing the CAM. The search operations are performed within search cycles with each search operation being performed over multiple clock cycles. In t
Gibson G. F. Randall
Schultz Kenneth J.
Shafai Farhad
Ho Hoai V.
Martine & Penilla LLP
SiberCore Technologies
LandOfFree
Three port content addressable memory device and methods 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 Three port content addressable memory device and methods for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Three port content addressable memory device and methods for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2846720