Content addressable memory

Details Content addressable memory Content addressable memory

2001-12-06

2002-12-17

Nguyen, Viet Q. (Department: 2818)

Static information storage and retrieval

Associative memories

Ferroelectric cell

C365S203000, C365S204000, C365S230030, C365S189070

Reexamination Certificate

active

06496398

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to semiconductor memory, and more specifically relates to providing an improved content addressable memory (CAM).
2. Background of the Invention
Content addressable memory, also called “associative memory”, is a type of storage device which includes comparison logic with each bit of storage. A data value is broadcast to all words of storage and compared with the data values in storage. Words that match are flagged in some way. Subsequent operations can then work on flagged words, e.g., read the flagged words out one at a time or write to certain bit positions in all of the flagged words. A CAM can thus operate as a data parallel processor, also referred to as SIMD processor (Single Instruction/Multiple Data). Moreover, content addressable memories are often used in caches and memory management units.
The content addressable memory described in U.S. Pat. No. 5,870,324 has two memory arrays D
0
′ and D
1
′ to store all memory locations. The memory array D
0
′ contains two blocks D
00
and D
10
. The block D
00
stores the bit positions
0
to
11
of a first portion of the memory locations, whereas the block D
10
stores the bit positions
0
to
11
of a second portion of the memory locations. The memory array D
1
′ contains blocks D
01
and D
11
, which store the bit positions
12
to
23
of the first and the second portion of the memory locations, respectively. A location with a width of 24 bits is therefore divided into two halves in the described CAM.
The memory arrays D
0
′ and D
1
′ are each electrically linked through bit line drivers and write heads S
0
′ and S with the input lines B
0
to B
11
and compare lines CD
0
to CD
1
, and with the input lines B
12
to B
23
and the compare lines CD
12
to CD
23
, respectively. A read/write memory block E
0
′ belongs to the memory array D
0
′, whereas a read/write memory block E
1
′ belongs to the memory array D
1
′. The read/write memory blocks E
0
′ and E
1
′ have both an enable circuit, which allows writing in a read/write cell of one of the blocks E
0
′ or E
1
′. Each of the blocks D
00
, D
01
, D
10
and D
11
is linked through corresponding match lines MATCH
00
, MATCH
01
, MATCH
10
and MATCH
11
with an enable circuits. Each location having 12-bit positions of one of the blocks D
00
, D
0
, D
10
and D
11
thereby has a separate match line.
The match lines MATCH
00
and MATCH
01
, or MATCH
10
and MATCH
11
, are linked logically in an AND-operation in the enable circuits. Only when both of the match lines MATCH
00
and MATCH
01
, or MATCH
10
and MATCH
11
, indicate that the corresponding bit positions of the comparison data on the match line correspond to those bits stored in the blocks of a data word, the corresponding enable circuit gets activated for that location in the blocks in which the agreement was determined. The information of the agreement of the comparison data and a stored data word is then flagged by writing into a corresponding read/write cell of one of the read/write blocks E
0
′ or E
1
′. This information can then be read out through output lines Out
0
and Out
1
which are linked with the read/write blocks E
0
′ or E
1
′ through output drivers. The enable circuit, the logical AND-operation of the match lines and the read/write cell of the memory block E
0
′ is implemented for each memory location of the CAM.
BRIEF SUMMARY OF THE INVENTION
An object of the present invention is to provide an improved content addressable memory which will flag memory locations of which the content only partially matches a given comparison value.
A content addressable memory according to the present invention has at least one memory array having a number of memory locations. Each memory location has a predetermined number of memory cells, whereby each memory cell is able to store 1 bit of information. In the case of the memory locations having 16 memory cells, then each memory location is able to store 16 bits of information. Although 16 memory cells might form one memory location, this does not necessarily mean that all 16 memory cells forming one memory location have to be positioned adjacent to each other. It might rather be advantageous, e.g., for wiring reasons, to place memory cells side by side that belong to different memory locations.
The memory array is divided into at least a first memory block and a second memory block. It is acknowledged that, without departing from the spirit of the invention, the memory array might also be divided into more than two separate memory blocks. The first memory block is formed by a first portion of each of the memory locations and a second memory block is formed by a second portion of each of the memory locations. In other words, one part of the memory cells, e.g., the memory cells representing the lower 8 bits of the memory locations, are grouped to form the first memory block and another part of the memory cells, e.g., the memory cells representing the upper 8 bits of the memory locations, are grouped to form the second memory block.
The content addressable memory according to the present invention also has a first set and a second set of compare lines which are associated to the first and the second memory block, respectively. Compare lines are generally used to apply comparison values-to comparison units, one of which is associated to each memory cell. For example, the compare line carrying the compare signal representing the reference value of bit position 3 is connected to all comparison units associated to memory cells storing the bit position 3 in a memory location. Thus, there are as many logically different compare lines as there are bit positions in one memory location. However, physically there might be a higher number due to wiring constraints.
Furthermore, the content addressable memory includes a first and a second set of match lines, whereas the first set of match lines is associated to the first memory block, and the second set of match lines is associated to the second memory block. A match line generally combines the output of all comparison units belonging to one memory location. However, since, according to the present invention, each memory location is divided into at least two portions, two times as many match lines as there are memory locations are distinguished.
Pre-charge units are provided for charging the match lines before a comparison operation. For performance reason the content-addressable memory according to the present invention is implemented using dynamic logic. Therefore, pre-charging of the match lines is necessary. The pre-charging brings the match line into a high-level state. During the following comparison operation, the match line keeps its high-level state if all bit positions of a memory location correspond to the respective bit positions of the comparison value. In case there is only one mismatch, the level of the match line is pulled down to a low-level state. The pre-charge units may be combined with other units, e.g., with a comparison unit, or may be distributed, e.g., parts connected to the match line, whereas other parts might be connected to the comparison unit. The pre-charge units may even not directly cause the match line to go into the pre-charge-state, as it will be apparent from the detailed description of a preferred embodiment below.
In order to allow that a match of only a subset of all bit positions of a memory location with the respective comparison value generates a match signal, the results of the comparison of the first memory block and the result of the comparison of the second memory block are logically combined. In the above example, in which a 16 bit wide memory location is divided into a lower and an upper 8 bit portion, a partial match of either the lower 8 bits or the upper 8 bits might generate a match signal, depending on how the results of both comparisons are combined. In the case of onl

Affiliated with

Also associated with

Rating

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 Content addressable memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2977111