Static information storage and retrieval – Associative memories – Ferroelectric cell
Reexamination Certificate
2000-10-06
2002-03-26
Robertson, David L. (Department: 2187)
Static information storage and retrieval
Associative memories
Ferroelectric cell
C365S189070
Reexamination Certificate
active
06362992
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to static information storage and retrieval systems, and more particularly to associative memories, which are also referred to as content or tag memories.
BACKGROUND ART
Many real world applications today require searching information at high speed. In particular, as network-systems proliferate in which data packets are transferred based on the contents of address information contained there in, it is increasingly desirable to perform very high speed comparisons to deliver such data packets (“routing” and “switching” are the terms particularly used in the network field). This has motivated the network industry to turn to hardware solutions, including a class of circuits known as “content addressable memories” (CAM). The following discussion will generally use this example of packet routing and switching in networks, although many other applications also exist where high speed searching is desirable, and where the present invention may be useful.
The data packet routing and switching in networks generally employs a matching function, wherein a header field in the data packet is compared to a number of table entries. There are basically two types of information search which are of interest in this role, exact match search and partial match search.
For these two types of information searching two types of CAMs are available. Binary CAM can only be used for exact match search applications. Ternary CAM, on the other hand, can be configured and used for exact match and partial match search applications.
To some extent, CAM can be compared to more widely known random access memories (RAM). CAM cells must be both readable and writable, just like RAM cells. However, CAM operates in the converse way that RAM operates. In a RAM, the input is an address and the output is the data stored at that address. In a CAM, the input is a data sample and the output is a flag to indicate a match, as well as an address of matching data.
For example, a typical unit today is a 128 bit by 1024 (or 1K) CAM, which can be used to compare a 128 bit data sample against a “database” of 1024 potential matches. The time period required for this is inherently short and is generally consistent despite the database size, ignoring extrinsic factors. It is this ability which CAMs provide to quickly search wide data words against large address spaces (databases) which makes them highly useful.
FIGS. 1
a
and
1
b
(background art) summarize examples of logic operation in binary and ternary CAM, respectively. In
FIG. 1
a
, a binary CAM unit has the content of
1010
stored at address
0
; the content of
1010
also stored at address
1
; the content of
1100
stored at address
2
; and the content of
1000
stored at address
3
. If the data
1010
is input to this binary CAM, a flag indicates a match and an output of
0
is generated, indicating the first match address. If the data
1100
is input to this CAM, the flag again indicates a match and an output of
2
is generated, indicating the only match address this time. Finally, if the data
1001
is input, the flag does not indicate a match (any output should be ignored). In this example there will never be a output of
1
, since we are presuming a prioritization which provides the lowest matching address.
In
FIG. 1
b
, a ternary CAM unit has the content of
1010
with the mask
0000
stored at address
0
; the content of
1010
with the mask
0001
stored at address
1
; the content of
1100
with the mask
0000
stored at address
2
; and the content of
1000
with the mask
0001
stored at address
3
. If the data
1010
is input to this CAM, a flag indicates a match and an output of
0
is generated, indicating the first match address (again prioritized). If the data
1100
is input to this CAM, the flag again indicates a match and an output of
2
is generated, indicating the (only) match address. However, if the data
1001
is input to this ternary CAM, the flag indicates a match and an output of
3
is generated. This occurs because the mask here has filtered the last bit of the content—with this content and mask data of either
1000
or
1001
this same result would be produced. Continuing, if the data
1101
is input to this ternary CAM, the flag here will not indicate a match.
In the above ternary CAM example there could potentially be a valid address output of
1
. This would occur if the data
1011
were input. Also, in this ternary CAM example longest prefix type masks have been used. Such longest prefix masking is particularly useful in modern network routing and switching schemes, where the leading bits, or prefixes, of addresses are often all that is important in routing and switching.
FIG. 2
(background art) is a block diagram which stylistically depicts how a typical CAM unit
10
contains three logic blocks
12
: a CAM array block
14
, a match detection block
16
, and a priority encoder block
18
. A data input
20
and a result output
22
complete this simple representation.
The CAM array block
14
contains CAM cells and comparison logics, discussed presently, which receive a signal for comparison with a signal at the data input
20
. The match detection block
16
contains logics to generate a match signal for each CAM entry. The priority encoder block
18
takes in the match signals (from the match detection block
16
) and outputs the address of the highest priority matched entry, as a signal at the result output
22
.
FIG. 3
(background art) is a block diagram which stylistically depicts how a typical binary CAM unit
30
includes three major logic blocks
32
(analogous to the logic blocks
12
of FIG.
2
), and which particularly depicts the details of a CAM array block
34
and a match detection block
36
. A priority encoder block
38
is also shown here, but not depicted in detail since it may be conventional (or even omitted). Finally, an input bus
40
(analogous to the simplified data input
20
of
FIG. 2
) and a result output
42
are also provided.
The binary CAM array block
34
contains many binary CAM cells
44
. Each such binary CAM cell
44
typically consists of a comparator logic cell
46
and a content location
48
, typically equivalent to a SRAM bit. All of the content locations
48
have entry data bits stored in them before the binary CAM unit
30
is used. The data to be searched (“compared” or “matched”) may then be provided on the input bus
40
(here extending from B
0
to Bn). The unit data searched in a CAM is often referred to as a “word,” although this comparand data may be much longer than an 8-bit word, e.g., 32 bits or 128 bits are typical in current commercially available CAMs.
The comparator logic cell
46
basically compares the data on the input bus
40
with the data pre-stored in the content location
48
, and then outputs a bit signal
52
.
FIG. 3
a
(background art) depicts a simplified gate logic equivalent of the comparator logic cell
46
. The bit signal
52
is a 1 if the data are the same or a 0 if they are different (in principal, the logical inverse of an exclusive OR logic). In actual practice, say, at an integrated circuit die level other gate logic may be used or semiconductors may be employed in manners which blur distinction between individual logical units and thus may not form distinct “gates.” Accordingly, this is a conceptual representation, which skilled in the art will appreciate may be implemented in many different manners.
Returning to
FIG. 3
, all of the respective bit signals
52
output from the comparator logic cells
46
, in a respective entry (row), go to the match detection block
36
. The match detection block
36
includes a series of AND gates
54
, one per respective entry (row) in the CAM. All of the bit signals
52
for a respective entry (row) are directed to one such AND gate
54
, and if all of the respective bit signals
52
are true (all 1's) the AND gate
54
generates a respective match signal
56
. Again, this also is a conceptual representation of what may be employed in actuality.
These m
Purple Ray, Inc.
Roberts Raymond E.
Robertson David L.
LandOfFree
Binary-ternary 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 Binary-ternary content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Binary-ternary content addressable memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2849075